令和4年度 春期 応用情報技術者試験 午後 問3 深さ優先探索による数独解法プログラムの盤面走査とデータ構造改善

図1 問題例

図2 図1の解答

方針：数字が入っていない空白のマスに、1〜9の数字を入れて、パズルのルールにのっとって全部のマスを埋めることができる解答を探索する。

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

表1 プログラムで使用する配列，関数，変数及び定数の一部

図4 メインプログラム

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

図5 関数 solve のプログラム

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

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

function row_ok(n, x)         // 横 1 行の重複チェック
  row_top ← <span id="q3_blank_o" class="blank-label">オ</span>              // 行の左端のマスを示す添字を求める
  for (i を 0 から 8 まで 1 ずつ増やす)
    if ( <span id="q3_blank_ka" class="blank-label">カ</span> )
      return false
    endif
  endfor
  return true
endfunction

function column_ok(n, x)      // 縦 1 列の重複チェック
  column_top ← <span id="q3_blank_ki" class="blank-label">キ</span>           // 列の上端のマスを示す添字を求める
  for (i を 0 から 8 まで 1 ずつ増やす)
    if ( <span id="q3_blank_ku" class="blank-label">ク</span> )
      return false
    endif
  endfor
  return true
endfunction

function frame_ok(n, x)       // 3×3 の枠内の重複チェック
  frame_top ← x - <span id="q3_blank_ke" class="blank-label">ケ</span> - 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

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