パズルの解答を求めるプログラムに関する次の記述を読んで，設問1〜3に答えよ。
太線で3×3の枠に区切られた9×9のマスから成る正方形の盤面に，1〜9の数字を入れるパズルの解答を求めるプログラムを考える。このパズルは，図1に示すように幾つかのマスに数字が入れられている状態から，数字の入っていない各マスに，1〜9のうちのどれか一つの数字を入れていく。このとき，盤面の横1行，縦1列，及び太線で囲まれた3×3の枠内の全てにおいて，1〜9の数字が一つずつ入ることが，このパズルのルールである。パズルの問題例を図1に，図1の解答を図2に示す。
図1 問題例
図2 図1の解答
このパズルを解くための方針を次に示す。
この方針に沿ってパズルを解く手順を考える。
〔パズルを解く手順〕
（1）盤面の左上端から探索を開始する。マスは左端から順に右方向に探索し，右端に達したら一行下がり，左端から順に探索する。
（2）空白のマスを見つける。
（3）（2）で見つけた空白のマスに，1〜9の数字を順番に入れる。
（4）数字を入れたときに，その状態がパズルのルールにのっとっているかどうかをチェックする。
（4-1）ルールにのっとっている場合は，（2）に進んで次の空白のマスを見つける。
（4-2）ルールにのっとっていない場合は，（3）に戻って次の数字を入れる。このとき，入れる数字がない場合には，マスを空白に戻して一つ前に数字を入れたマスに戻り，（3）から再開する。
（5）最後のマスまで数字が入り，空白のマスがなくなったら，それが解答となる。
〔盤面の表現〕
この手順をプログラムに実装するために，9×9の盤面を次のデータ構造で表現することにした。
・9×9の盤面を81個の要素をもつ1次元配列boardで表現する。添字は0から始まる。各要素にはマスに入れられた数字が格納され，空白の場合は0を格納する。
配列boardによる盤面の表現を図3に示す。ここで括弧内の数字は配列boardの添字を表す。
図3 配列boardによる盤面の表現
パズルのルールにのっとっているかどうかのチェックでは，数字を入れたマスが含まれる横1行の左端のマス，縦1列の上端のマス，3×3の枠内の左上端のマスを特定し，行，列，枠内のマスに既に格納されている数字と，入れた数字がそれぞれ重複していないことを確認する。このチェックを“重複チェック”という。
〔解法のプログラム〕
プログラムで使用する配列，関数，変数及び定数の一部を表1に示す。なお，表1の配列及び変数は大域変数とする。
| 名称 | 種類 | 内容 |
| board | 配列 | 盤面の情報を格納する配列。 初期化時には問題に合わせて要素に数字が設定される。 |
| solve(x) | 関数 | パズルを解くための手順を実行する関数。 盤面を表すboardの添字xを引数とする。 |
| row_ok(n,x) | 関数 | 横1行の重複チェックを行う関数。チェック対象の数字n，チェック対象のマスを示す添字xを引数とする。 数字の重複がない場合はtrue，重複がある場合はfalseを返す。 |
| column_ok(n,x) | 関数 | 縦1列の重複チェックを行う関数。チェック対象の数字n，チェック対象のマスを示す添字xを引数とする。 数字の重複がない場合はtrue，重複がある場合はfalseを返す。 |
| frame_ok(n,x) | 関数 | 3×3の枠内の重複チェックを行う関数。チェック対象の数字n，チェック対象のマスを示す添字xを引数とする。 数字の重複がない場合はtrue，重複がある場合はfalseを返す。 |
| check_ok(n,x) | 関数 | row_ok，column_ok，frame_okを呼び出し，全ての重複チェックを実行する関数。チェック対象の数字n，チェック対象のマスを示す添字xを引数とする。 全てのチェックで数字の重複がない場合はtrue，一つ以上のチェックで数字の重複がある場合はfalseを返す。 |
| div(n,m) | 関数 | 整数nを整数mで割った商を求める関数。 |
| mod(n,m) | 関数 | 整数nを整数mで割った剰余を求める関数。 |
| print_board() | 関数 | board[]の内容を9×9の形に出力する関数。 |
| row_top | 変数 | 数字を入れようとするマスが含まれる横1行の左端のマスを示す添字を格納する変数。 |
| column_top | 変数 | 数字を入れようとするマスが含まれる縦1列の上端のマスを示す添字を格納する変数。 |
| frame_top | 変数 | 数字を入れようとするマスが含まれる3×3の枠内の左上端のマスを示す添字を格納する変数。 |
| MAX_BOARD | 定数 | 盤面に含まれるマスの数を表す定数で81。 |
解法のプログラムのメインプログラムを図4に，関数solveのプログラムを図5に，重複チェックを行うプログラムの一部を図6に示す。
図4 メインプログラム
図5 関数solveのプログラム
図6 重複チェックを行うプログラムの一部
〔プログラムの改善〕
解法のプログラムは深さ優先探索であり，探索の範囲が広くなるほど，再帰呼出しの回数が指数関数的に増加し，重複チェックの実行回数も増加する。
そこで，重複チェックの実行回数を少なくするために，各マスに入れることができる数字を保持するためのデータ構造Zを考える。データ構造Zは盤面のマスの数×9の要素をもち，添字xは0から，添字nは1から始まる2次元配列とする。Z[x][n]は，ゲームのルールにのっとってboard[x]に数字nを入れることができる場合は要素に1を，できない場合は要素に0を格納する。データ構造Zの初期化処理と更新処理を表2のように定義した。
なお，データ構造Zは大域変数として導入する。
| 処理の名称 | 処理の内容 |
| 初期化処理 | 初期化時の盤面に対し，個々の空白のマスについて1〜9の数字を入れた場合の重複チェックを行う。 重複チェックの結果によって，初期化時の盤面の状態で個々の空白のマスに入れることができない数字は，データ構造Zの該当する数字の要素に0を設定する。それ以外の要素には1を設定する。 |
| 更新処理 | 空白のマスに数字を入れたとき，そのマスが含まれる横1行，縦1列，3×3の枠内の全てのマスを対象に，データ構造Zの該当する数字の要素を0に更新する。 |
〔パズルを解く手順〕の（1）の前にデータ構造Zの初期化処理を追加し，〔パズルを解く手順〕の（2）〜（5）を次の（2）〜（4）のように変更した。
（2）空白のマスを見つける。
（3）データ構造7を参照し，（2）で見つけた空白のマスに入れることができる数字のリストを取得し，リストの数字を順番に入れる。
（3-1）入れる数字がある場合，①処理Aを行った後，マスに数字を入れる。その後，データ構造Zの更新処理を行い，（2）に進んで次の空白のマスを見つける。
（3-2）入れる数字がない場合，マスを空白に戻し，②処理Bを行った後，一つ前に数字を入れたマスに戻り，戻ったマスで取得したリストの次の数字から再開する。
（4）最後のマスまで数字が入り，空白のマスがなくなったら，それが解答となる。
出典：令和4年度春期 問3
設問1 図5中の ア 〜 エ に入れる適切な字句を答えよ。
解答・解説
解答例
ア：board[x]が0でない
イ：x + 1
ウ：check_ok(n, x)がtrueと等しい
エ：0
解説
設問2 図6中の オ 〜 ケ に入れる適切な字句を答えよ。
解答・解説
解答例
オ：div(x, 9) * 9
カ：board[row_top + i]がnと等しい
キ：mod(x, 9)
ク：board[column_top + 9 * i]がnと等しい
ケ：mod(div(x, 9) * 9, 27)
解説
設問3 〔プログラムの改善〕について，下線①の処理A及び下線②の処理Bの内容を，“データ構造”という字句を含めて，それぞれ20字以内で述べよ。
解答・解説
解答例
処理A：データ構造Zを退避する
処理B：退避したデータ構造Zを取り出す
解説
IPA公開情報
出題趣旨
深さ優先探索は，全探索アルゴリズムの一種であり，グラフ及びグラフと同一視できるようなデータを探索 する際に広く利用されている。
本問では，パズルの解法を求める処理を題材に，盤面を 1 次元配列を用いて表し，深さ優先探索のアルゴリズムを再帰処理で表現することで，それを実装したプログラム及びデータ構造の特性に関する理解を問う。
採点講評
問 3 では，パズルの解法を求める処理を題材に，その解法を，深さ優先探索，再帰処理，1 次元配列による盤面の表現を用いて実装するためのアルゴリズム，プログラム及びデータ構造の特性について出題した。全体として正答率は平均的であった。
設問 2 のケは，正答率が低かった。添字 x，3×3 の枠内の先頭の数字，mod(x, 3)の組合せを列挙することで，ケが取るべき値を求めることができる。剰余や商の性質を理解し，着実に計算することで正答を導き出し てほしい。
設問 3 は，正答率が低かった。下線②の“処理 B”では，“マスを空白に戻す”のに合わせて，データ構造 Z も数字を入れる前の状態に戻す必要がある。これを，Z の内容を実際に更新して行う代わりに，大域変数として導入した Z を，下線①の“処理 A”で一時退避しておき，“処理 B”ではそれを取り出すことによって実現できることを理解してほしい。
