八皇后问题(1848) — 把八个棋子摆得互不攻击。连高斯也数过的棋盘

前言 — 摆放八个纵横斜向都能攻击的棋子

这是 1848 年刊登在德国国际象棋杂志上的一道题。在 8×8 的棋盘上放 8 个皇后,任何一个皇后都不能处在会被其他皇后吃掉的位置。工具只有棋盘和棋子。规则一句话就能说完。

皇后可以纵向、横向、斜向一直走到棋盘边缘。每放一个,它所在的行、列和两条斜线就被封住。可放的位置转眼间越来越少。即便如此,把八个都放完的摆法依然存在,一共有 92 种。

本文从 1848 年的马克斯·贝泽尔(Max Bezzel)讲起,经过 1850 年的瑙克(Nauck)与高斯,1874 年的格莱舍(Glaisher),直到 1971 至 72 年的戴克斯特拉(Dijkstra)。在现代,2024 年 LinkedIn 公开的 Queens 中,也能看到非常相似的约束。我只以历史学者的眼光,写已经确认的内容。

八个互不攻击的皇后的排列(示意图・AI 生成)

那个时代的背景 — 杂志上的出题、书信往来、枚举的竞赛

1848 年,国际象棋问题作者马克斯·贝泽尔在柏林的国际象棋杂志上发表了八皇后问题。贝泽尔是问题作者,不是数学家。作为棋盘上的游戏提出的问题,后来成了数学的题材。

1850 年,弗朗茨·瑙克给出了 92 种解。不过,他并没有附上这就是全部的证明。据传,瑙克还进一步考虑了把棋盘扩展为 n×n、放 n 个皇后的一般性问题。

同在 1850 年,数学家高斯也在与天文学家舒马赫(Schumacher)的书信中思考这个问题。据说高斯在找到 72 种解时,得知了瑙克的 92 种。到此为止,是近年一篇概述论文所述的经过。

“共 92 种”的证明,据说是由 1874 年的 J・W・L・格莱舍给出的。同一年,S・京特(Günther)提出了使用行列式的方法。不过,这个问题的来历因作者而异。论文本身也声明,各文献所述的历史并不相同。

书信与棋盘并排的十九世纪中叶的书桌(示意图・AI 生成)

机制 — 每行放一个,搜索范围一下子缩小

来数一数摆法有多少种。从 64 格中选 8 格,有 4,426,165,368 种。全部检查,靠手是做不到的。

这时会发现一件事:同一行放两个,必然互相攻击。所以每行恰好放一个。剩下只需逐行决定列。如果列也不重复,摆法就减少到 8 的阶乘,即 40,320 种。再检查斜线,剩下的就是 92 种。

把 92 种按旋转或翻转后能重合的归并,共有 12 类。11 类各有 8 种,剩下 1 类左右上下对称,有 4 种。11×8+4 等于 92。

戴克斯特拉在 1971 年 8 月的《A Short Introduction to the Art of Programming》(EWD316)第 9 章中处理了这个问题。把每一行的列位置记录在数组里,用布尔值数组管理可用的列和斜线。走到死胡同就退回一步,尝试另一列。这种“退回”的步骤,称为回溯(backtracking)。

攻击线的棋盘,与在死胡同处回退的搜索树(示意图・AI 生成)

通向现代的谱系 — 从编程教材,到计算难度的研究

据英文版 Wikipedia,戴克斯特拉在 1972 年用这个问题展示了“结构化程序设计”的力量。同年的合著《Structured Programming》(达尔、戴克斯特拉、霍尔)广为人知。戴克斯特拉在 1972 年还获得了图灵奖,授奖理由是倡导结构化程序设计。

扩大棋盘规模的研究也在继续。直到 2016 年,27×27 的棋盘上的全部解已被枚举出来。另一方面,解的存在本身并不难。除 2 和 3 之外的所有 n,都存在可放置的摆法。

变难的是先放置一部分皇后的情形。2017 年,Gent、Jefferson、Nightingale 证明,这个“从中途补完”的问题是 NP 完全,且是 #P 完全的。这个古老的游戏,也成了 AI 研究性能测试的题材。

2024 年 5 月,LinkedIn 将 Queens 与 Pinpoint、Crossclimb 一同公开。这是按行、列和颜色区域放置皇后的游戏。与八皇后同一类的约束,在这里也被使用。不过,没有确认到开发者说过自己受八皇后启发的资料。与其说是谱系,不如读作同一类型的游戏,这样更稳妥。

从棋盘到搜索、彩色分区格子、再到屏幕的谱系(示意图・AI 生成)

参考文献

本文参考的信息来源(贝泽尔的原始文献、瑙克与高斯的书信、格莱舍的论文本身均未确认。历史叙述依据下列概述与论文):

・Wikipedia: Eight queens puzzle

・Wikipedia(日语): エイト・クイーン

・The n-queens problem (arXiv:2109.08083)

・Matemateca IME-USP: 8 Queens problem

・E. W. Dijkstra: EWD316, A Short Introduction to the Art of Programming

・EWD316 第 9 章: The problem of eight queens

・Wikipedia: Edsger W. Dijkstra

・Gent, Jefferson, Nightingale: Complexity of n-Queens Completion (JAIR 59, 2017)

・Wikipedia: LinkedIn(游戏功能一节)

・Aftermath: LinkedIn Games(Queens 的规则介绍)

结语 — 没有证明的 92,与一百七十年后的棋盘

1850 年,瑙克用手找到了 92 种。当时还没有这就是全部的证明。证明出现于 1874 年。答案先出现,理由随后追上。在数学史上,这是常见的顺序。

1848 年的问题,到 1971 年成了“思考方式的范例”,到 2017 年成了“难度的标尺”。到 2024 年,在每天都有人玩的屏幕上,也排列着非常相似的约束。

从历史上看,这个棋盘所表明的是:一行的规则,历经一百七十年也不会穷尽。棋子八个,棋盘一块。即便如此,人们仍会改变顺序,再一次重新摆放。

立在夜晚棋盘上的一个皇后(示意图・AI 生成)