問題プレビューID: dc1ab8da応用情報技術者試験 2022年(令和4年度)春期 午後

問 3
応用情報技術者試験 2022年(令和4年度)春期 午後

パズルの解答を求めるプログラムに関する次の記述を読んで,設問 1~3 に答えよ。

太線で 3×3 の枠に区切られた 9×9 のマスから成る正方形の盤面に,1~9 の数字を入れるパズルの解答を求めるプログラムを考える。このパズルは,図1に示すように幾つかのマスに数字が入れられている状態から,数字の入っていない各マスに,1~9 のうちのどれか一つの数字を入れていく。このとき,盤面の横1行,縦1列,及び太線で囲まれた 3×3 の枠内の全てにおいて,1~9 の数字が一つずつ入ることが,このパズルのルールである。パズルの問題例を図1に,図1の解答を図2に示す。

図 1 問題例

2197
423
5829
9672
6354
7491
7693
964
416

図 2 図1の解答

281493765
946257381
573168429
495671238
618325974
327849516
762984153
159736842
834512697

このパズルを解くための方針を次に示す。

方針:数字が入っていない空白のマスに,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 の添字を表す。

図 3 配列 board による盤面の表現

[0][1][2][3][4][5][6][7][8]
[9][10][11][12][13][14][15][16][17]
[18][19][20][21][22][23][24][25][26]
[27][28][29][30][31][32][33][34][35]
⋮⋮⋮⋮⋮⋮⋮⋮⋮
[72][73][74][75][76][77][78][79][80]

〔ルールのチェック方法〕

パズルのルールにのっとっているかどうかのチェックでは,数字を入れたマスが含まれる横1行の左端のマス,縦1列の上端のマス,3×3 の枠内の左上端のマスを特定し,行,列,枠内のマスに既に格納されている数字と,入れた数字がそれぞれ重複していないことを確認する。このチェックを"重複チェック"という。

〔解法のプログラム〕

プログラムで使用する配列,関数,変数及び定数の一部を表1に示す。なお,表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 メインプログラム

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

図 5 関数 solve のプログラム

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

図 6 重複チェックを行うプログラムの一部

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 は大域変数として導入する。

表 2 データ構造 Z の初期化処理と更新処理

処理の名称処理の内容
初期化処理初期化時の盤面に対し,個々の空白のマスについて 1~9 の数字を入れた場合の重複チェックを行う。重複チェックの結果によって,初期化時の盤面の状態で個々の空白のマスに入れることができない数字は,データ構造 Z の該当する数字の要素に 0 を設定する。それ以外の要素には 1 を設定する。
更新処理空白のマスに数字を入れたとき,そのマスが含まれる横1行,縦1列,3×3 の枠内の全てのマスを対象に,データ構造 Z の該当する数字の要素を 0 に更新する。

〔パズルを解く手順〕の(1)の前にデータ構造 Z の初期化処理を追加し,〔パズルを解く手順〕の(2)~(5)を次の(2)~(4)のように変更した。

(2) 空白のマスを見つける。

(3) データ構造 Z を参照し,(2)で見つけた空白のマスに入れることができる数字のリストを取得し,リストの数字を順番に入れる。

(3-1) 入れる数字がある場合,①処理Aを行った後,マスに数字を入れる。その後,データ構造 Z の更新処理を行い,(2)に進んで次の空白のマスを見つける。

(3-2) 入れる数字がない場合,マスを空白に戻し,②処理Bを行った後,一つ前に数字を入れたマスに戻り,戻ったマスで取得したリストの次の数字から再開する。

(4) 最後のマスまで数字が入り,空白のマスがなくなったら,それが解答となる。

設問1

図5中の[ア]~[エ]に入れる適切な字句を答えよ。

設問2

図6中の[オ]~[ケ]に入れる適切な字句を答えよ。

設問3

〔プログラムの改善〕について,下線①の処理A及び下線②の処理Bの内容を,"データ構造Z"という字句を含めて,それぞれ20字以内で述べよ。

模範解答

設問1 ア board[x]が 0 でない,イ x+1,ウ check_ok(n, x)が true と等しい,エ 0

設問2 オ 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 データ構造Zを退避する,処理B 退避したデータ構造Zを取り出す

解説

深さ優先探索によるパズルの解法を題材に,盤面を 1 次元配列で表し,再帰処理で実装したプログラム及びデータ構造の特性に関する理解を問う。

設問1では,関数 solve の空欄を問う。[ア]は対象のマスが空白でない場合の判定であり,board[x]が 0 でないことである。[イ]は次の探索であり,添字を一つ進めた x+1 を引数とする再帰呼出しである。[ウ]は数字を入れてよいかの判定であり,check_ok(n, x)が true と等しいことである。[エ]は再帰から戻った場合のマスの初期化であり,空白を表す 0 を格納する。

設問2では,重複チェックの空欄を問う。[オ]は行の左端のマスを示す添字であり,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では,データ構造 Z を用いた改善を問う。数字を入れる前にデータ構造Zを退避し(処理A),入れる数字がなくなって戻るときに退避したデータ構造Zを取り出す(処理B)ことで,探索のやり直しに対応する。

関連問題

本文が同じ・似ている問題を表示しています