回溯算法解八皇后问题详解

本文深入解析了如何用回溯算法优雅地解决经典的八皇后问题——在8×8棋盘上放置8个互不攻击的皇后，确保任意两个皇后不在同一行、列或对角线上；通过JavaScript递归实现，巧妙利用数组记录每行皇后位置，并借助isSafe函数实时检测列与双对角线冲突，配合“尝试—验证—失败回退”的核心机制，高效枚举所有92种合法解，既展现了回溯算法的简洁逻辑与强大剪枝能力，也为理解递归状态管理和约束求解提供了绝佳范例。

八皇后问题是回溯算法的经典应用。目标是在8×8的国际象棋棋盘上放置8个皇后，使得任意两个皇后都不能在同一行、同一列或同一条对角线上。JavaScript中通过递归和回溯可以清晰地实现这一逻辑。

基本思路

使用一个数组queens记录每行皇后的列位置，例如queens[i] = j表示第i行的皇后在第j列。逐行放置皇后，每放一个就检查是否与前面的皇后冲突。如果不冲突，进入下一行；如果冲突，尝试下一列。若当前行所有列都不合法，则回退到上一行调整位置。

判断位置是否安全

每次尝试在某行某列放置皇后前，需要验证该位置是否安全。主要检查三点：

• 是否与已放置的皇后在同一列
• 是否在左上对角线（行差等于列差）
• 是否在右上对角线（行差等于列的反向差）

代码实现如下：

function isSafe(queens, row, col) {
  for (let i = 0; i 
回溯主函数
使用递归函数尝试在每一行放置皇后。当成功放置8个时，保存一个解。核心是尝试-检查-回退的过程。
function solveNQueens(n = 8) {
  const result = [];
  const queens = Array(n).fill(-1);
function backtrack(row) {
if (row === n) {
result.push([...queens]);
return;
}
for (let col = 0; col < n; col++) {
  if (isSafe(queens, row, col)) {
    queens[row] = col;
    backtrack(row + 1);
    queens[row] = -1; // 回溯
  }
}
}
backtrack(0);
return result;
}
输出结果示例
调用solveNQueens()会返回所有合法解，每个解是一个列索引数组。可进一步格式化为棋盘展示：
const solutions = solveNQueens();
console.log(`共找到 ${solutions.length} 种解法`);
// 打印前几个解
solutions.slice(0, 3).forEach((solution, index) => {
console.log(解 ${index + 1}:, solution);
});
基本上就这些。通过递归尝试每种可能，利用约束剪枝无效路径，回溯法高效求出所有解。不复杂但容易忽略细节，比如对角线判断和状态重置。
本篇关于《回溯算法解八皇后问题详解》的介绍就到此结束啦，但是学无止境，想要了解学习更多关于文章的相关知识，请关注golang学习网公众号！