N8
00:00

点格子放皇后。粉红射线是攻击线:同行、同列、同对角线都会被攻击。

联机竞速 · 邀请好友

联网竞速

同样棋盘规模手动解题,用时少者胜。

当前设置:8 皇后

什么是 N 皇后问题?

在 N×N 的国际象棋棋盘上放置 N 个皇后,使得任意两个皇后都不能互相攻击——即不在同一行、同一列或同一对角线上。这是组合数学与算法设计中的经典问题。

皇后的攻击范围

国际象棋中的皇后可以沿着行、列和对角线方向移动任意格数。因此放置 N 个互不攻击的皇后,意味着每行、每列、每条对角线上最多只能有一个皇后。

回溯算法

  1. 从第一行开始,尝试在每一列放置皇后
  2. 放置后检查是否与已有皇后冲突
  3. 如果安全,继续到下一行
  4. 如果当前行所有列都冲突,回溯到上一行尝试下一个位置

剪枝优化

在尝试放置皇后时,跳过那些会立即与已放置皇后冲突的列(同列、同对角线)。这种「剪枝」大幅减少了需要探索的搜索空间。

对称性与解的数量

许多解可以通过旋转和翻转得到,因此实际独立解的数量更少。各 N 的解数:

4→2
5→10
6→4
7→40
8→92
9→352
10→724
11→2680
12→14200

试试可视化模式

切换到可视化模式,观看回溯算法如何探索搜索树!蓝色脉冲表示正在尝试的位置,红色表示冲突,绿色表示安全——直观体会算法的每一步决策。