八皇后问题
| a | b | c | d | e | f | g | h | ||
| 8 |   | 8 | |||||||
| 7 | 7 | ||||||||
| 6 | 6 | ||||||||
| 5 | 5 | ||||||||
| 4 | 4 | ||||||||
| 3 | 3 | ||||||||
| 2 | 2 | ||||||||
| 1 | 1 | ||||||||
| a | b | c | d | e | f | g | h | ||
八皇后问题是一个以国际象棋为背景的问题：如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。当且仅当n = 1或n ≥ 4时问题有解[1]。
历史
八皇后问题最早是由西洋棋棋手马克斯·贝瑟尔（Max Bezzel）于1848年提出。第一个解在1850年由弗朗兹·诺克（Franz Nauck）给出。并且将其推广为更一般的n皇后摆放问题。诺克也是首先将问题推广到更一般的n皇后摆放问题的人之一。
在此之后，陆续有数学家对其进行研究，其中包括高斯和康托，1874年，S.冈德尔提出了一个通过行列式来求解的方法[2]，这个方法后来又被J.W.L.格莱舍加以改进。
1972年，艾兹格·迪杰斯特拉用这个问题为例来说明他所谓结构化编程的能力[3]。他对深度优先搜索回溯算法有着非常详尽的描述2。
八皇后问题在1990年代初期的著名电子游戏第七访客和NDS平台的著名电子游戏《雷顿教授与不可思议的小镇》中都有出现。
解题方法
八个皇后在8x8棋盘上共有4,426,165,368（64C8）种摆放方法，但只有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 | .. |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| U | 1 | 0 | 0 | 1 | 2 | 1 | 6 | 12 | 46 | 92 | 341 | 1,787 | 9,233 | 45,752 | .. |
| D | 1 | 0 | 0 | 2 | 10 | 4 | 40 | 92 | 352 | 724 | 2,680 | 14,200 | 73,712 | 365,596 | .. |
可以注意到六皇后问题的解的个数比五皇后问题的解的个数要少。现在还没有已知公式可以对n计算n皇后问题的解的个数。
示例程序
下面是求解n皇后的C代码，在程序中可以自己设置n个皇后以及选择是否打印出具体解。
#include <stdio.h>
#define QUEENS 8 /*皇后数量*/
#define IS_OUTPUT 1 /*(IS_OUTPUT=0 or 1)，Output用于选择是否输出具体解,为1输出，为0不输出*/
int A[QUEENS + 1], B[QUEENS * 3 + 1], C[QUEENS * 3 + 1], k[QUEENS + 1][QUEENS + 1];
int inc, *a = A, *b = B + QUEENS, *c = C;
void lay(int i) {
int j = 0, t, u;
while (++j <= QUEENS)
if (a[j] + b[j - i] + c[j + i] == 0) {
k[i][j] = a[j] = b[j - i] = c[j + i] = 1;
if (i < QUEENS) lay(i + 1);
else {
++inc;
if (IS_OUTPUT) {
for (printf("(%d)\n", inc), u = QUEENS + 1; --u; printf("\n"))
for (t = QUEENS + 1; --t; ) k[t][u] ? printf("Q ") : printf("+ ");
printf("\n\n\n");
}
}
a[j] = b[j - i] = c[j + i] = k[i][j] = 0;
}
}
int main(void) {
lay(1);
printf("%d皇后共计%d个解\n", QUEENS, inc);
getchar();
return 0;
}
以下列出尼克劳斯·维尔特的Pascal语言程序[4]。此程序找出了八皇后问题的一个解。
program eightqueen1(output);
var i : integer; q : boolean;
a : array[ 1 .. 8] of boolean;
b : array[ 2 .. 16] of boolean;
c : array[ -7 .. 7] of boolean;
x : array[ 1 .. 8] of integer;
procedure try( i : integer; var q : boolean);
var j : integer;
begin
j := 0;
repeat
j := j + 1;
q := false;
if a[ j] and b[ i + j] and c[ i - j] then
begin
x[ i ] := j;
a[ j ] := false;
b[ i + j] := false;
c[ i - j] := false;
if i < 8 then
begin
try( i + 1, q);
if not q then
begin
a[ j] := true;
b[ i + j] := true;
c[ i - j] := true;
end
end
else
q := true
end
until q or (j = 8);
end;
begin
for i := 1 to 8 do a[ i] := true;
for i := 2 to 16 do b[ i] := true;
for i := -7 to 7 do c[ i] := true;
try( 1, q);
if q then
for i := 1 to 8 do write( x[ i]:4);
writeln
end.
參考資料
- ^ Watkins, John J. (2004). Across the Board: The Mathematics of Chess Problems. Princeton: Princeton University Press. ISBN 0-691-11503-6
- ^ W. W. Rouse Ball (1960) The Eight Queens Problem, in Mathematical Recreations and Essays, Macmillan, New York, pp 165-171.
- ^ 奧利-約翰·達爾, 艾兹赫尔·戴克斯特拉, 東尼·霍爾 Structured Programming, Academic Press, London, 1972 ISBN 0-12-200550-3 see pp 72-82 for Dijkstra's solution of the 8 Queens problem.
- ^ Wirth, 1976, p. 145