CodinGameからパズルのお知らせがあったので挑戦してみます。
15パズルのアルゴリズムはまったく作ったことがありませんでしたが、
その縮小版のパズルがあったので始めて作ってみました。
最短手数を探して、その手を動かすパネルの位置を横、縦の位置の順で一手ずつ表示します。
スライドは1つずつです。問題はあらかじめ最短手数を決まっている盤面を提示されるようです。
A*のアルゴリズムは使っていないのですが、10手まで解けました。
画像右手のソースが全てです。
ボートをフラットにしています。"0123456789AB"が完成になります。
teはボードの各位置(0-11)から交換できる位置が入っています。
あとは迷路の探索とおなじようなアルゴリズムでいけました。
繰り返しが起こらないように発生した盤面を全て保持していますが、
このルーチンはリソースを大量にとって、探索にも大きな負担をかけています。
代替案が浮かばないのでそのままです。10手までで1400局面ほど作成していました。
A*用に解答とのズレを判断したりしているのですが、ヒープソートにしてみるとかえって遅くなったので
このデータ構造では最大の38手、1秒はまったく解けません。
しかし世界にはこれを1秒で解いているPython3の猛者がいます。
すごい
