学习首页/贪心与回溯/N 皇后交互演示 · JavaScript

代码与动画 N QUEENS

N 皇后.

逐行尝试放置皇后，遇到同列或对角线冲突时回溯。

回溯搜索搜索规模 O(n!)（粗略上界）找到首个解即停止

原理与执行逻辑

逐行放置一个皇后，将列和两条对角线冲突作为剪枝条件。某一行没有可行位置时撤销上一行的选择，继续尝试其他列。

执行步骤

  1. 用 columns[row] 保存该行皇后的列。
  2. 从左到右尝试当前行每一列，与已放置皇后检查同列及对角线冲突。
  3. 无冲突时加入列并递归下一行，后续失败则弹出列。
  4. 放满 n 行后返回首个解，停止继续枚举。

关键理解

同列条件是 c1 = c2，对角线条件是 |c1 - c2| = |r1 - r2|。已放置部分始终互不攻击，冲突候选无需继续深入。

简短示例

4 皇后的列下标 [1, 3, 0, 2] 表示四行分别放在第 1、3、0、2 列；所有列不同，任意两点都不在同一对角线。

代码与执行动画

STEP 0 / 39
N 皇后
function firstQueens(n) {  const columns = [];  function visit(row) {    if (row === n) return true;    for (let col = 0; col < n; col++) {      const conflict = columns.some((c, r) => c === col || Math.abs(c - col) === row - r);      if (conflict) continue;      columns.push(col);      if (visit(row + 1)) return true;      columns.pop();    }    return false;  }  return visit(0) ? columns : [];}
15 行 · 0 个片段标记
················
当前数据正在操作已访问 / 命中标记 / 指针
0

开始逐行放置

每行放置一个皇后，列与两条对角线均不能冲突。

配置演示数据

应用后重新生成执行过程，可单步观察结果。

实现说明

N 皇后的操作规则

演示 4 或 5 皇后，按列从左到右尝试。Q 表示已放置的皇后，× 表示冲突候选格；返回每行皇后的列下标，展示首个可行解。

对应题目与扩展练习

观察执行过程后，按题目约束调整输入、返回值与实现。链接打开官方题目页面。