八皇后问题

八皇后问题的一个解

八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。当且仅当 n = 1 或 n ≥ 4 时问题有解。

历史

八皇后问题最早是由国际西洋棋棋手马克斯·贝瑟尔于1848年提出。之后陆续有数学家对其进行研究，其中包括高斯和康托，并且将其推广为更一般的n皇后摆放问题。八皇后问题的第一个解是在1850年由弗朗兹·诺克给出的。诺克也是首先将问题推广到更一般的n皇后摆放问题的人之一。1874年，S.冈德尔提出了一个通过行列式来求解的方法，这个方法后来又被J.W.L.格莱舍加以改进。

艾兹格·迪杰斯特拉在1972年用这个问题为例来说明他所谓结构性编程的能力²。

八皇后问题出现在1990年代初期的著名电子游戏第七访客中。

八皇后問題的解

八皇后问题一共有 92 个互不相同的解。如果将旋转和对称的解归为一种的话，则一共有12个独立解，具体如下：

独立解1	独立解2	独立解3
独立解4	独立解5	独立解6
独立解7	独立解8	独立解9
独立解10	独立解11	独立解12

解的个数

下表给出了 n 皇后问题的解的个数包括独立解U（OEIS中的数列A002562）以及互不相同的解D（OEIS中的数列A000170）的个数：

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	..	24	25	26
U:	1	0	0	1	2	1	6	12	46	92	341	1,787	9,233	45,752	..	28,439,272,956,934	275,986,683,743,434	2,789,712,466,510,289
D:	1	0	0	2	10	4	40	92	352	724	2,680	14,200	73,712	365,596	..	227,514,171,973,736	2,207,893,435,808,352	22,317,699,616,364,044

可以注意到六皇后问题的解的个数比五皇后问题的解的个数要少。现在还没有已知公式可以对 n 计算 n 皇后问题的解的个数。

參考資料

• Watkins, John J. (2004). Across the Board: The Mathematics of Chess Problems. Princeton: Princeton University Press. ISBN 0-691-11503-6.
• O.-J. Dahl, E. W. Dijkstra, C. A. R. Hoare Structured Programming, Academic Press, London, 1972 ISBN 0-12-200550-3 see pp 72-82 for Dijkstra's solution of the 8 Queens problem.