N クイーン

n × n の盤面の各行にクイーンを一つ置き、同じ列や対角線を共有させない問題です。列を左から試し、衝突なら即拒否し、一行に合法位置がなければ前の選択を戻します。

クイーンごとに列、row - col、row + col を登録します。三つとも未使用なら置けます。取り消しも三つすべてを消し、存在しない駒の制約を残しません。

N クイーンのバックトラッキング

行順に再帰し、一枚置いてから search(row + 1) を呼ぶため、行の重複は構造で防げます。

• 同列は同じ col。
• \ の対角線は同じ row - col。
• / の対角線は同じ row + col。

三集合の検査は通常のハッシュモデルで期待 O(1)。衝突候補は盤面を変えません。合法なら queens に加え、三キーを登録して再帰します。子が成功すれば結果を保って返し、失敗なら駒と三キーを消して次の列を試します。

不変条件は、失敗した子から戻った時に、呼び出し元の選択前の状態を完全に回復することです。カーソルを後ろへ動かすだけではありません。

数独、時間割、資源割り当て、制約探索にも「選択、予約、再帰、失敗時の解放」が現れます。このレッスンは最初の解だけで、全列挙、対称性による枝刈り、ビットマスクは使いません。

探索をステップで追う

既定は n = 4、列は 0, 1, 2, 3 の順。

1. search(0) が (0, 0) を試す。三集合が空で配置し、行 1 へ。
2. 行 1 は列の衝突で (1, 0)、row - col = 0 で (1, 1) を拒否。(1, 2) を置き、列ベクトルの前部は [0, 2]。
3. 行 2 は全滅。列 0 は使用済み、1 は (1, 2) と /、2 は使用済み、3 は (1, 2) と \ で衝突。false。
4. (1, 2) と三キーを消し、行 1 の列 3 に (1, 3) を置く。
5. 行 2 に (2, 1) を置くが、行 3 は全列衝突。(2, 1) を戻し、行 2 の後続もなく、戻って (1, 3) も消す。
6. 行 1 が尽き、(0, 0) を消す。次の根選択前に盤面と三集合が空へ戻る。
7. (0, 1) を置く。行 1 は 0、1、2 を拒否して (1, 3)。行 2 は (2, 0)。行 3 は 0、1 を拒否し (3, 2)。
8. row = 4 の基底へ到達し、[1, 3, 0, 2] を返す。添字が行、値が列。

候補検査 26、仮配置 8、バックトラック 4 回です。18 回の即時拒否で、114 個の未制約の後続行割り当てを生成せずに済みます。制約なしの四行は 4^4 = 256 完全盤面、列重複なしなら 4! = 24。26 は候補訪問、256 と 24 は完成割り当てで、同じ単位ではありません。

赤線が候補を妨げる駒を示します。X は即衝突で未配置、戻しの輪は合法配置後の子探索が失敗した印です。右欄の 4 x 4 = 16 は生成されなかった十六の後続割り当てを表します。

時間・空間計算量

実際の量は列順で変わります。左からの場合、n = 4 は四回戻しますが、n = 5 は [0, 2, 4, 1, 3] へ取り消しなしで達します。大きい盤面が必ず難しい首解トレースとは限りません。

一つの解が必要で探索木が小さければ、この集合型が使えます。全解には成功時に盤面をコピーし、早期 return せず続けます。大きい N はビットマスクや対称性、豊富な制約は専用の制約・SAT ソルバーが候補です。

境界ケース

• n = 1 は即 [0]。
• n = 2、3 は無解。根の全選択を尽くし、Python None、JavaScript null を返す時に全集合を空へ戻す。
• 画面の 1 <= n <= 5 は表示制限。
• 列順は最初の解と戻し回数を変え得るが、合法盤面の集合は変えない。
• 全解を集めるなら成功基底でコピーして継続する。

よくある間違い

• 盤面だけ戻す。 古い列・対角キーが合法候補を拒否します。
• 登録と削除の対角式を混ぜる。 row - col は \、row + col は /。名前を交換しても構いませんが、検査・追加・削除の式は統一します。
• 最初の失敗で行全体を false にする。 次の列を試し、全候補の後に false です。
• 拒否でも状態を変える。 衝突候補は入れていないので、書いてから片付ける必要はありません。
• 結果の意味を誤る。 [1, 3, 0, 2] の添字は行、値は列で、駒 ID ではありません。