DIV CSS 佈局教程網

JavaScript 以遞歸回溯法解八皇后問題
編輯:關於JavaScript     

以下分享回溯法解八皇后的實作,附詳細註解。

function NQueens(order) {
    if (order < 4) {
        console.log('N 皇后問題需 order 大於 3!');
        return;
    }
    var nQueens = [];
    var backTracking = false;

rowLoop:
    for (var row = 0; row < order; row++) {
        // 若 row 小於 0,代表問題無解
        if (row < 0) {
            console.log('此 N 皇后問題無解!');
            break;
        }
        // 第一次進入這一列
        if (nQueens[row] === undefined) { nQueens[row] = []; }

        for (var col = 0; col < order; col++) {
            // 0 代表已檢測過且不可放皇后
            if (nQueens[row][col] === 0) { continue; }

            // 回溯時遇到「曾經可放」的位置,說明後續驗證沒通過,需重試
            else if (backTracking && nQueens[row][col] == 1) {
                // 若本列已到尾端,需繼續往前回溯
                if (col === order - 1) {
                    resetRow(nQueens, order, row);
                    row = row - 2;
                    continue rowLoop;
                }
                nQueens[row][col] = 0;
                backTracking = false;
                continue;
            }

            // 放下一個皇后
            nQueens[row][col] = 1;

            // 位置合法,跳到下一列(每列只能放一個皇后)
            if (isQueenValid(nQueens, row, col)) { continue rowLoop; }

            // 已到列尾仍找不到位置,代表前面的皇后放錯了,必須回溯
            else if (col == order - 1) {
                backTracking = true;
                resetRow(nQueens, order, row);   // 本列清為 undefined
                row = row - 2;                   // 減 2 是因為迴圈尾還有一次自增
                continue rowLoop;
            } else {
                nQueens[row][col] = 0;           // 未到列尾,繼續找
                continue;
            }
        }
    }
    return nQueens;
}

// 回溯前清空本列
function resetRow(nQueens, order, row) {
    for (var col = 0; col < order; col++) { nQueens[row][col] = undefined; }
}

// 判斷位置是否可放皇后
function isQueenValid(nQueens, row, col) {
    // 列(row)檢測
    for (var i = 0; i < col; i++) {
        if (nQueens[row][i] == 1) { return false; }
    }
    // 對角線檢測:左上 45 度與右上 45 度
    for (var j = 1; j < row + 1; j++) {
        if (nQueens[row - j][col] == 1 ||
            nQueens[row - j][col - j] == 1 ||
            nQueens[row - j][col + j] == 1) {
            return false;
        }
    }
    return true;
}

function printQ(queens) {
    for (var row = 0; row < queens.length; row++) {
        var rowText = '';
        for (var col = 0; col < queens.length; col++) {
            if (queens[row][col] === undefined) { queens[row][col] = 0; }
            rowText += queens[row][col] + ' ';
        }
        console.log(rowText);
    }
}

var queens = NQueens(8);
printQ(queens);

幾點說明

這份實作用 row = row - 2 配合 continue rowLoop 來「倒退回上一列」,減 2 是因為 for 迴圈尾端還有一次 row++。這種手動操作迴圈變數的寫法雖然能運作,但可讀性不佳,也容易在邊界上出錯。

更清晰的回溯寫法。回溯法的標準形式其實是「選位置 → 檢查 → 遞歸進入下一層 → 失敗則撤銷選擇」,用遞歸表達比操作迴圈指標自然得多:

function solveNQueens(n) {
    var results = [];
    var cols = [], diag1 = [], diag2 = [];

    function place(row, board) {
        if (row === n) { results.push(board.slice()); return; }
        for (var col = 0; col < n; col++) {
            if (cols[col] || diag1[row + col] || diag2[row - col + n]) continue;
            cols[col] = diag1[row + col] = diag2[row - col + n] = true;
            board.push(col);
            place(row + 1, board);
            board.pop();
            cols[col] = diag1[row + col] = diag2[row - col + n] = false;  // 撤銷選擇
        }
    }

    place(0, []);
    return results;
}

console.log(solveNQueens(8).length);   // 92 組解

這個版本用三個陣列分別記錄「欄是否被佔」、「兩條對角線方向是否被佔」,把每次合法性檢查從迴圈降為一次查表。對角線的編號技巧是關鍵:左上到右下的對角線以 row - col 為定值,右上到左下則以 row + col 為定值。

順帶一提,八皇后共有 92 組解(若把旋轉與鏡像視為同一組,則只有 12 組基本解)。原實作只回傳找到的第一組,若要列舉全部,改寫成上面的遞歸形式並移除 find 後的中止條件即可。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved