N-Queens問題の詳細解析

🔍 問題の概要

N-Queens問題は、n×nのチェスボード上にn個のクイーンを配置する問題です。クイーンは縦・横・斜めの全方向に移動できるため、互いに攻撃し合わない位置に配置する必要があります。

4-Queens 解1

.

♕

.

♕

.

♕

.

4-Queens 解2

.

♕

.

♕

.

♕

.

♕

.

💻 TypeScript実装とコード解析

/**
 * N-Queens問題を解く関数
 * @param n - チェスボードのサイズ (n x n)
 * @returns 全ての解の配列。各解は文字列の配列で、'Q'はクイーン、'.'は空きマスを表す
 */
function solveNQueens(n: number): string[][] {
    const result: string[][] = [];
    const board: string[][] = Array(n).fill(null).map(() => Array(n).fill('.'));
    
    /**
     * 指定された位置にクイーンを配置できるかチェック
     * @param row - 行のインデックス
     * @param col - 列のインデックス
     * @returns 配置可能かどうか
     */
    function isSafe(row: number, col: number): boolean {
        // 同じ列をチェック（上方向のみ、下はまだ配置していないため）
        for (let i = 0; i < row; i++) {
            if (board[i][col] === 'Q') return false;
        }
        
        // 左上対角線をチェック
        for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] === 'Q') return false;
        }
        
        // 右上対角線をチェック
        for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] === 'Q') return false;
        }
        
        return true;
    }
    
    /**
     * バックトラッキングを使用してクイーンを配置
     * @param row - 現在の行
     */
    function backtrack(row: number): void {
        // ベースケース：全ての行にクイーンを配置完了
        if (row === n) {
            // 現在のボード状態を文字列配列として結果に追加
            result.push(board.map(row => row.join('')));
            return;
        }
        
        // 現在の行の各列でクイーンの配置を試行
        for (let col = 0; col < n; col++) {
            if (isSafe(row, col)) {
                // クイーンを配置
                board[row][col] = 'Q';
                // 次の行に進む
                backtrack(row + 1);
                // バックトラック（クイーンを取り除く）
                board[row][col] = '.';
            }
        }
    }
    
    backtrack(0);
    return result;
}

🧠 アルゴリズムの詳細解析

1. メイン関数の構造

1 初期化フェーズ
結果配列 result とボード配列 board を初期化します。ボードは二次元配列で、全てのセルを '.' で初期化します。

2. 安全性チェック関数 (isSafe)

2 縦方向チェック
現在の列 col の上方向（row=0からrow-1まで）にクイーンが存在するかチェック

3 左上対角線チェック
(row-1, col-1) から (0, 0) 方向へ対角線上にクイーンが存在するかチェック

4 右上対角線チェック
(row-1, col+1) から (0, n-1) 方向へ対角線上にクイーンが存在するかチェック

💡 重要な最適化ポイント：
下方向と下対角線のチェックが不要な理由は、バックトラッキングが上から下へ行を進むため、下の行はまだクイーンが配置されていないためです。

🔄 バックトラッキングの動作原理

バックトラッキングの流れ（4×4の例）

.

1 再帰的探索
各行で全ての列を試行し、安全な位置にクイーンを配置

2 制約満足
配置後、次の行に進んで同じ処理を再帰的に実行

3 バックトラッキング
行き詰まった場合、前の状態に戻ってクイーンを除去し、次の可能性を探索

4 解の記録
全ての行にクイーンが配置できたら、現在のボード状態を解として記録

📊 計算量解析

時間計算量

O(N!)
最悪の場合、各行でN個の選択肢があり、制約により選択肢が減少していく

空間計算量

O(N²)
ボード配列 + 再帰呼び出しスタック（最大N階層）

// 実際のパフォーマンス測定例
function measurePerformance() {
    const testCases = [4, 5, 6, 7, 8];
    
    testCases.forEach(n => {
        const start = performance.now();
        const solutions = solveNQueens(n);
        const end = performance.now();
        
        console.log(`N=${n}: ${solutions.length} solutions in ${(end - start).toFixed(2)}ms`);
    });
}

// 期待される結果:
// N=4: 2 solutions
// N=5: 10 solutions  
// N=6: 4 solutions
// N=7: 40 solutions
// N=8: 92 solutions

🎯 TypeScript特有の最適化

型安全性の確保

// 型注釈による安全性向上
function solveNQueens(n: number): string[][] {
    // 戻り値の型が明確
    const result: string[][] = [];
    
    // 2次元配列の型が明示的
    const board: string[][] = Array(n).fill(null)
        .map((): string[] => Array(n).fill('.'));
    
    // 内部関数も適切な型注釈
    function isSafe(row: number, col: number): boolean {
        // パラメータと戻り値の型が明確
        // ...
    }
}

パフォーマンス最適化のポイント

1. メモリ効率的な配列操作
Array(n).fill(null).map() を使用してTypeScriptの型チェッカーを満足させつつ、効率的な初期化を実現

2. 不要なコピーの回避
board.map(row => row.join('')) で文字列変換時のみ新しい配列を作成

3. 早期リターン
isSafe 関数で攻撃される位置が見つかったら即座にfalseを返す

🚀 実行例とテストケース

// テスト実行例
console.log("N=1の場合:");
console.log(solveNQueens(1));
// 出力: [["Q"]]

console.log("N=4の場合:");
const result4 = solveNQueens(4);
console.log(`解の数: ${result4.length}`);
result4.forEach((solution, index) => {
    console.log(`解 ${index + 1}:`);
    solution.forEach(row => console.log(row));
    console.log();
});

// 出力:
// 解の数: 2
// 解 1:
// .Q..
// ...Q
// Q...
// ..Q.
//
// 解 2:
// ..Q.
// Q...
// ...Q
// .Q..