Nクイーン問題とは？
Nクイーン(N-Queens)は、N×Nの盤にN個のクイーンを互いに攻撃しないように置く方法(またはその場合の数)を見つける問題です。クイーンは同じ行・同じ列・両対角線に沿って攻撃するので、どの2つのクイーンも行・列・対角線を共有してはいけません。バックトラッキングの教科書的な例です。
核心の一行: 「1行に1つずつ、ダメなら戻る」。 全配置を闇雲に試す代わりに、行き詰まった瞬間に諦めて別の選択へ戻ります。
核心はバックトラッキング
各行にクイーンを1つずつ置くと決めれば、同じ行の衝突は自動的に消えます。残るは列と対角線だけです。
バックトラッキングはこう動きます — 現在の行の安全な列にクイーンを置いて次の行へ再帰し、置く場所がなければ(行き詰まれば)今置いたクイーンを取り除いて前の行へ戻り、別の列を試します。
枝刈り(pruning)
毎回盤全体を調べるのは遅いです。列の使用、両対角線の使用を真偽値配列で記録すれば、1マスの安全性をO(1)で判定できます。
- •同じ列:
col[c] - •↘ 対角線:
row + colが同じ - •↙ 対角線:
row - colが同じ(負を避けるため+N-1補正)
不可能な枝を即座に切るので探索量が大きく減ります。
動作原理
ステップ1. row = 0 から始めます。
ステップ2. 現在の行の各列 c について、列・両対角線が空いていればクイーンを置いて印を付け、row + 1 へ再帰します。
ステップ3. 再帰が戻ったら(成功でも失敗でも)印を消してクイーンを取り除きます(バックトラッキング)— 次の列を公平に試すためです。
ステップ4. row == N に到達すればN個全て置いたので、解が1つ完成します。
AlgoNoteの可視化は、クイーンが置かれ、行き詰まって戻り、取り除かれる過程を色でステップごとに示します。
時間計算量と空間計算量
| 計算量 | |
|---|---|
| 時間 | 最悪O(N!)付近(枝刈りで大幅減) |
| 空間 | O(N) |
枝刈りのおかげで実際の探索はN!よりはるかに少なくなります。
例で追ってみる
4クイーン:
- •(行0,列0)に置く → 行1は列2のみ安全 → 行2は安全な場所なし → 戻る
- •(行0,列1)に置く → 行1列3 → 行2列0 → 行3列2 → 解完成
- •4クイーンの解はちょうど2つです。
よくあるミス
- •対角線インデックス:
row+colとrow-col(+N-1補正)を混同すると衝突検査がずれます。 - •状態復元の欠落: 再帰から戻った後、列・対角線の印とクイーンを必ず戻す必要があります(バックトラッキングの核心)。
- •目標の混同: 「場合の数」か「1つの配置」かで止める条件が変わります。
AlgoNoteで直接確認しましょう
クイーンが1行ずつ置かれ、行き詰まると前の行へ戻って別の列を試すバックトラッキング過程をAlgoNoteでステップごとに確認できます。