paizaの問題で15パズルを解くプログラムを書きました
与えられた配置をできるだけ少ないスライド回数で解く問題です(実行時間時間制限あり)
15パズル
1から15のパネルが4かける4の正方形に配置されていて、パネルをスライドさせていって1から15までが順番に並ぶようにするものです
File:15-puzzle.svg - Wikimedia Commons
動かす回数が多くなってもよいなら、簡単に解ける方法があるみたいなので人間はこっちを使ったほうがよいでしょう
解き方
パズル系の問題はだいたい幅優先探索や深さ優先探索で解けます
知識としては知っていましたが自分で書いたことはなかったので、今回は幅優先探索、最良優先探索、A*探索、双方向探索あたりを書いてみました
この辺のアルゴリズムの説明は以下の記事が迷路の探索のアニメーションで表されていたりしてわかりやすいかもしれません
今回の問題では自分のコードでは残念ながら最良優先探索以外では手数のかかる配置が解けなかったです
最良優先探索は現在の盤面を評価して(ゴールまでのコストを推定して)、評価がよいものから順に探索していく幅優先探索の一種です。今回はパネルの最終的な位置とのマンハッタン距離の合計の2.5倍とスタートからの移動回数の和を盤面の評価としました
マンハッタン距離の合計のそのものとスタートからの移動回数の和を使うとA*探索になります。A*探索だと処理が間に合わなかったのでマンハッタン距離の合計の2.5倍という適当な係数をかけて無理矢理終わらせました
順位は30位で、1位の平均手数の39.6手とは14.8手も差がありました
今回は幅優先探索系のアルゴリズムを実装したので、次になにかやる機会があれば反復深化深さ優先探索とかを実装してみたいです
参考資料
いろいろとググりながらやったので勉強になりました
やはり手を動かさないと覚えませんね
1位の人の記事
- A*探索で15パズルにも挑戦してみた。 - 似非学問的な手記
- M.Hiroi's Home Page / Puzzle De Programming
- 15パズル自動解答プログラムの作り方
- GDD2011 DevQuiz のスライドパズル晒し祭りをまとめてみた - Fire and Motion
- 幅優先探索すら知らない素人がDevQuizで満点を取るまでの話
- GDD2011, DevQuizのスライドパズルの解答コードを公開しました - Goto_youthKの徒然日記
- blog.k11i.biz: GDD2011 DevQuiz のスライドパズルに挑戦してみました
スライドパズルの解法系の記事
探索の種類とか可視化とかの記事
ソースコード
# -*- 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