2022年 春期 応用情報技術者試験 問3

パズルの解答を求めるプログラム

問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に示す。

function main()
  board[]を初期化する    //問題を盤面に設定する
  solve(0)             //盤面の左上端のマスを示す添字を引数として関数solveを呼び出す
endfunction

function solve(x)
  if (x >= MAX_BOARD-1 より大きい)
    print_board()                           //解答を出力する
    exit()                                  //メインプログラムの処理を終了する
  else
    if (ア)                      //対象のマスが空白でない場合
      solve (イ)                    //次の探索
    else
      for (n を 1 から 9 まで 1 ずつ増やす)        //1～9の数字を順にマスに入れる
        if (ウ)
          board[x] ← n
          solve (イ)                //次の探索
          board[x] ← エ              //再帰から戻った場合のマスの初期化
        endif
      endfor
    endif
  endif
endfunction

function row_ok(n, x)                       //横1行の重複チェック
  row_top ← オ                     //行の左端のマスを示す添字を求める
  for (i を 0 から 8 まで 1 ずつ増やす)
    if (カ)
      return false
    endif
  endfor
  return true
endfunction
function column_ok(n, x)                    //縦1列の重複チェック
column_top ← キ                  //列の上端のマスを示す添字を求める
for (i を 0 から 8 まで 1 ずつ増やす)
if (ク)
return false
endif
endfor
return true
endfunction
function frame_ok(n, x)                     //3×3の枠内の重複チェック
frame_top ← x - ケ - mod(x, 3)  //枠内の左上端のマスを示す添字を求める
for (i を 0 から 2 まで 1 ずつ増やす)
for (j を 0 から 2 まで 1 ずつ増やす)
if (board[frame_top + 9 * i + j]が n と等しい)
return false
endif
endfor
endfor
return true
endfunction

[プログラムの改善]

解法のプログラムは深さ優先探索であり、探索の範囲が広くなるほど、再帰呼び出しの回数が指数関数的に増加し、重複チェックの実行回数も増加する。

そこで、重複チェックの実行回数を少なくするために、各マスに入れることができる数字を保持するためのデータ構造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)　最後のマスまで数字が入り、空白のマスがなくなったら、それが解答となる。