以下分享回溯法解八皇后的實作,附詳細註解。
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 後的中止條件即可。