唯物是真 @Scaled_Wurm

プログラミング(主にPython2.7)とか機械学習とか

最良優先探索で15パズルを解いてみた(paizaオンラインハッカソン5+)

python 競技プログラミング

paizaの問題で15パズルを解くプログラムを書きました
与えられた配置をできるだけ少ないスライド回数で解く問題です(実行時間時間制限あり)

15パズル

1から15のパネルが4かける4の正方形に配置されていて、パネルをスライドさせていって1から15までが順番に並ぶようにするものです
f:id:sucrose:20150524224525p:plain
File:15-puzzle.svg - Wikimedia Commons

動かす回数が多くなってもよいなら、簡単に解ける方法があるみたいなので人間はこっちを使ったほうがよいでしょう

解き方

パズル系の問題はだいたい幅優先探索ã‚„深さ優先探索で解けます
知識としては知っていましたが自分で書いたことはなかったので、今回は幅優先探索、最良優先探索、A*探索、双方向探索あたりを書いてみました
この辺のアルゴリズムの説明は以下の記事が迷路の探索のアニメーションで表されていたりしてわかりやすいかもしれません

今回の問題では自分のコードでは残念ながら最良優先探索以外では手数のかかる配置が解けなかったです
最良優先探索は現在の盤面を評価して(ゴールまでのコストを推定して)、評価がよいものから順に探索していく幅優先探索の一種です。今回はパネルの最終的な位置とのマンハッタン距離の合計の2.5倍とスタートからの移動回数の和を盤面の評価としました
マンハッタン距離の合計のそのものとスタートからの移動回数の和を使うとA*探索になります。A*探索だと処理が間に合わなかったのでマンハッタン距離の合計の2.5倍という適当な係数をかけて無理矢理終わらせました

順位は30位で、1位の平均手数の39.6手とは14.8手も差がありました
f:id:sucrose:20150524225558p:plain
今回は幅優先探索系のアルゴリズムを実装したので、次になにかやる機会があれば反復深化深さ優先探索とかを実装してみたいです

参考資料

いろいろとググりながらやったので勉強になりました
やはり手を動かさないと覚えませんね

1位の人の記事

スライドパズルの解法系の記事

探索の種類とか可視化とかの記事

ソースコード

# -*- coding: utf-8 -*-
import sys
import heapq

field = []
for line in sys.stdin:
    sp = line.split()
    L = len(sp)
    field += sp

cur = field.index('*')

#移動可能な場所を列挙
RIGHT, LEFT, DOWN, UP = [1, -1, L, -L]
move = []
for i in xrange(L * L):
    temp = []
    if i % L != L - 1:
        temp.append(RIGHT)
    if i % L != 0:
        temp.append(LEFT)
    if i / L != L - 1:
        temp.append(DOWN)
    if i / L != 0:
        temp.append(UP)
    move.append(temp)

END = map(str, range(1, L * L)) + ['*']

#マンハッタン距離を計算
md = 0
for i, n in enumerate(field):
    n = int(n) if n != '*' else L * L
    ox = (n - 1) % L
    oy = (n - 1) / L
    x = i % L
    y = i / L
    md += abs(ox - x) + abs(oy - y)

q = []
heapq.heappush(q, (2.5 * md, md, 0, field[::], cur, 0, []))

visited = set([tuple(field)])

for i in xrange(10**8):
    if not q:
        break
    cost_est, md, cost, state, cur, last, history = heapq.heappop(q)
    for d in move[cur]:
        #直前の状態に逆戻りしない
        if d == -last:
            continue
        
        temp = state[::]
        #交換する
        temp[cur], temp[cur + d] = temp[cur + d], temp[cur]
        #マンハッタン距離の差分を計算
        md_diff = 0
        for i, n in [(cur, temp[cur]), (cur + d, temp[cur + d])]:
            n = int(n) if n != '*' else L * L
            ox = (n - 1) % L
            oy = (n - 1) / L
            x = i % L
            y = i / L
            md_diff += abs(ox - x) + abs(oy - y)
        for i, n in [(cur, temp[cur + d]), (cur + d, temp[cur])]:
            n = int(n) if n != '*' else L * L
            ox = (n - 1) % L
            oy = (n - 1) / L
            x = i % L
            y = i / L
            md_diff -= abs(ox - x) + abs(oy - y)
        #終了確認
        key = tuple(temp)
        if temp == END:
            print '\n'.join(history + [temp[cur]])
            break
        #訪問済みかどうかを確認
        if key in visited or cost + 1 + md + md_diff > 1000:
            continue
        else:
            visited.add(key)
        
        heapq.heappush(q, (cost + 1 + 2.5 * (md + md_diff), md + md_diff, cost + 1, temp, cur + d, d, history + [temp[cur]]))
    else:
        continue
    break
'); jQuery.noConflict(true);