解説

問われているのは、図2の②の盤面を図3の規則に従って配列で表すことです。

各子ノードは「探索対象のノードに対して，移動できる駒ごとにその駒を移動した後のノード」です。また、図2の作成過程では「1回目の駒の移動では…ルートノードから深さが1となる①～③の子ノードを作成」とあります。つまり、②はルート盤面から空白マスに隣接する駒のどれかを1手だけ動かした盤面です。

ルートノードは中央下の部分が空白マスとなっており、この空白マスに移動可能な駒は左="3"、上="5"、右="1"の3つです。図2中の1回目の3つの盤面のうち、①は"3"を右に移動したもの、③は"1"を左に移動したものに対応しますから、残る②は"5"を下に動かしたケースだとわかります。図3の規則を整理すると、盤面と配列表現の関係は以下のようになっています（空白マスは"9"で表すことに注意）。②では"5"と"9"が入れ替わります。規則に従うと、配列表現は{{8，6，7}，{2，9，4}，{3，5，1}}となります。

∴{{8，6，7}，{2，9，4}，{3，5，1}}

解説

空欄アにはwhileループを継続するための条件式が入りますが、プログラム全体の流れを把握してからでないと理解しにくいため、説明は最後に回します。

〔イについて〕
変数 explore_queue はクラス Queue のインスタンスで、探索対象の盤面データのリストを保持しています。空欄イは.に続く字句なので、ここにはクラス Queue のメソッドかプロパティが入ります。

行21の処理では戻り値をBoardState型変数 state に入れているので、Queueの説明（図5）より、戻り値が適合するpoll()とpeek()が解答の候補となります。どちらもキューの先頭要素への参照を返しますが、poll()が先頭要素を取り出すのに対し、peek()は参照だけで取り出しは行わないという点が異なります。

プログラム全体を見ると、他にキューから取り出す処理が存在しないため、ここで先頭要素が削除されなければ、行21では同じ盤面が繰り返し state に格納されてしまいます。これでは一向に探索処理が進みません。したがって、空欄イには取り出しを伴う「poll()」が当てはまります。

∴イ＝poll()

〔ウエオについて〕
空欄を含むif文は、新たな盤面 new_state を作成する際の条件となっています。

本文の動作説明に従うと、子ノードが表す盤面は、空白マスを上下左右のいずれかへ1マス移動することで作成されますが、この際、空白マスの場所によって移動（マス置換え）できる方向が限定されます。したがって、空白マスの移動先が盤面内に収まっていることを確認する処理が必要です。『盤面内で収まっている』をプログラム上で表現すると、行番号・列番号がともに「1以上かつ board_size 以下」となります。行23～26のif文ではこの境界判定を行っています。

BoardStateの説明（図4）では、盤面における空白マスの位置をメンバ変数 space で保持していることが示されています。space は配列で、[1]が行番号、[2]が列番号です。また、プログラム中では空白マスの移動先の4パターンを保持する変数として、配列 direction が定義されています。行4の説明より、[1]に行番号の増減、[2]に列番号の増減が入っています。この2つのデータを利用すれば境界判定を行うことができます。現在注目している移動パターンは direction[i] で参照できるため、4つある移動パターンの判定を一般化した条件式を考えると、次の4つに整理されます。

• space[1] + direction[i][1] が 1 以上（上方向）
• space[1] + direction[i][1] が board_size 以下（下方向）
• space[2] + direction[i][2] が 1 以上（左方向）
• space[2] + direction[i][2] が board_size 以下（右方向）

したがって、空欄ウには「direction[i][1]」、空欄エには「board_size」、空欄オには「direction[i][2]」がそれぞれ当てはまります。

なお、行27～32行目では、現在探索中の盤面のコピーを new_state に生成（行27）し、空白マスの位置更新（行28、29）、空白マスと移動先マスの要素を入れ替える（行30～32）ことで、子ノードの盤面を作成しています。

∴ウ＝direction[i][1]
　エ＝board_size
　オ＝direction[i][2]

〔カについて〕
空欄を含むif文がtrueの場合には、関数 printResult により開始時点から盤面の遷移、駒の移動回数を出力され、プログラムは終了しています。本文中の記述と照合すると、これはゴールノードに至った場合の処理であることがわかります。

ゴールノードに至ったかどうかは、表2の関数 checkGoal(b, g) で判定することができます。引数bには「評価対象の盤面」、引数gには「ゴールの盤面配列」を渡します。「評価対象の盤面」には今生成した子ノードの盤面（本文中の「移動できる駒ごとにその駒を移動した後のノード」）である new_state.board を、「ゴールの盤面配列」には行3の createGoal(N) によって生成され保持している goal_board を設定すればよいです。

∴カ＝checkGoal(new_state.board，goal_board)

〔キクについて〕
.に続く字句なので、ここにはメソッドかプロパティが入ります。戻り値がなく、すでに両変数は行16、18にてコンストラクタで生成済です。したがって、消去法で add メソッドが入ると判断できます。

本文中ではこの箇所に該当する記述として以下の2つがあります。

• 子ノードが表す盤面が既に探索したノード(探索済みノード)と同じであれば，この子ノードは終端ノードとして，以降の探索は行わない
• 子ノードがゴールノードと同じであれば，最小解が見つかったと判断して探索を終了

図7の該当箇所を読むと、新しい状態 new_state を生成した直後にゴール判定を行い，ゴールでなければcheckSameBoard(new_state.board, check_list)で探索済と同一の盤面かを確かめています。この判定がfalseなら本文中の「終端ノードではない」に当たるので、この new_state は以降の探索に回すため"探索待ちリスト"に追加します。また、その盤面はすでに探索対象となったことをマークするため、"探索済みリスト"にも登録する必要があります。これが行38、39で行う処理の位置づけです。

空欄に入るメソッド名はいずれも add ですが、クラス Queue の引数 st はBoardState型、クラス List の引数 b は盤面を表す整数配列と異なっています。このため適切な引数は以下のようになります。

• explore_queue.add() ⇒ BoardState型の変数 new_state
• check_list.add() ⇒ そのメンバ変数である new_state.board

したがって、空欄キは「add(new_state)」、空欄クには「add(new_state.board)」が当てはまります。

∴キ＝add(new_state)
　ク＝add(new_state.board)

〔アについて〕
whileループを抜けた後は、「ゴールの盤面に至る駒の移動方法がない旨のメッセージを出力」してプログラムは終了します。つまり、空欄には探索継続か終了かを判定する条件が入ります。

whileループでは、explore_queue から要素を取り出し、それを基に新たな盤面を生成し、それが終端ノードでなければ explore_queue に追加するという処理を繰り返しています。終端ノードは explore_queue への追加は行われないため、探索が終盤に進むと explore_queue の要素は減っていき、やがて explore_queue は空になります。これが本文中でいう「全てのリーフノードが終端ノードとなった場合」に該当します。

逆にまだ探索対象が存在するうちは、whileループを継続する必要があります。探索対象が存在するかどうかは、クラス Queue の isEmpty() を使って調べられ、isEmpty() がfalse（＝空でない）であれば探索を続け、true（＝空）になったらwhileループを抜けることになります。したがって、空欄アには「explore_queue.isEmpty()」が当てはまります。

幅優先探索では「探索候補をキューに入れ、キューが空でない間取り出して展開する」という反復が基本となることを覚えておきましょう。

∴ア＝explore_queue.isEmpty()