箱入り娘パズルを自動で攻略するシステムを作成した

今回つくったもの

箱入り娘というパズルを幅優先探索を使って自動で解くシステムを作りました。

箱入り娘パズルとは

箱入り娘とは、駒を空いている位置にスライドさせることによって、一番大きな娘の駒を、枠下部の出口に移動させるパズルです。

枠の切れ目部分に娘の駒を運べればクリアです。

使い方

以下のコードを実行すると、パズルが自動で解かれ、クリアまでの手順がファイル内に描画されます。

$ git clone https://github.com/mimic-asy/HakoiriCpp.git
$ cd HakoiriCpp
$ mkdir build
$ cd build
$ cmake ..
$ make
$ ./Hakoirimusume  
$ cd ..
$ python3 make_fig.py # 時間がかかります

どのように動いているのか

前提

箱入り娘のパズルは、盤面同士の関係をグラフ構造で表すことができます。盤面がノード、駒の移動がエッジに相当します。

手法

幅優先探索で、スタート盤面からクリア盤面までの経路を求めました。

なぜ幅優先探索を用いたのか

深さ優先探索では新しい盤面を発見できない場合、以前に探索した盤面に再び戻り、繰り返し探索を行います。
箱入り娘のパズルの特性上、同じ盤面に何度も遭遇するため、深さ優先探索では探索時間が莫大にふえてしまいます。このため今回は幅優先探索を用いています。

今後の展望

更に構造を理解して高速化を行い、１分以下になるようにする。

2023/11/5 追記

１分以上探索＋経路捜索に時間がかかっていたが、今回の改良によって３秒位で処理が終わるようになった。

変更点

・幅優先探索の際vectorに既存の盤面を保存しFor文でvector内部の盤面と現在の盤面の確認をしていたが、unorderd_mapに保存するように変更した。辞書構造で既存の盤面を検索できるようにした。

・盤面を自動で動かす関数を見直し、余分なコピーを減らした。

・stringでいくつか比較を行っている箇所をIntで比較するように変更した

・保守性の向上のため、const,参照渡し等の見直しをした。

以上の点を改良した結果、高速化が実現した。