在 N×N 棋盘上放置 N 个皇后,使其互不攻击。
点格子放皇后。粉红射线是攻击线:同行、同列、同对角线都会被攻击。
同样棋盘规模手动解题,用时少者胜。
当前设置:8 皇后
在 N×N 的国际象棋棋盘上放置 N 个皇后,使得任意两个皇后都不能互相攻击——即不在同一行、同一列或同一对角线上。这是组合数学与算法设计中的经典问题。
国际象棋中的皇后可以沿着行、列和对角线方向移动任意格数。因此放置 N 个互不攻击的皇后,意味着每行、每列、每条对角线上最多只能有一个皇后。
在尝试放置皇后时,跳过那些会立即与已放置皇后冲突的列(同列、同对角线)。这种「剪枝」大幅减少了需要探索的搜索空间。
许多解可以通过旋转和翻转得到,因此实际独立解的数量更少。各 N 的解数:
切换到可视化模式,观看回溯算法如何探索搜索树!蓝色脉冲表示正在尝试的位置,红色表示冲突,绿色表示安全——直观体会算法的每一步决策。