以前ペントミノパズルを解くプログラムを書いたことでいろいろ学ぶことがあったので、今度は箱入り娘を解くプログラムを書いてみた。
※画像はイメージです（ソルバーは単にコマンドラインで動くだけ）
箱入り娘
箱入り娘はスライドパズルの一種で、空いているマスにピースをスライドで移動させて2x2という大きなピースを外に出すのが目的。 ピースの幅が2マスあるのに空きマスも同じく2マスしかないという、かなり自由度が制限されているのが面白い。 ピースの構成にもよるけど縦長4＋横長1を含む配置だと81手になる（同じピースを連続で動かすのは1手と数える）。
ソルバーの方針
ペントミノの場合には12種類のピースをいろいろな順や向きで置いてみて全てが配置できたら解が求まる。 行き詰まったら少し戻して別の配置を調べるという、深さ優先探索を行なっていた。 しかし箱入り娘の場合は最短手順を探したいので、そのようにして解を見つけても最短かどうかはわからないので探索を打ち切ることができずにすべての局面を調べなければいけなくなってしまう。
そこで最初の状態から可能な手（複数ありえる）をそれぞれ一手進めて、さらにそれぞれに…という具合に「幅優先探索」で調べる。 それによって最初に解を見つけた時点でそれが最短手順なので、打ち切ることができる。
アルゴリズムの違いとしては、深さ優先探索の場合は保持しておくべき状態は最大の深さ程度で済むが、幅優先探索の場合は各局面から進められる手の数だけ状態が増えていくので、メモリを多く指数関数的に必要とする。
ただ箱入り娘の場合には空きが2マスだけで可能な手がそれほど多くないので、特に気にする必要はない。
ソルバーの実装
深さ優先探索では状態を辿るごとに再帰呼び出しをして、行き詰まったら関数から抜けて１つ前の状態に戻る、という方法で実装した。 幅優先探索では状態が分岐していくので違う方法を取る必要があって、キューを使う （Wikipediaにも書いてある）：
- 初期化時：キューに盤面の初期状態を入れる
- 探索時：キューから取り出して、その状態から可能な手を列挙して、それぞれの手を反映した状態をキューに積む
- 終了判定：解となる状態に達する、またはキューが空になる（すべての状態を調べ尽くした：解なし）
手を進めた状態がすでに登場した局面と同じだったら、そこから進める局面はすでにキューに登録済みなので除外する。 箱入り娘の場合、動かしたピースを逆に戻したり空きマスを一周させたりした場合などに相当する。
同じピースを連続で動かす場合は一手と数えるので、その場合はキューの先頭に積んで次に即調べるようにして、そうでなければキューの後ろに積むようにすることで最短の手順を優先で調べることができる。 またそれに関連して同じ局面でも同じ手数だけど違う手順で到達する場合があって、その最後の手と次の手が連続する可能性があるのでそれも考慮する必要がある。
重複判定はピースそのものは違っても形が一緒であれば同じと判定したり、左右対称の盤面を除外してやることで調べる局面を減らすことができる。
結果
かかった速度（環境:Macbook Air 2020）：
| 内容 | 秒 |
|---|---|
| ピースの違いを考慮してしまっている場合 | 20.46秒 |
| ピースの違いを無視する場合 | 0.08秒 |
| 盤面の左右対称を判定する場合 | 0.07秒 |
- 箱入り娘は自由度が高くないので、一瞬で解が求まってしまう
- 可能な手の最大は7、平均は3.3程度
- チェックした局面は15,360
- 万単位、なので全然大したことない（ピースの違いを無視することで相当絞り込める）
- そうしないと一千万単位になってしまいだいぶ辛い
最高難易度の配置
一番手数がかかるのは、横長3＋縦長2のケース？（103手）
$ cargo run --release -- --interactive --board=10021002334465578..9 |
--boardで初期状態を指定、--interactiveオプションでエスケープシーケンスを使ってターミナル上で一手ずつ確認できるようにした （近頃身につけた罫線キャラを使って）
ソース：https://github.com/tyfkda/Hakoiri
追記：もっと長い手の配置があるっぽい 箱入り娘パズルの攻略法
# 123手 |
# 138手 |
最長手数となる盤面を探すという「逆問題」を考えるのも面白いかも知れない。