八皇后問題
| 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