萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 腳本程式專題 >> JavaScript

JavaScript 遞歸回溯法解決八皇后問題完整實現

問題定義

在 8×8 棋盤上放置 8 個皇后,使任意兩個皇后不在同一行、同一列、同一對角線上。輸出所有合法解(共 92 組)或任一解。

回溯法核心思想

  1. **逐行放置**:第 0 行放 1 個,第 1 行放 1 個... 每行僅 1 個皇后。
  2. **逐列嘗試**:當前行遍歷 0~7 列,檢查該位置是否安全。
  3. **安全檢查**:同列、左上對角、右上對角無皇后。
  4. **遞歸深入**:安全則放置,進入下一行。
  5. **回溯撤銷**:某行所有列嘗試完畢無安全位置 → 回上一行,移除其皇后,繼續嘗試下一列。

完整帶註釋實現 (輸出第一組解)

function solveNQueens(n) {
    if (n < 4) { console.log('N<4 無解'); return null; }

    var board = []; // board[row] = col 表示該行皇后所在列
    var solutions = [];

    function isSafe(row, col) {
        for (var r = 0; r < row; r++) {
            var c = board[r];
            if (c === col) return false;                    // 同列
            if (c - r === col - row) return false;          // 主對角線 (行-列 差值相等)
            if (c + r === col + row) return false;          // 副對角線 (行+列 和值相等)
        }
        return true;
    }

    function backtrack(row) {
        if (row === n) { // 所有行放置完成
            solutions.push(board.slice()); // 複製當前解
            return true; // 只找一解可返回 true 停止;找所有解移除此行
        }
        for (var col = 0; col < n; col++) {
            if (isSafe(row, col)) {
                board[row] = col;       // 放置
                if (backtrack(row + 1)) return true; // 遞歸下一行
                board[row] = -1;        // 回溯:移除 (可省略,下輪覆蓋)
            }
        }
        return false; // 此行無解,觸發上層回溯
    }

    backtrack(0);
    return solutions[0] || null;
}

// 運行
var solution = solveNQueens(8);
if (solution) {
    console.log('解 (行->列):', solution); // 例: [0, 4, 7, 5, 2, 6, 1, 3]
    printBoard(solution);
}

function printBoard(cols) {
    for (var r = 0; r < 8; r++) {
        var line = '';
        for (var c = 0; c < 8; c++) line += (cols[r] === c ? '♛ ' : '· ');
        console.log(line);
    }
}

輸出示例

解 (行->列): [0, 4, 7, 5, 2, 6, 1, 3]
♛ · · · · · · ·
· · · · ♛ · · ·
· · · · · · · ♛
· · · · · ♛ · ·
· · ♛ · · · · ·
· · · · · · ♛ ·
· ♛ · · · · · ·
· · · ♛ · · · ·

效能優化技巧

技巧原理效能提升
位運算用 3 個整數位掩碼表示 `cols`、`diag1`、`diag2` 佔用情況,`O(1)` 判斷安全10x~100x
對稱性剪枝利用棋盤對稱,僅搜尋前半列,解數乘 2 (中心列特殊處理)~2x
迭代式非遞歸手動維護堆疊,避免函數調用開銷微幅

位運算版核心 (極速)

function solveNQueensBit(n) {
    var count = 0, solutions = [];
    var upperlim = (1 << n) - 1; // 低 n 位全 1

    function backtrack(cols, hills, dales, row, path) {
        if (cols === upperlim) { // 所有列佔滿 = 找到一解
            solutions.push(path.slice());
            return;
        }
        // 可用位置 = ~(cols | hills | dales) & upperlim
        var free = (~(cols | hills | dales)) & upperlim;
        while (free) {
            var currPos = free & -free; // 取最低位 1 (最右可用列)
            free ^= currPos;            // 移除該位
            var col = Math.log2(currPos); // 列索引
            path.push(col);
            backtrack(cols | currPos,
                      (hills | currPos) << 1,   // 主對角左移
                      (dales | currPos) >> 1,   // 副對角右移
                      row + 1, path);
            path.pop();
        }
    }
    backtrack(0, 0, 0, 0, []);
    return solutions;
}
// solveNQueensBit(8) 幾毫秒內得出 92 解

N 皇后問題擴展

  • 計數問題:OEIS A000170 (1, 0, 0, 2, 10, 4, 40, 92, 352, 724...)。
  • 約束滿足問題 (CSP):經典 AI 教學案例,可用 AC-3、啟發式搜尋 (MRV、LCV)。
  • 並行化:首行不同列分配給不同 Worker 並行搜尋。
copyright © 萬盛學電腦網 all rights reserved