スライドパズルを解くプログラムに関する次の記述を読んで，設問に答えよ。
表1のルールで定義されるスライドパズルについて考える。
表1 スライドパズルのルール
一辺が3マスのスライドパズルの例を図1に示す。
図1 一辺が3マスのスライドパズルの例
本問では，一辺のマスの個数が任意のスライドパズルにおいて，ゴールの盤面になるまでの駒の移動回数が最小となる移動方法（以下，最小解という）を一つ求めるプログラムを作成する。
〔一辺がNマスのスライドパズルの最小解を幅優先探索を用いて求める方法〕
幅優先探索を行ったときの，スライドパズルの盤面の遷移を，グラフで表現する。開始時点の盤面をルートノード，ある時点の盤面をノード，駒の移動に伴う盤面の遷移をエッジで表現する。また，ゴールの盤面をゴールノードとして定義する。
幅優先探索で最小解を求める方法を次のように考える。ここで，Nは2以上とする。
探索対象のノードに対して，移動できる駒ごとにその駒を移動した後のノードを作成して，探索対象のノードの子ノードとし，探索対象のノードは探索済みとなる。このとき，子ノードが表す盤面が既に探索したノード（以下，探索済みノードという）と同じであれば，この子ノードは終端ノードとして，以降の探索は行わない。また，子ノードがゴールノードと同じであれば，最小解が見つかったと判断して探索を終了する。
〔Nが3の場合の例〕
一辺が3マスのスライドパズルの最小解を求める過程の例を図2に示す。
図2 一辺が3マスのスライドパズルの最小解を求める過程の例
（1）1回目の駒の移動では，ルートノードを探索対象のノードとする。ここでは，移動できる駒が三つあるので，ルートノードから深さが1となる①〜③の子ノードを作成し，ルートノードは探索済みノードとなる。ここで，①〜③の子ノードに対して，ゴールノードの判定及び終端ノードの判定を行う。
（2）次に，作成した子ノードで終端ノード以外のノードをそれぞれ探索対象のノードとし，駒の移動にあわせて子ノードを作成する。図2では，①〜③のノードから④〜⑪の子ノードを作成し，①〜③は探索済みノードとなる。ここで，④〜⑪の子ノードに対して，ゴールノードの判定及び終端ノードの判定を行う。図2では，盤面が探索済みノードと一致する⑤，⑥及び⑩は終端ノードとなり，以降の探索は行わない。
（3）以降，（2）で作成したノードの子ノードの作成と，ゴールノードの判定及び終端ノードの判定を繰り返す。図2の⑫は，n回目の移動でゴールノードに至ったことを示している。なお，全てのリーフノードが終端ノードと判定された場合，ゴールの盤面に至る駒の移動方法がないことを意味しているので，その旨のメッセージを出力して探索を終了する。
次に，配列を用いた盤面の表現方法を図3に示す。ここで，空白マスを表す値は最も大きい駒の数字である8に1を加えた9とする。なお，配列の要素番号は1から始まるものとする。
図3 配列を用いた盤面の表現方法
〔一辺がNマスのスライドパズルの最小解を求めるプログラム〕
一辺がNマスのスライドパズルにおいて，開始時点の盤面をランダムに作成し，最小解を求め，開始時点の盤面からの遷移及び駒の移動回数を出力するプログラムを作成する。開始時点からの盤面の遷移を保持する単方向連結リストの要素となるクラスBoardStateの説明を図4に，キューを実現するクラスQueueの説明を図5に，リストを実現するクラスListの説明を図6に，プログラムで使用する主な関数を表2に，最小解を求めるプログラムを図7に示す。
図4 クラスBoardStateの説明
図5 クラスQueueの説明
図6 クラスListの説明
表2 プログラムで使用する主な関数
図7 最小解を求めるプログラム
設問1 図2中の②の盤面を図3に倣って，配列で答えよ。
解答・解説
解答例
XXX
解説
XXX
設問2 図7中の ア 〜 ク に入れる適切な字句を答えよ。
解答・解説
解答例
XXX
解説
XXX
IPA公開情報
出題趣旨
未公開
採点講評
未公開
