关于八皇后问题 | 回溯与 n 皇后问题

德国国际象棋排局家马克斯·贝瑟尔于 1848 年在柏林的一份国际象棋杂志上提出了这个谜题。弗朗兹·诺克于 1850 年发表了全部 92 个解，并对更大的棋盘提出了同样的问题。卡尔·弗里德里希·高斯饶有兴趣地关注这个谜题，并在信中讨论过它。

互不攻击的八个皇后必须位于八个不同的行和八个不同的列。所以一个解就是把数字 1 到 8 打乱后的一种顺序，即一个排列，外加一条规则：任意两个皇后不能在同一条斜线上。在 40,320 个排列中，只有 92 个符合要求。

回溯一次构建解的一部分，一走进死胡同就立刻退回。对皇后来说：在下一行第一个安全的格子上放一个皇后；当某一行没有安全的格子时，就回到上一行，把那里的皇后往后移。1972 年，艾兹格·迪杰斯特拉正是用这种搜索，借这个谜题讲解结构化程序设计。

把棋盘旋转四分之一圈，或者翻转它，解仍然是解。这样每个解最多有八个版本。92 个解分成 12 个这样的组：十一个各有 8 个成员，一个只有 4 个，因为那个解旋转半圈后看起来不变。

在 n×n 的棋盘上，问题相同，只是换成 n 个皇后。从 4 开始，每个 n 都有解，而且解的数量增长很快：4×4 有 2 个，8×8 有 92 个，12×12 有 14,200 个。目前还没有已知的计数公式；纪录数值来自大规模的计算机搜索。

打开八皇后，点击一个格子放置皇后；再点一次就把它拿走。“显示攻击范围”会在你的皇后攻击的格子上标出圆点，红色的皇后在互相攻击。“求解”一步一步运行回溯搜索，并保留你放下的皇后。“下一个解”按顺序浏览每一个解，“大小”可以把棋盘从 4×4 改到 12×12。

常见问题

八皇后问题是谁发明的？

德国国际象棋排局家马克斯·贝瑟尔，于 1848 年。弗朗兹·诺克于 1850 年发表了第一套完整的解。

一共有多少个解？

标准棋盘上有 92 个。如果把旋转和镜像算作同一个，则有 12 个。

为什么 6×6 棋盘的解这么少？

它只有 4 个解，全部来自同一个组。更小的 5×5 棋盘有 10 个。更大的棋盘解越来越多：7×7 有 40 个，8×8 有 92 个。

PictorX 会上传什么吗？

不会。棋盘画在你浏览器里的画布上。“保存”会下载 PNG，“编辑”会在 PictorX 编辑器中打开那张图。

在浏览器中打开 PictorX — 无需安装，无需信用卡即可启动。