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