箱入り娘パズルとは
みなさんはスライドパズルの一種、箱入り娘はご存じでしょうか
画像はwikipediaより。(引用 画像の作者名Adan パズル「箱入り娘」。 2005/7/13,Adanさんによる撮影)
箱入り娘とは、駒を空いている位置にスライドさせて移動させることによって、娘と呼ばれる２×２の一番大きな駒を、枠の下部の切れ目に移動させることを目的としたパズルです。
簡単そうに見えますが自分でやってみるとめちゃくちゃむずかしいです。
もしやってみたい方は、千葉市科学館で売っており、体験コーナーもあって遊べるのでぜひ。通販でも手に入ります。
（通販だと箱入り娘ではなくて箱入り曹操でした。箱入り曹操…？）
今回はこの箱入り娘をPythonで解いていこうと思います。
コードはこちら(githubページに飛びます）
どうやって解くか
今回は幅優先探索によって初期位置から娘を目的の位置に届けるクリアまでの経路を求めます。
箱入り娘をPython上で再現する
箱入り娘の盤面は、多重配列np.arrayを用いて再現しました。
それぞれの駒を指定しやすいように、父、母、娘...等の名前をつけました。これらの駒を並べて盤面を再現しました。
箱入り娘パズルでは、同じような形の駒が複数あるので全体としての形状は変わらず、駒の名前だけが違うパターンが多く存在します。
しかし探索する際には名前を区別する必要はなく、全体の形のみを比較したいため、比較を行う際には駒を形状ごとに数字へ変換しました
するとこのようになります。
全体の形のみを比較することができるようになるため、変換する前よりも効率的に探索を行えるようになりました。
クリアまでの経路の求め方
幅優先探索を行って新規に盤面を発見した際に、新規に発見された盤面とその一つ前の盤面を対応づけます。これを探索の各ステップで行うことで全ての盤面同士につながりができ、つながりを逆に辿ることでどの盤面からでも初期位置まで戻ることができます。これを利用してクリアとなる盤面から初期盤面までの経路を求めています。
実行結果
総盤面数と、クリアまでの経路が出ました、経路は下図のようになっております。
初期位置から116手でクリアへ辿り着くことができました。
まとめ
・箱入り娘を幅優先探索で解いてみた結果、11６手で解けることが判明しました。
・箱入り娘が取れる盤面の総数は25955個でした。
書いてみて得られたこと
・深さ優先探索も同時に実装したので幅優先探索との特性の違いを知ることができました。
・最初は、np.arrayのまま全ての処理を行なっていました。とても遅かったので盤面を文字列で表現して処理を行なったところ倍以上の速度になったので、型ごとの速さの違いを体験する良い機会となりました。
・ちゃんと動いていると思っていたものでもテストコードを書くと色々バグが出てきて、テストコードをちゃんと書かなければという意識が芽生えました。
最後に
アルバイトを募集しています。
twitterのDMやリプライでお声がけください。
https://twitter.com/Not_rinrikan