応用情報技術者 2012年 秋期 午後 問02

解答の論理構成

1. 問題文は「N×Nマスの場合、配列colの大きさはNであり、upwdとdownwdの大きさはともにアである。」と述べています。
2. upwdとdownwdはそれぞれ“斜め上方向”“斜め下方向”を示す配列です。
3. $N\times N$ の盤面で斜め方向に走る利き筋（＝対角線）は、 • 左上→右下方向：盤面右端までに $N$ 本、下端までに $N-1$ 本の計 $2N-1$ 本
   • 左下→右上方向：同様に計 $2N-1$ 本
   のように、それぞれ $2N-1$ 本存在します。
4. よって、斜め方向を表す各配列の要素数は「$2N-1$」でなければ全ての対角線を一意に管理できません。
5. したがって、ア に入る字句は「2N-1」となります。

誤りやすいポイント

• 「対角線は $N$ 本しかない」と思い込む
  → 盤面中央をはさんで上下（または左右）にもう $N-1$ 本あることを見落としやすいです。
• “両方向合わせて $2(2N-1)$ 本”と考え、配列も倍にする
  → upwdとdownwdは方向別に1本ずつ用意されるため、各配列は $2N-1$ で十分です。
• 端のマスにあるクイーンを想定せず、添字範囲を $0～2N-2$ ではなく $1～2N-2$ など半端に設定する
  → 図中の添字は「1」から始まるため、範囲は必ず $1～2N-1$ を確保する必要があります。

FAQ

解答の論理構成

1. 斜め方向の管理用配列
   【問題文】では「盤面の利き筋の方向別に配列col（列方向）、upwd（斜め上方向）及びdownwd（斜め下方向）を用意した」とあり、各マスにクイーンを置くと3本の配列要素をNOT_FREEにします。
2. upwdの添字規則は与えられている
   同じ文中で「upwd[i+k-1]」と添字式を明示しています。斜め上方向は行番号iと列番号kの“和”が一定であるため、i+kが基準になるのは自然です。
3. downwdの本質は “行−列” が一定
   斜め下方向は行番号と列番号の“差” i-kが同じマスを結びます。
4. 負値を回避するためのオフセット
   差i-kは
   • 最小で1-N（一番左上のマス）
   • 最大でN-1（一番右下のマス）
     と負の値を取り得ます。配列添字は1以上の整数でそろえたいので、定数を足してシフトします。
5. 0ではなく N を加える理由
   • 値域1-N … N-1に N を加えると1 … 2N-1に変換できます。
   • この範囲は【問題文】の「upwdとdownwdの大きさはともにアである」から、配列長が2N-1であることと整合します。
6. 結論
   以上より「downwd[イ]」の添字は
   i - k + N
   となり、模範解答の「イ：i-k+N」と一致します。

誤りやすいポイント

• upwdと同じく +1オフセットを付けてi-k+N-1とずらしてしまう。
• i-kが負になるケースを考えずにそのまま配列添字に用いて実行時エラーを起こす。
• 差ではなく和を用いてupwdとdownwdを混同する。

FAQ

解答の導き方

1. ループ変数（ウ）
   for 文の直後の条件が「col[k] と upwd[i+k−1] と downwd[[イ]] が全て FREE と等しい」となっており、列を表す添字は k です。関数 search は i 行目について列を順に試すので、ループ変数は列番号の k です。
   → [ウ] = k
2. 開始値（エ）と終了値（オ）
   本文は解法を「1 行目において、1 列目にクイーンを配置する。次に 2 行目において、1 列目から順に、…クイーンが配置できる列を探索する」と説明しています。各行の探索は 1 列目から始まり、本文の「N×N マスの場合、配列 col の大きさは N」のとおり列番号は 1〜N です。
   → [エ] = 1、[オ] = N
   本文の「取り除いたクイーンの次の列以降で…探索する」という動作は、開始値を変えなくても実現できます。後続の行で FAILURE が返ると①でクイーンを取り除き、同じ for 文が k を 1 増やして次の列を試すからです。
3. クイーンを配置する処理（カ）
   本文に「配列 pos は、行番号を添字とし、その行に配置したクイーンの位置（列番号）を値とする」とあり、①では「pos[i] ← 0」で取り除いています。配置するときはその逆で、i 行目に列番号 k を記録します。
   → [カ] = pos[i] ← k
4. 再帰呼出しの引数（キ）
   search は「i 行目以降についてクイーンの配置の仕方を探索する」関数です。i 行目に置けたら、次は i+1 行目以降を探索します。
   → [キ] = i+1

誤りやすいポイント

• エを「前回試した列の次」を表す変数にしてしまう。再試行は for 文が k を進めることで行われるので、開始値は常に 1 です。
• ループ変数を行番号の i と取り違える。行は search の引数 i、列は for 文の k です。
• カで「col[k] ← NOT_FREE」を答える。この処理は図7で既にカの次の行に書かれており、カは pos の記録です。

FAQ

解答の導き方

1. 関数 search の引数の意味
   本文に「i 行目以降についてクイーンの配置の仕方を探索する再帰関数 search」とあります。引数は探索を始める行番号です。
2. 探索の開始位置
   本文の解法は「1 行目において、1 列目にクイーンを配置する」から始まります。盤面全体（1 行目以降）の配置を探すので、最初の呼出しでは 1 行目を指定します。
3. 結論
   → [ク] = 1
   search(1) の中で 1 行目のクイーンを置き、search(2)、search(3)、…と再帰的に次の行へ進みます。

誤りやすいポイント

• 0 を答える。本文の行番号・列番号は 1 から始まり、図3〜6 の配列の添字も 1 からです。
• N を答える。search は「i 行目以降」を探索するので、N を渡すと最後の行しか探索しません。

FAQ

解答の論理構成

1. 初期状態
   メインプログラム（図8）の
   if ( search( ク ) …
   でsearch(1) が呼ばれ、全配列は FREE、posは全て0です。
2. 探索木の展開順序
   関数searchは図7の
   for ( ウ を エ から オ まで1ずつ増やす )
   で列kを 1 → 2 → 3 → 4 の順に調べます。
3. ① が実行される条件
   図7で示された ① は

1. 4×4マスにおける実行過程
   （各行の “→” は実際にクイーンを置いた列、×は衝突で置けなかった列を表す）

   行	調査順	結果	① 実行有無
   1	1→	後続で失敗	①④
   2	1× 2× 3→	後続で失敗	①①
   3	1× 2× 3× 4×	全滅 → 戻る	—
   2	3を取り除き4→	後続で失敗	①③
   3	1× 2→	後続で失敗	①②
   4	全滅 → 戻る	—
   3	2を取り除き 全滅	—
   2	4を取り除き 全滅	—
   1	1を取り除き2→	以降は成功	①④

   ① が実行されたタイミングは次の4回です。
   1. (2行3列) を取り除く
   2. (3行2列) を取り除く
   3. (2行4列) を取り除く
   4. (1行1列) を取り除く
2. 結論
   以上より、図9の解に到達するまでに
   「図7中の①の部分」は 4回 実行されます。

誤りやすいポイント

• ① は “列を1つ進めるたび” ではなく、“再帰呼び出しが FAILURE を返したときだけ” 実行されます。
• 同じ行で複数回クイーンを置き換えても、① が走るのは “取り除くときだけ” であり、“置き直す前の衝突判定” では走りません。
• 盤上で置ける列が0本になった行では その行では①が発生しない 点を忘れがちです（①は「置いた後」にしか現れないため）。

FAQ