小さいサイズのスライドパズルを解かせる
この記事は
の9日目がなんか空いていたので書いている記事です。
導入
未来予知者なので、11日の枠にnaanさんの記事が投稿されることを知っています。具体的には「あほくさスライドパズル」と呼ばれる2x3サイズのスライドパズルを手で解くコツがよくまとまっており、naanさんの天才さも確かに感じられる良記事が存在する未来が見えます。
しかし、パズルを速く短く解くのは (naanさん以外の) 人間には至難の業です。 凡人にも簡単な方法としてコンピュータにこのスライドパズルを解かせてみましょう。
解き方
グラフをつくる
このパズルでは適当なピースを1個スライドすることである盤面から他の盤面に変移できます。
盤面の状態を頂点とみなし、盤面変移の関係を辺とみなしたグラフを考えます。するとスライドパズルの解を求める問題は、このグラフ上で初期盤面から正解盤面までの路を探索する問題に帰着されます！
盤面の状態数は高々6!=720通りなので、この規模ならBFSで最短路を求めても高速に動作します。
コードを書く
書きます。
書きました。 (クリックで展開されます)
解く
解きます。
$ time python3 ahokusa.py < ahokusa.in 下左上右右下左上左下 real 0m0.044s user 0m0.044s sys 0m0.000s
解けました。やったね
〆
2x3サイズなら簡単な知識だけでソルバーを作れるので、みんなも書いてみよう1
元ネタ記事の作成、およびこの記事の確認をしてくださったnaanさんに最大限の敬意を表し、記事の締めといたします。
おまけ
初期盤面をコピーしスクリプトを実行してSlackに貼り付けるまでの時間でnaanさんが解き終えていました。一生勝てません
