N-Queens Algorithm Deep Analysis

アルゴリズム概要

N-Queens問題は、N×Nのチェス盤上にN個のクイーンを、互いに攻撃し合わないように配置する問題です。この問題をバックトラッキング手法で解決します。

ソースコード解析

/**
 * N-Queens問題を解く関数
 * @param {number} n - チェス盤のサイズ (1 <= n <= 9)
 * @returns {string[][]} - 全ての有効なクイーン配置を返す
 * 
 * 時間計算量: O(N!) - バックトラッキングで全探索
 * 空間計算量: O(N^2 * 解の個数) - 盤面保存のため
 */
function solveNQueens(n: number): string[][] {
    const results: string[][] = [];
    
    // 現在の盤面を '.' で初期化
    const board: string[][] = Array.from({ length: n }, () => 
        Array(n).fill('.')
    );
    
    // 使用済みの列・対角線を記録する集合（O(1)チェックのため）
    const cols: Set = new Set();      // 同じ列
    const diag1: Set = new Set();     // 左上→右下 (row-col)
    const diag2: Set = new Set();     // 右上→左下 (row+col)
    
    /**
     * バックトラッキング探索
     * @param {number} row - 現在の行
     */
    function backtrack(row: number): void {
        // ベースケース: 全ての行にクイーンを配置完了
        if (row === n) {
            const solution: string[] = board.map(r => r.join(''));
            results.push(solution);
            return;
        }
        
        // 現在の行の各列を試行
        for (let col = 0; col < n; col++) {
            // 攻撃範囲チェック（O(1)時間）
            if (cols.has(col) || 
                diag1.has(row - col) || 
                diag2.has(row + col)) {
                continue; // 制約違反のためスキップ
            }
            
            // クイーンを配置
            board[row][col] = 'Q';
            cols.add(col);
            diag1.add(row - col);
            diag2.add(row + col);
            
            // 次の行を再帰探索
            backtrack(row + 1);
            
            // バックトラック: 状態を元に戻す
            board[row][col] = '.';
            cols.delete(col);
            diag1.delete(row - col);
            diag2.delete(row + col);
        }
    }
    
    backtrack(0); // 0行目から開始
    return results;
}

インタラクティブ可視化

計算量解析

重要な最適化ポイント