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

AP 過去問題 午後に戻る。

AP過去問_令和7年度春期_午後_問2_経営戦略の同じ回の前の問題へ移動。

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行目

開始時点の盤面

<table id="開始時点の盤面">

<tr>

 <td>8</td><td>6</td><td>7</td>

</tr>

<tr>

 <td>2</td><td>5</td><td>4</td>

</tr>

<tr>

 <td>3</td><td>空白マス</td><td>1</td>

</tr>

</table>

　ゴールの盤面

<table id="ゴールの盤面">

<tr>

 <td>1</td><td>2</td><td>3</td>

</tr>

<tr>

 <td>4</td><td>5</td><td>6</td>

</tr>

<tr>

 <td>7</td><td>8</td><td>空白マス</td>

</tr>

</table>

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

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

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

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

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

〔Nが3の場合の例〕

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

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

ルートノード

<table id="ルートノード">

<tr>

  <td>8</td><td>6</td><td>7</td>

</tr>

<tr>

  <td>2</td><td>5</td><td>4</td>

</tr>

<tr>

  <td>3</td><td>空白マス</td><td>1</td>

</tr>

</table>

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

子ノード①

<table id="子ノード①">

<tr>

  <td>8</td><td>6</td><td>7</td>

</tr>

<tr>

  <td>2</td><td>5</td><td>4</td>

</tr>

<tr>

  <td>空白マス</td><td>3</td><td>1</td>

</tr>

</table>

子ノード②

<table id="子ノード②">

<tr>

  <td>省略</td><td>省略</td><td>省略</td>

</tr>

<tr>

  <td>省略</td><td>省略</td><td>省略</td>

</tr>

<tr>

  <td>省略</td><td>省略</td><td>省略</td>

</tr>

</table>

子ノード③

<table id="子ノード③">

<tr>

  <td>8</td><td>6</td><td>7</td>

</tr>

<tr>

  <td>2</td><td>5</td><td>4</td>

</tr>

<tr>

  <td>3</td><td>1</td><td>空白マス</td>

</tr>

</table>

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

子ノード④

<table id="子ノード④">

<tr>

  <td>8</td><td>6</td><td>7</td>

</tr>

<tr>

  <td>空白マス</td><td>5</td><td>4</td>

</tr>

<tr>

  <td>2</td><td>3</td><td>1</td>

</tr>

</table>

子ノード⑤

<table id="子ノード⑤">

<tr>

  <td>8</td><td>6</td><td>7</td>

</tr>

<tr>

  <td>2</td><td>5</td><td>4</td>

</tr>

<tr>

  <td>3</td><td>空白マス</td><td>1</td>

</tr>

</table>

子ノード⑥

<table id="子ノード⑥">

<tr>

  <td>8</td><td>6</td><td>7</td>

</tr>

<tr>

  <td>2</td><td>5</td><td>4</td>

</tr>

<tr>

  <td>3</td><td>空白マス</td><td>1</td>

</tr>

</table>

子ノード⑦

<table id="子ノード⑦">

<tr>

  <td>8</td><td>6</td><td>7</td>

</tr>

<tr>

  <td>空白マス</td><td>2</td><td>4</td>

</tr>

<tr>

  <td>3</td><td>5</td><td>1</td>

</tr>

</table>

子ノード⑧

<table id="子ノード⑧">

<tr>

  <td>8</td><td>空白マス</td><td>7</td>

</tr>

<tr>

  <td>2</td><td>6</td><td>4</td>

</tr>

<tr>

  <td>3</td><td>5</td><td>1</td>

</tr>

</table>

子ノード⑨

<table id="子ノード⑨">

<tr>

  <td>8</td><td>6</td><td>7</td>

</tr>

<tr>

  <td>2</td><td>4</td><td>空白マス</td>

</tr>

<tr>

  <td>3</td><td>5</td><td>1</td>

</tr>

</table>

子ノード⑩

<table id="子ノード⑩">

<tr>

  <td>8</td><td>6</td><td>7</td>

</tr>

<tr>

  <td>2</td><td>5</td><td>4</td>

</tr>

<tr>

  <td>3</td><td>空白マス</td><td>1</td>

</tr>

</table>

子ノード⑪

<table id="子ノード⑪">

<tr>

  <td>8</td><td>6</td><td>7</td>

</tr>

<tr>

  <td>2</td><td>5</td><td>空白マス</td>

</tr>

<tr>

  <td>3</td><td>1</td><td>4</td>

</tr>

</table>

以降の子ノードは省略。

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

子ノード⑫

<table id="子ノード⑫">

<tr>

  <td>1</td><td>2</td><td>3</td>

</tr>

<tr>

  <td>4</td><td>5</td><td>6</td>

</tr>

<tr>

  <td>7</td><td>8</td><td>空白マス</td>

</tr>

</table>

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

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

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

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

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

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

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

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

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

配列表現サンプル

<table id="配列表現サンプル">

<tr>

  <td>8</td><td>6</td><td>7</td>

</tr>

<tr>

  <td>2</td><td>5</td><td>4</td>

</tr>

<tr>

  <td>3</td><td>空白マス</td><td>1</td>

</tr>

</table>

1行目を表す配列 {8, 6, 7}、2行目を表す配列 {2, 5, 4}、3行目を表す配列 {3, 9, 1}

(2) (1)で行ごとに定義した配列を整数型配列の配列(以下、盤面配列という)で表す。

{{8, 6, 7}, {2, 5, 4}, {3, 9, 1}}

(3) 1行目の3列目の駒の数字は、盤面配列名をboardとするとboard[1][3]として参照する。

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

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

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

　

令和7年度春期 午後 問3 プログラミング(問題原文)

■

　

回答・解説

　

AP過去問_令和7年度春期_午後_問2_経営戦略の同じ回の前の問題へ移動。

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

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

AP 過去問題 午後に戻る。