応用情報技術者 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. ループ変数 ウ
   図7には
   if ( colk と upwd[i+k-1] と downwd[ ... ] … )
   とあり、配列添字に使われているのは 「k」 だけです。従ってループで増減させる変数も 「k」 とするのが自然です。
2. ループ開始値 エ
   解法の手順には
   「1行目において、1列目にクイーンを配置する。次に…2行目の列を1列目から順に探索し…」
   とあります。列探索は必ず 「1列目から」 始めると明記されているため、開始値は 「1」 です。
3. ループ終了値 オ
   N×N 盤の全列を調べきるまで探索を続けるため、終了値は最大列番号である 「N」 です。
4. クイーンを配置した列を記録する カ
   配列 pos の定義は
   「行番号を添字とし、その行に配置したクイーンの位置（列番号）を値とする」
   ですから、行 i にクイーンを置いた列 k を格納する代入文は
   posi ← k となります。
5. 次の行を再帰探索する キ
   1 行に 1 個ずつクイーンを置く方針なので、行 i の次は 「i+1 行目」 を探索します。したがって再帰呼び出しの実引数は 「i+1」 です。

誤りやすいポイント

• 変数名の取り違え
  k と i を混同し、列探索を i で回してしまうと行番号と列番号が逆転します。
• ループ開始値の誤記
  「列1から探索」という文面を読み落として 0 から開始すると、配列外参照や列番号ずれを起こします。
• pos の更新忘れ
  クイーンを配置した時点で posi を更新しないと、バックトラック後に正しい出力が得られません。

FAQ

解答の論理構成

1. 【問題文】には最初の作業として
   「・1行目において、1列目にクイーンを配置する。」
   と明記されています。したがって探索は“行1”から始まります。
2. 図7の関数 search(i) は「i行目以降についてクイーンの配置の仕方を探索する」手続きです。
   つまり、行1から探索を開始したい場合は i = 1 を与えます。
3. 図8のメインプログラムでは
   if ( search( ク ) と SUCCESS が等しい ) then
   と書かれており、ここに渡す値が“開始行”になります。
4. 以上より ク には 1 を入れ、search(1) として探索を開始するのが論理的帰結です。
5. よって解答は
   「ク：1」

誤りやすいポイント

• 0 行目や N 行目から探索を始めると考えてしまう
  → 配列添字を 0 起点で実装する言語に慣れていると誤解しやすいですが、本問題では【問題文】が「1行目」からの記述です。
• pos 配列の初期値が 0 なので「行番号も 0 から」と連想してしまう
  → pos の 0 は「未配置」を表す特別値であって行番号ではありません。
• search の呼出しで変数を渡すと誤認する
  → 図8には引数として変数名は示されておらず、固定値を渡す想定です。

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