AP過去問令和7年度春期午後問3 プログラミング

AP過去問_令和7年度春期_午後_問4_システムアーキテクチャの同じ回の次の問題へ移動。

AP過去問_令和6年度秋期_午後_問3_プログラミングの前の回の同じカテゴリの問題へ移動。

令和7年度春期午後問3 プログラミング(AIプロンプト向け)

■スライドパズルを解くプログラムに関する次の記述を読んで、設問に答えよ。

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

<div><div class="table-container"><div class="table-header"><span class="table-title">表1 スライドパズルのルール</span><span class="table-unit">単位億円</span></div> <table border="0" width="100%" style="border-collapse: collapse;border-style: solid"> <tr> <td align="center" style="border: 2px solid; width: 5em;">用語</td> <td align="center" style="border: 2px solid;">説明</td> </tr> <tr> <td align="center" style="border: 2px solid;">盤面</td> <td align="center" style="border: 2px solid;">正方形の面に、1から順に1ずつ大きくなる数字の書かれた駒が配置されている。1か所だけ駒の置かれていない空白のマス(以下、空白マスという)がある。</td> </tr> <tr> <td align="center" style="border: 2px solid;">開始時点の盤面</td> <td align="center" style="border: 2px solid;">開始時点では、駒と空白マスはランダムに配置されている。</td> </tr> <tr> <td align="center" style="border: 2px solid;">ゴールの盤面</td> <td align="center" style="border: 2px solid;">盤面左上に数字が1の駒があり、右の駒の数字は1ずっ増えていき、その行の右端の駒に書かれた数字より1 大きい数字が、次の行の左端の駒の数字となる。盤面右下のマスが空白マスとなる。</td> </tr> <tr> <td align="center" style="border: 2px solid;">駒の移動</td> <td align="center" style="border: 2px solid;">駒の上下左右いずれかに空白マスがある場合、駒を空白マスに移動することができる。駒が移動した場合、駒が置かれていたマスが空白マスになる。駒を空白マスに移動させて盤面を変化させ、ゴールの盤面と同じにすることを目指す。</td> </tr> </table> </div> </div>

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

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

開始時点の盤面

縦方向に1行目、2行目、3行目

開始時点の盤面

8	6	7
2	5	4
3	空白マス	1

　ゴールの盤面

1	2	3
4	5	6
7	8	空白マス

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

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

〔一辺がNマスのスライドパズルの最小解をを用いて求る方法〕　幅優先探索を行ったときの、スライドパズルの盤面の遷移を、グラフで表現する。開始時点の盤面をルートノード、ある時点の盤面をノード、駒の移動に伴う盤面の遷移をエッジで表現する。また、ゴールの盤面をゴールノードとして定義する。

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

　探索対象のノードに対して、移動できる駒ごとにその駒を移動した後のノードを作成して、探索対象のノードの子ノードとし、探索対象のノードは探索済みとなる。このとき、子ノードが表す盤面が既に探索したノード(以下、探索済みノードという)と同じであれば、この子ノードは終端ノードとして、以降の探索は行わない。また、子ノードがゴールノードと同じであれば、最小解が見つかったと判断して探索を終了する。

〔Nが3の場合の例〕

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

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

ルートノード

8	6	7
2	5	4
3	空白マス	1

1回目としてルートノードの子ノード①～③がある。

子ノード①

8	6	7
2	5	4
空白マス	3	1

子ノード②

省略	省略	省略
省略	省略	省略
省略	省略	省略

子ノード③

8	6	7
2	5	4
3	1	空白マス

2回目として子ノード①の子ノード④、⑤がある。2回目として子ノード②の子ノード⑥、⑦、⑧、⑨がある。2回目として子ノード③の子ノード⑩、⑪がある。⑤、⑥、⑩は終端ノード

子ノード④

8	6	7
空白マス	5	4
2	3	1

子ノード⑤

8	6	7
2	5	4
3	空白マス	1

子ノード⑥

8	6	7
2	5	4
3	空白マス	1

子ノード⑦

8	6	7
空白マス	2	4
3	5	1

子ノード⑧

8	空白マス	7
2	6	4
3	5	1

子ノード⑨

8	6	7
2	4	空白マス
3	5	1

子ノード⑩

8	6	7
2	5	4
3	空白マス	1

子ノード⑪

8	6	7
2	5	空白マス
3	1	4

以降の子ノードは省略。

n回目として、いづれかの子ノードの子ノード⑫をゴールノードとして

子ノード⑫

1	2	3
4	5	6
7	8	空白マス

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

(1) 1回目の駒の移動では、ルートノードを探索対象のノードとする。ここでは、移動できる駒が三つあるので、ルートノードから深さが1となる①～③の子ノードを作成し、ルートノードは探索済みノードとなる。ここで、①～③の子ノードに対して、ゴールノードの判定及び終端ノードの判定を行う。

(2) 次に、作成した子ノードで終端ノード以外のノードをそれぞれ探索対象のノードとし、駒の移動にあわせて子ノードを作成する。図2では、①～③のノードから④～⑪の子ノードを作成し、①～③は探索済みノードとなる。ここで、④～⑪の子ノードに対して、ゴールノードの判定及び終端ノードの判定を行う。図2では、盤面が探索済みノードと一致する⑤、⑥及び⑩は終端ノードとなり、以降の探索は行わない。

(3) 以降、(2)で作成したノードの子ノードの作成と、ゴールノードの判定及び終端ノードの判定を繰り返す。図2の⑫は、n回目の移動でゴールノードに至ったことを示している。なお、全てのリーフノードが終端ノードと判定された場合、ゴールの盤面に至る駒の移動方法がないことを意味しているので、その旨のメッセージを出力して探索を終了する。

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

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

盤面を次の例に示すように配列を用いて表現する。

(1) 盤面の行ごとに並ぶ駒の数字を整数型の配列で表す。

横方向に1列目、2列目、3列目

配列表現サンプル