スライドパズルを解くプログラム

表1のルールで定義されるスライドパズルについて考える。

一辺が3マスのスライドパズルの例を図1に示す。

クリックで拡大

図1　一辺が3マスのスライドパズルの例

本問では，一辺のマスの個数が任意のスライドパズルにおいて，ゴールの盤面になるまでの駒の移動回数が最小となる移動方法（以下，最小解という）を一つ求めるプログラムを作成する。

〔一辺がNマスのスライドパズルの最小解を幅優先探索を用いて求める方法〕

幅優先探索を行ったときの，スライドパズルの盤面の遷移を，グラフで表現する。開始時点の盤面をルートノード，ある時点の盤面をノード，駒の移動に伴う盤面の遷移をエッジで表現する。また，ゴールの盤面をゴールノードとして定義する。

幅優先探索で最小解を求める方法を次のように考える。ここで，Nは2以上とする。

探索対象のノードに対して，移動できる駒ごとにその駒を移動した後のノードを作成して，探索対象のノードの子ノードとし，探索対象のノードは探索済みとなる。

このとき，子ノードが表す盤面が既に探索したノード（以下，探索済みノードという）と同じであれば，この子ノードは終端ノードとして，以降の探索は行わない。

また，子ノードがゴールノードと同じであれば，最小解が見つかったと判断して探索を終了する。

〔Nが3の場合の例〕

一辺が3マスのスライドパズルの最小解を求める過程の例を図2に示す。

クリックで拡大

図2　一辺が3マスのスライドパズルの最小解を求める過程の例

次に，配列を用いた盤面の表現方法を図3に示す。ここで，空白マスを表す値は最も大きい駒の数字である8に1を加えた9とする。なお，配列の要素番号は1から始まるものとする。

クリックで拡大

図3　配列を用いた盤面の表現方法

〔一辺がNマスのスライドパズルの最小解を求めるプログラム〕

一辺がNマスのスライドパズルにおいて，開始時点の盤面をランダムに作成し，最小解を求め，開始時点の盤面からの遷移及び駒の移動回数を出力するプログラムを作成する。開始時点からの盤面の遷移を保持する単方向連結リストの要素となるクラスBoardStateの説明を図4に，キューを実現するクラスQueueの説明を図5に，リストを実現するクラスListの説明を図6に，プログラムで使用する主な関数を表2に，最小解を求めるプログラムを図7に示す。