問題の定義
「箱入り娘」は、下図に示すように枠の中に収められた大きさの異なる 1×1、2×1、1×2、2×2 のタイルが空いているスペースを使って縦、横に動かせるようになっている一種のスライディングパズルです。最初（A）のように奥に置かれた一番大きな2×2のタイルを、周りのタイルを縦、横にスライドさせることによって、最終的に（B）の様に出口の位置まで移動させて外に出すのがパズルの目的です。最終状態において、2×2以外のタイルの配置については任意です。
タイルには通常下の図のように名前が書かれています。（a）がオーソドックスな「箱入娘」の文字ですが、将棋になぞらえた（b）、三國志の世界をイメージした（c）のようなものもあり、それぞれにストーリー性があります。
ここでは（あ）のタイプで話を進めることにすると、下図の（a）のように最初一番奥にいる「娘」を出口まで移動させるのですが、途中、他のタイル、特に番頭のタイルが邪魔になりなかなか難しいのです。小うるさい番頭が箱入り娘の自由を邪魔しているようです。（笑）それでもなんとか（b）のように「娘」を出口まで移動できたらパズルが解けたことになります。
このパズルは最近ではスマートフォンの上でも手軽に楽しむことができ、下のリンクのようなものがあります。
play.google.com
この問題をコンピュータで解くことを考えたとき、上の（a）において、それぞれのタイルを、空き：０、娘：１、父親：２、母親：３、下男：４、下女：５、番頭：６、小僧：７という数字で表すと扱いやすくなります。そうすると盤面の初期状態は下図（ア）のように書き表せます。タイルの4種類の異なった形をしていますが、最小の１×１のタイルを単位として、盤面を５×４の枡目で考えることにします。そして各枡目の値をそこに置かれているタイルの番号で表すようにすると初期状態は（イ）のように表現できます。
このとき、２，３，４，５は2×1の縦長の同じ形状のタイルですが、それらは区別する必要があります。というのは、下図のようになったとき、空きを表す０の左側に2×1の縦長のタイルがありますが、（あ）と（い）では明らかに異なるからです。
そして、下図のように出口のすぐ上の２つの枡目の値が１になるようにタイルを移動できた時にパズルが解けたことになるわけです。
この盤面とそれが変化しうる状態を階層的な木構造で保持し、その空間の中を効率的に探索すればこのパズルを解くことができそうです。その探索方法を次回考えることにします。
箱入娘を解く その０ ⇐ ⇒ 箱入娘を解く その２
