八皇后問題是經典的演算法題目:在 8×8 的棋盤上放八個皇后,讓任意兩個皇后都不會互相威脅(同行、同列、同對角線皆不可)。網路上討論很多,但用 JavaScript 實作的相對少見,本文就來完整走一遍。
最直觀的建模方式是「每一列只放一個皇后」。這樣一來,只要依序決定每一列皇后放在哪一行的哪個位置,並在每次放置後檢查是否合法;若後續發現無解,就退回上一列改放別的位置——這正是回溯法的核心。
function NQueens(order) {
// 4 皇后以下的問題無解(order 為 2、3 時)
if (order < 4) {
console.log('N Queens problem apply for order bigger than 3 !');
return;
}
var nQueens = [];
var backTracking = false;
rowLoop: for (var row = 0; row < order; row++) {
// 若 row 小於 0,代表所有可能都試完了,問題無解
if (row < 0) {
console.log('This N Queens problem has no solution !');
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;
}
// 否則標記為 0,繼續往後找
nQueens[row][col] = 0;
backTracking = false;
continue;
}
// 嘗試在 (row, col) 放皇后
nQueens[row][col] = 1;
// 合法就換下一列
if (isQueenValid(nQueens, row, col)) {
continue rowLoop;
}
// 走到該列末端仍找不到位置,代表前面某列的選擇有問題,需要回溯
else if (col == order - 1) {
backTracking = true;
resetRow(nQueens, order, row); // 清空本列,讓它能重新嘗試
row = row - 2; // 迴圈尾會 +1,所以這裡 -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;
}
}
// 判斷 (row, col) 是否可以放皇后
function isQueenValid(nQueens, row, col) {
// 同列檢查
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);
1. 為什麼是 row = row - 2?因為在 for 迴圈中,每次迭代結束都會自動執行 row++。要回到上一列,就必須先減 2,加上迴圈自身的加一,淨效果才是 -1。
2. 為什麼要用 0 和 1 兩種標記?回溯時需要區分兩種狀態:這個位置「檢查過且不可用」(0),還是「曾經放得進去但後續被推翻」(1)。只有 1 才需要在回溯時重新嘗試,0 則可以直接跳過,這 distinction 讓回溯邏輯得以正確運作。
3. 為什麼用 labelled continue?continue rowLoop 直接跳到外層迴圈的下一次迭代,跳過 col++ 的剩餘流程。若用一般的 continue,只會跳過內層迴圈,邏輯就錯了。
如果只想要「找出所有解」,用遞迴會比回溯狀態機清楚得多:
function solveNQueens(n) {
var results = [];
function place(row, cols, diag1, diag2, current) {
if (row === n) {
results.push(current.slice());
return;
}
for (var col = 0; col < n; col++) {
var bit = 1 << col;
// 檢查該位置的三個方向是否已被佔用
if ((cols & bit) || (diag1 & (1 << (row + col))) || (diag2 & (1 << (row - col + n)))) {
continue;
}
current.push(col);
place(row + 1, cols | bit,
diag1 | (1 << (row + col)),
diag2 | (1 << (row - col + n)),
current);
current.pop();
}
}
place(0, 0, 0, 0, []);
return results;
}
console.log(solveNQueens(8).length); // 92 組解
這個版本用位元運算記錄「哪些欄、哪兩條對角線已被佔用」,把每次合法性檢查壓到幾個位元運算,八皇后共有 92 組解,跑起來幾乎是瞬時的。