応用情報技術者 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. [オ]（row_topの式）

• row_topの説明に「数字を入れようとするマスが含まれる横1行の左端のマスを示す添字を格納する変数」とあります。行番号を $r$ とすると $r=div(x,9)$ です。行の先頭添字はその行番号に9を掛けた値なので、row_topは $r\times 9$ を表します。したがって [オ] = div(x, 9)*9 例：$x=10$ のとき $div(10,9)=1$ なので行先頭は $1\times 9=9$ であり、これは添字9が正しい行先頭です。

1. 図6の行チェック内の条件（forループ中の判定、力）

• for (iを0から8まで) で行内の9マスを順に参照するので、参照添字はrow_top + iです。これらのマスの値が既に入れようとする数字 $n$ と等しいかを調べればよく、条件は 力 = board[row_top+i]がnと等しい となります。

1. [キ]（column_topの式）

• column_topの説明に「数字を入れようとするマスが含まれる縦1列の上端のマスを示す添字」とあるので、列番号を $c$ とすると $c=mod(x,9)$ です。列の上端添字はその列番号そのものなので [キ] = mod(x, 9) 例：$x=19$ のとき $mod(19,9)=1$ であり、列上端は添字1（各行の同じ列の最上行）です。

1. 列チェック内の条件（forループ中の判定、ク）

• 列方向に1行下がると添字は $+9$ されるため、列内を順に参照する添字はcolumn_top + 9*iです。これらが $n$ と等しいかを判定する条件は ク = board[column_top+9*i]がnと等しい となります。

1. [ケ]（frame_topを求める式の中の項）

• 図6 に frame_top を求める式として frame_top ← x − ケ − mod(x, 3) とあるため、[ケ] は行方向のブロック内オフセットに関係する式であることが分かります。ここで行番号を $r=div(x,9)$、列番号を $c=mod(x,9)$ と置きます。行の先頭添字は $r\times 9$ です。3×3ブロックは「縦に3行、横に3列」から成るため、行方向に3行下がると添字は $3\times 9=27$ 増えます。したがって $r\times 9$ を $27$ で剰余を取ると、その行が属する「3行ブロック内での行先頭からのオフセット」を $0,9,18$ のいずれかで得られます。r の値ごとの具体例を列挙します（分かりやすさのため）：
• $r=0$ → $r\times 9=0$ → $mod(0,27)=0$
• $r=1$ → $9$ → $mod(9,27)=9$
• $r=2$ → $18$ → $mod(18,27)=18$
• $r=3$ → $27$ → $mod(27,27)=0$
• $r=4$ → $36$ → $mod(36,27)=9$
• $r=5$ → $45$ → $mod(45,27)=18$
• $r=6$ → $54$ → $mod(54,27)=0$
• $r=7$ → $63$ → $mod(63,27)=9$
• $r=8$ → $72$ → $mod(72,27)=18$

• [オ]：div(x, 9)*9
• 力：board[row_top+i]がnと等しい
• [キ]：mod(x, 9)
• [ク]：board[column_top+9*i]がnと等しい
• [ケ]：mod(div(x, 9)*9, 27)

誤りやすいポイント

• row_topを求める際にdiv(x,9) だけにしてしまい、さらに9を掛けるべきことを忘れる。例：x=10の行先頭は9である。
• column_topにdiv(x,9) を使ってしまう（列はmodを使う）。行と列の計算を取り違えると致命的。
• 3×3ブロックを一次元配列上で「連続した27個」と誤解する。実際は列方向に間隔（+1）と行方向に間隔（+9）が混在している。3行下がると +27になる性質を利用する。
• 行チェックと列チェックで増分を逆にする（行は +1、列は +9）。ループ内の添字計算を紙に書いて確かめる。
• modとdivの使い方混同（剰余か商かを明確にする）。特にブロック番号はdiv、ブロック内オフセットはmodを使う。
• 添字が0始まりであることを忘れる（1始まりの感覚だとオフバイワンになる）。

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