応用情報技術者 2022年 春期 午後 問03

解答の論理構成

1. [ア] の判断基準
   • 盤面の配列について【問題文】には「各要素にはマスに入れられた数字が格納され、空白の場合は 0 を格納する。」とあります。
   • したがって “対象のマスが空白でない” とは board[x] に 0 以外の値が入っている場合であり、条件式は「board[x]が0でない」となります。
2. [イ] の添字計算
   • 探索順序は〔パズルを解く手順〕(1) にある通り「左端から順に右方向に探索し、右端に達したら一行下がり…」ですが、1次元配列で実装しているため右隣のマスはインデックスを1増やすだけで得られます。
   • よって次に処理すべきマスは x+1 です。
3. [ウ] の成立条件
   • 1～9 の数字を試す for ループの中では「数字を入れたときに、その状態がパズルのルールにのっとっているかどうかをチェックする。」とあり、チェック用関数は【表1】で示された check_ok(n, x) です。
   • true が返れば「ルールにのっとっている」と解釈し再帰に進むため、判定式は「check_ok(n, x)がtrueと等しい」。
4. [エ] の巻き戻し処理
   • 再帰から戻ったときには「マスを空白に戻して…」という 〔パズルを解く手順〕(4-2) の指示があります。空白は 0 で表現されるので board[x] ← 0 が必要です。

誤りやすいポイント

• 1 行 9 列を 1 次元配列で表す際、右端から次の行頭に移る計算（x + 1 ではなく (x+1) mod 9 など）と混同する。
• [ウ] で row_ok・column_ok・frame_ok を個別に呼び出してしまい、記述が長くなる。実際には check_ok(n, x) が包括している。
• 「空白に戻す」処理を忘れ、バックトラック時に盤面が汚れたままになる。

FAQ

解答の論理構成

1. 行の左端インデックス計算（[オ]）
   • 盤面は「9×9 の盤面を 81 個の要素をもつ 1 次元配列 board で表現する。添字は 0 から始まる。」という仕様です。
   • 1行は9マスなので、マス x が属する行の左端は
     div(x, 9)（行番号）×9＝div(x, 9)*9 となります。
   • よって [オ] は原文どおり「div(x, 9)*9」です。
2. 行内の重複判定式（[カ]）
   • 行の左端 row_top から8回ループし、対象値 n と同じ数字があれば重複と判定します。
   • したがって if 文の中身は
     board[row_top+i]がnと等しい で決まり、模範解答では「board[row_top+i]がnと等しい」。
3. 列の上端インデックス計算（[キ]）
   • 列は 9 行にまたがるため、列番号は mod(x, 9) で求められます。
   • よって [キ] は「mod(x, 9)」。
4. 列内の重複判定式（[ク]）
   • 列の上端 column_top から下方向へ9マスを調べます。
   • 配列位置は column_top + 9i なので if 条件は
     board[column_top+9i]がnと等しい となり、模範解答はこれをそのまま採用しています。
5. 3×3 枠の左上端オフセット（[ケ]）
   • 行方向については、行の左端 div(x, 9)*9 を3行区切り（27＝3×9）で見た余りが、その行が枠内で何行目かを示します。
     例：行 0～2 → 0, 9, 18、行 3～5 → 0, 9, 18 …
   • よって余り計算 mod(div(x, 9)*9, 27) を x から引けば、行方向で枠の最上段まで戻ることができます。
   • 枠の左上端は「x − 行方向オフセット − 列方向オフセット (mod(x, 3))」なので、[ケ] に当たる行方向オフセットは
     mod(div(x, 9)*9, 27) が最適です。

• 「div(x, 9)*9」
• 「board[row_top+i]がnと等しい」
• 「mod(x, 9)」
• 「board[column_top+9*i]がnと等しい」
• 「mod(div(x, 9)*9, 27)」
  がすべて論理的に導けます。

誤りやすいポイント

• 行頭を x - mod(x,9) としてしまい、列番号と混同する。
• 列上端を求める際に div(x,9) を使い、行と列を逆に認識するミス。
• 3×3 枠の計算で「27」を「9*9=81」と誤って設定し、枠の範囲が崩れる。
• if 条件の添字計算で i に 1 を足し忘れたり、引数 n と board の位置を逆に書く実装ミス。

FAQ

解答の論理構成

1. 問題文は、従来の深さ優先探索に対し「重複チェックの実行回数を少なくするために、各マスに入れることができる数字を保持するためのデータ構造 Z を考える」と述べています。この “データ構造 Z” は探索のたびに内容が書き換わります。
2. 新しい手順の説明では
   「(3-1) 入れる数字がある場合、①処理A を行った後、マスに数字を入れる。その後、データ構造 Z の更新処理を行い…」
   「(3-2) 入れる数字がない場合、マスを空白に戻し、②処理B を行った後、一つ前に数字を入れたマスに戻り…」
   と明記され、処理A は“数字を入れる前”、処理B は“数字を取り消した後”に呼ばれます。
3. 数字を試すたびに “データ構造 Z の更新処理” が走るため、バックトラック時には更新前の Z を取り戻す必要があります。
4. よって
   ・処理A＝更新前の “データ構造 Z” をどこかに保存する（退避）
   ・処理B＝保存していた “データ構造 Z” を元に戻す（復元）
   が唯一破綻なく探索木をたどる方法です。
5. 以上より模範解答どおり
   「処理A：データ構造Zを退避する」
   「処理B：退避したデータ構造Zを取り出す」
   が導かれます。

誤りやすいポイント

• 処理A／処理Bを「board の退避・復元」と勘違いする。board は再帰から戻る直前に board[x] ← 0 としてリセットされるので別途保存は不要です。
• 「データ構造 Z の更新処理＝処理A」と読み違える。処理A はあくまで更新“前”に呼び出される点に注意します。
• 「処理Bで再度更新処理を呼ぶ」と考える誤解。更新処理は数字を書き込むときだけ行うので、取り消し時は保存した Z を復元するだけで十分です。

FAQ