テーマ：パズルの解答を求めるプログラム
目次
問3 パズルの解答を求めるプログラムに関する次の記述を読んで、設問1～3に答えよ。
太線で3×3の枠に区切られた9×9のマスから成る正方形の盤面に、1～9の数字を入れるパズルの解答を求めるプログラムを考える。このパズルは、図1に示すように幾つかのマスに数字が入れられている状態から、数字の入っていない各マスに、1～9のうちのどれか一つの数字を入れていく。このとき、盤面の横1行、縦1列、及び太線で囲まれた3×3の枠内の全てにおいて、1〜9 の数字が一つずつ入ることが、このパズルのルールである。パズルの問題例を図1に、図1の解答を図2に示す。
このパズルを解くための方針を次に示す。
方針：数字が入っていない空白のマスに、1〜9の数字を入れて、パズルのルールにのっとって全部のマスを埋めることができる解答を探索する。
この方針に沿ってパズルを解く手順を考える。
〔パズルを解く手順〕
(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の添字を表す。
〔ルールのチェック方法〕
パズルのルールにのっとっているかどうかのチェックでは、数字を入れたマスが含まれる横1行の左端のマス、縦1列の上端のマス、3×3の枠内の左上端のマスを特定し、行、列、枠内のマスに既に格納されている数字と、入れた数字がそれぞれ重複していないことを確認する。このチェックを”重複チェック”という。
〔解法のプログラム〕
プログラムで使用する配列、関数、変数及び定数の一部を表1に示す。なお、表1の配列及び変数は大域変数とする。
解法のプログラムのメインプログラムを図4に、関数solveのプログラムを図5に、重複チェックを行うプログラムの一部を図6に示す。
〔プログラムの改善〕
解法のプログラムは深さ優先探索であり、探索の範囲が広くなるほど、再帰呼出しの回数が指数関数的に増加し、重複チェックの実行回数も増加する。
そこで、重複チェックの実行回数を少なくするために、各マスに入れることができる数字を保持するためのデータ構造 Zを考える。データ構造 Zは盤面のマスの数×9の要素をもち、添字xは0から、添字nは1から始まる2次元配列とする。Z[x][n]は、ゲームのルールにのっとってboard[x]に数字nを入れることができる場合は要素に1を、できない場合は要素に0を格納する。データ構造Zの初期化処理と更新処理を表2のように定義した。
なお、データ構造Zは大域変数として導入する。
〔パズルを解く手順〕の(1)の前にデータ構造Zの初期化処理を追加し、〔パズルを解く手順〕の(2)～(5)を次の(2)～(4)のように変更した。
(2) 空白のマスを見つける。
(3) データ構造Zを参照し、(2)で見つけた空白のマスに入れることができる数字のリストを取得し、リストの数字を順番に入れる。
(3-1) 入れる数字がある場合、①処理Aを行った後、マスに数字を入れる。その後、データ構造Zの更新処理を行い、(2)に進んで次の空白のマスを見つける。
(3-2) 入れる数字がない場合、マスを空白に戻し、②処理Bを行った後、一つ前に数字を入れたマスに戻り、戻ったマスで取得したリストの次の数字から再開する。
(4) 最後のマスまで数字が入り、空白のマスがなくなったら、それが解答となる。
設問1 図5中のア～エに入れる適切な字句を答えよ。
解答
ア：board[x]が0でない
イ：x + 1
ウ：check_ok(n, x)がtrueと等しい
エ：0
解説
アは『対象のマスが空白でない場合』とある。
対象のマス：board配列の添字番目
空白でない：0でない
イは『次の探索』とある。
現在の添字の次ということで「x＋1」。
ウは行コメントがないがアのelseに当たる部分なので「対象のマスが空白の場合」の処理。さらに、次の行でマスに数字を格納しているので、縦横枠内の重複チェックがOKかを判定しているif文になる。
エは『再起から戻った場合のマスの初期化』とあるので、マスの初期化＝マスを空白にするとなるので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)
解説
オは『行の左端のマスを示す添字を求める』とあるので、左端のマスの添字になる0, 9, 18, 27～が求められる式を当てはめてあげれば良い。行数の9の倍数ですね。行数を求めるには添字を横のマス数である9で割れば出ます。9進数と考えればいいかと。
カは行コメントありませんが、次の行でfalseを返しているので、重複があるかチェックしているif文になります。横方向にチェックするのでboard配列の添字は1ずつズレるrow_top+iです。
キは『列の上端のマスを示す添字を求める』とあるので、上端のマスの添字になる0～8が求められる式を当てはめてあげれば良い。どんな数字が来ても0～8の範囲の答えとなるので、9で割った余りを求めれば良いことになります。
クは行コメントありませんが、次の行でfalseを返しているので、重複があるかチェックしているif文になります。縦方向にチェックするのでboard配列の添字は9ずつズレるcolumn_top+(9*i)です。
ケは『枠内の左上端のマスを示す添字を求める』とあるので、枠内の左上端のマスの添字になる0,3,6,27,30,33～が求められる式を当てはめてあげれば良い。式全体は「x – ケ – mod(x, 3)」となっているので最後の「mod(x, 3)」で0～2の値が取れることが分かる。あとは、枠の上段の値が取れれば良いので、「mod(div(x, 9) * 9, 27)」で枠左端上の添字を27で割った余りで現在の添字から上段までの差分を取ってます。
設問3 〔プログラムの改善〕について、下線①の処理A及び下線②の処理Bの内容を、”データ構造Z”という字句を含めて、それぞれ20字以内で述べよ。
解答
処理A：データ構造Zを退避する
処理B：退避したデータ構造Zを取り出す
解説
(3-2)で1マス戻っていることから、データ構造Zも1つ前に戻す必要がある。
コメントを残す