🔍 N-Queens問題：ビットマスクアルゴリズム解析

バックトラッキング + ビット演算による高速化手法の詳細解説

📋 問題概要

N-Queens問題は、n×nのチェス盤にn個のクイーンを配置し、どのクイーンも互いに攻撃し合わないような配置の数を求める古典的な問題です。

4×4盤面での解1

4×4盤面での解2

💻 TypeScriptコード実装

/**
 * n-queens puzzle の解の総数を返す関数
 * @param n - チェス盤のサイズ (1 <= n <= 9)
 * @returns number - n-queens の異なる解の数
 */
function totalNQueensGPT(n: number): number {
    let count = 0;

    /**
     * 深さ優先探索 (バックトラッキング)
     * @param row - 現在の行
     * @param cols - 既に使用中の列 (bitmask)
     * @param diag1 - 既に使用中の対角線 (↘方向, bitmask)
     * @param diag2 - 既に使用中の対角線 (↙方向, bitmask)
     * @returns void
     */
    function dfs(row: number, cols: number, diag1: number, diag2: number): void {
        if (row === n) {
            count++;
            return;
        }

        // 置ける場所 (n ビット分だけ残す)
        let available = ((1 << n) - 1) & ~(cols | diag1 | diag2);

        while (available) {
            // 最右ビットを抽出
            const bit = available & -available;
            available -= bit;
            dfs(row + 1, cols | bit, (diag1 | bit) << 1, (diag2 | bit) >> 1);
        }
    }

    dfs(0, 0, 0, 0);
    return count;
}

🧠 アルゴリズムの処理ステップ

ステップ1: 初期化

解の数をカウントする変数countを0で初期化し、DFS関数を定義

ステップ2: ベースケース

全ての行にクイーンを配置完了したら、解の数を1増加

ステップ3: 配置可能位置計算

ビット演算で現在の行での配置可能な列を高速計算

ステップ4: 再帰探索

各配置可能位置に対して再帰的にDFSを実行

🔧 ビットマスクの動作原理

n=4の場合のビット表現例：

cols (列制約):
0
1
0
1
→ 列1と3が使用中
diag1 (↘対角線):
1
0
1
0
→ 対角線制約
diag2 (↙対角線):
0
1
0
1
→ 対角線制約
available:
0
0
0
0
→ 配置可能位置なし

重要なビット演算：

⏱️ 計算量解析

項目 従来手法 ビットマスク手法 改善効果
衝突判定 O(n) O(1) 大幅改善
時間計算量 O(n! × n) O(n!) n倍高速化
空間計算量 O(n²) O(n) メモリ効率化
n=8での実行速度 遅い 高速 実用的

🎯 アルゴリズムの特徴

✅ 利点

  • O(1)での衝突判定
  • メモリ効率が良い
  • コードが簡潔
  • 高速な実行速度

⚠️ 注意点

  • ビット演算の理解が必要
  • デバッグが困難
  • nの上限（通常32ビット）
  • 可読性がやや劣る

🎮 インタラクティブデモ

異なるnの値でのアルゴリズム実行結果：