八皇后問題
| 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 | ||
八皇后問題的唯一對稱解（重合於旋轉和反射變換）
| 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。
解題方法
[編輯]八個皇后在8x8棋盤上共有4,426,165,368（64C8）種擺放方法，但皇后間互不攻擊只有11×8 + 1×4 = 92個「可行解」。如果將在旋轉和反射下重合的可行解歸為一種的話，則一共有12個「獨立解」（fundamental solution），具體如下：
獨立解1
|
獨立解2
|
獨立解3
|
獨立解4
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
獨立解5
|
獨立解6
|
獨立解7
|
獨立解8
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
獨立解9
|
獨立解10
|
獨立解11
|
獨立解12
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
一個獨立解通常有8個變體（含其最初形式），可以先對其進行旋轉90°、180°和270°，加上其最初形式形成4個旋轉變體，再針對一個固定位置比如縱軸進行反射（字母p的垂直反射是字母q），從而得到8個變體。但獨立解10旋轉180°形式與最初形式重合，並且旋轉270°形式與旋轉90°形式重合，所以只有4種變體即自身及其反射和90°旋轉及其反射。
獨立解11具有額外的性質無三皇后在一線。
獨立解3的旋轉90°再垂直反射（效果同於45°反射）的變體，體現了階梯狀模式而被稱為「樓梯解」，n皇后問題對n ≥ 4可通過特定公式得到樓梯解[4][5]：
- 如果n除以6的餘數不是2或者3，則這個列表簡單的就是不大於n的所有偶數以及隨後的所有奇數。
- 否則，寫出偶數和奇數的單獨列表，比如：(2, 4, 6, 8 – 1, 3, 5, 7)。
- 如果餘數是2，在奇數列表中交換1和3並移動5到末尾，比如：(3, 1, 7, 5)。
- 如果餘數是3，在偶數列表中移動2到末尾並在奇數列表中移動1和3到末尾，比如：(4, 6, 8, 2 – 5, 7, 9, 1, 3)。
- 將奇數列表附加在偶數列表之後並從左至右的在這些橫行上放置皇后，比如：(a2, b4, c6, d8, e3, f1, g7, h5)。
八皇后問題的12個獨立解之間沒有由數學性質決定出的次序，這裏的獨立解次序和所採用的變體是求獨立解的特定搜索算法的輸出結果（第一個解在棋盤左下角或左上角有一個皇后），不加以人為調整，比如：將獨立解3的樓梯變體放在最前，將獨立解10放在最後等等。
解的個數
[編輯]下表給出了n皇后問題的解的個數包括獨立解U（OEIS數列A002562）以及可行解D（OEIS數列A000170）的個數：
| n | U | D |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 0 | 0 |
| 3 | 0 | 0 |
| 4 | 1 | 2 |
| 5 | 2 | 10 |
| 6 | 1 | 4 |
| 7 | 6 | 40 |
| 8 | 12 | 92 |
| 9 | 46 | 352 |
| 10 | 92 | 724 |
| 11 | 341 | 2,680 |
| 12 | 1,787 | 14,200 |
| 13 | 9,233 | 73,712 |
| 14 | 45,752 | 365,596 |
| 15 | 285,053 | 2,279,184 |
| 16 | 1,846,955 | 14,772,512 |
| 17 | 11,977,939 | 95,815,104 |
| 18 | 83,263,591 | 666,090,624 |
| 19 | 621,012,754 | 4,968,057,848 |
| 20 | 4,878,666,808 | 39,029,188,884 |
| 21 | 39,333,324,973 | 314,666,222,712 |
| 22 | 336,376,244,042 | 2,691,008,701,644 |
| 23 | 3,029,242,658,210 | 24,233,937,684,440 |
| 24 | 28,439,272,956,934 | 227,514,171,973,736 |
| 25 | 275,986,683,743,434 | 2,207,893,435,808,352 |
| 26 | 2,789,712,466,510,289 | 22,317,699,616,364,044 |
| 27 | 29,363,495,934,315,694 | 234,907,967,154,122,528 |
可以注意到六皇后問題的解的個數比五皇后問題的解的個數要少。現在還沒有已知公式可以對n計算n皇后問題的解的個數。
示例程序
[編輯]求獨立解
[編輯]Python語言
[編輯]下面採用Python語言在致力保持不可變性原則下，生成八皇后問題的12個獨立解：
def queens(n):
def q(pl, r):
def place(c):
return r+c not in pl[1] and r-c not in pl[2]
return ((pl[0]+[c], pl[1]|{r+c}, pl[2]|{r-c}, pl[3]-{c})
for c in pl[3] if place(c))
def pipeline(pl, i):
for ipl in q(pl, i):
if i+1 < n:
yield from pipeline(ipl, i+1)
else:
yield ipl[0]
def toletter(x):
return 'abcdefghijklmnopqrstuvwxyz'[x]
def fund_solut(fl):
def inversed(xl):
return (xl.index(i) for i in range(0, n))
def variants(xl):
rl = [xl]
rl += [[*inversed(x)] for x in rl]
rl += [[*reversed(x)] for x in rl]
rl += [[n-1-i for i in x] for x in rl]
return (''.join(toletter(i) for i in x) for x in rl)
rs = set()
for i in fl:
ks = {*variants(i)}
if rs.isdisjoint(ks):
rs |= ks
yield i
for i in fund_solut(
pipeline(([], set(), set(), {*range(0, n)}), 0)):
rl = sorted(toletter(v)+str(k+1) for k, v in enumerate(i))
print(rl)
queens(8)
這裏的算法核心環節是生成器委託yield from。將這段代碼保存入queens.py文件中，下面演示其執行結果：
$ python3 ./queens.py
['a1', 'b7', 'c5', 'd8', 'e2', 'f4', 'g6', 'h3']
['a1', 'b7', 'c4', 'd6', 'e8', 'f2', 'g5', 'h3']
['a6', 'b1', 'c5', 'd2', 'e8', 'f3', 'g7', 'h4']
['a4', 'b1', 'c5', 'd8', 'e2', 'f7', 'g3', 'h6']
['a5', 'b1', 'c8', 'd4', 'e2', 'f7', 'g3', 'h6']
['a3', 'b1', 'c7', 'd5', 'e8', 'f2', 'g4', 'h6']
['a5', 'b1', 'c4', 'd6', 'e8', 'f2', 'g7', 'h3']
['a7', 'b1', 'c3', 'd8', 'e6', 'f4', 'g2', 'h5']
['a5', 'b1', 'c8', 'd6', 'e3', 'f7', 'g2', 'h4']
['a5', 'b3', 'c1', 'd7', 'e2', 'f8', 'g6', 'h4']
['a5', 'b7', 'c1', 'd4', 'e2', 'f8', 'g6', 'h3']
['a6', 'b3', 'c1', 'd8', 'e4', 'f2', 'g7', 'h5']
jq語言
[編輯]下面採用純函數式程式語言jq，生成八皇后問題的12個獨立解：
def queens(n):
def q: . as $pl
| $pl[4] as $r
| $pl[3] as $cl | $cl[] | . as $c
| ($r+$c | tostring) as $k0
| ($r-$c | tostring) as $k1
| def place:
($k0 | in($pl[1]) | not)
and ($k1 | in($pl[2]) | not);
select(place)
| [$pl[0]+[$c], $pl[1]+{$k0:null},
$pl[2]+{$k1:null}, $cl-[$c], $r+1];
def pipeline(n):
q | if n > 1 then pipeline(n-1) end;
def toletter:
"abcdefghijklmnopqrstuvwxyz"[.:.+1];
def fund_solut(f):
def inverse: . as $xl
| reduce range(0; n) as $i
([]; .+[$xl | index($i)]);
def variants:
[., inverse] | map(., reverse)
| map(., map(n-1-.))
| map(map(toletter) | add);
foreach f as $i
([null, {}]; .[1] as $ml
| ($i | variants) as $nl
| if all($nl[]; in($ml) | not) then
[$i, ($ml | .[$nl[]]=null)]
else
[null, $ml] end;
.[0])
| select (. != null);
fund_solut([[], {}, {}, [range(0; n)], 0]
| pipeline(n) | .[0])
| map(toletter) | to_entries
| map(.value+(.key+1 | tostring)) | sort;
queens(8)
這裏的算法核心環節是管道機制。將這段代碼保存入queens.jq文件中，下面演示其執行結果：
$ jq -nc -f ./queens.jq
["a1","b7","c5","d8","e2","f4","g6","h3"]
["a1","b7","c4","d6","e8","f2","g5","h3"]
["a6","b1","c5","d2","e8","f3","g7","h4"]
["a4","b1","c5","d8","e2","f7","g3","h6"]
["a5","b1","c8","d4","e2","f7","g3","h6"]
["a3","b1","c7","d5","e8","f2","g4","h6"]
["a5","b1","c4","d6","e8","f2","g7","h3"]
["a7","b1","c3","d8","e6","f4","g2","h5"]
["a5","b1","c8","d6","e3","f7","g2","h4"]
["a5","b3","c1","d7","e2","f8","g6","h4"]
["a5","b7","c1","d4","e2","f8","g6","h3"]
["a6","b3","c1","d8","e4","f2","g7","h5"]
求可行解
[編輯]Icon語言
[編輯]下面採用Icon語言，生成八皇后問題的92個可行解：
這裏的算法核心環節是可逆賦值運算<-。將這段代碼保存入queens.icn文件中，下面演示其執行結果並提取其92個解中的前兩個解：
$ icon ./queens.icn | wc -l
92
$ icon ./queens.icn | sed -n '1,2p'
a1,b7,c5,d8,e2,f4,g6,h3
a1,b7,c4,d6,e8,f2,g5,h3
Python語言
[編輯]下面採用Python語言基於共享變量，生成八皇后問題的92個可行解：
def queens(n):
col = [False]*n
down = [False]*(n*2-1)
up = [False]*(n*2-1)
def q(r):
def place(c):
return col[c] == False == down[r+c] == up[r-c]
for c in range(0, n):
if place(c):
col[c] = down[r+c] = up[r-c] = True
yield [c]
col[c] = down[r+c] = up[r-c] = False
def pipeline(i):
for r in q(i):
if i+1 < n:
for s in pipeline(i+1):
yield r + s
else:
yield r
def toletter(x):
return 'abcdefghijklmnopqrstuvwxyz'[x]
for i in (pipeline(0)):
rl = sorted(toletter(v)+str(k+1)
for k, v in enumerate(i))
print(rl)
queens(8)
這裏的算法核心環節是在生成器之間共享靜態變量。將這段代碼保存入queens.py文件中，下面演示其執行結果並提取其92個解中的前兩個解：
$ python3 ./queens.py | wc -l
92
$ python3 ./queens.py | sed -n '1,2p'
['a1', 'b7', 'c5', 'd8', 'e2', 'f4', 'g6', 'h3']
['a1', 'b7', 'c4', 'd6', 'e8', 'f2', 'g5', 'h3']
這個算法在8個橫行上執行縱列選擇函數q(r)的次數分別為：[1, 8, 42, 140, 344, 568, 550, 312]，共計1965次，q(r)在每個橫行上針對縱列執行函數place(c)的次數都是8，每橫行的選擇數分別為：[8, 64, 336, 1120, 2752, 4544, 4400, 2496]，總計15720次，其中每橫行的成功存乎最終結果者之數分別為：[8, 36, 62, 80, 90, 90, 92, 92]，總計550個。
可以進一步將其寫為下面的Python代碼，其執行方式和結果同於前述：
def queens(n):
cs = [0]*n
cl = [*range(0, n)]
down = [False]*(n*2-1)
up = [False]*(n*2-1)
def q(r):
def place(c):
return down[r+c] == False == up[r-c]
for i, c in enumerate(cl):
if place(c):
cs[r] = c
del cl[i]
down[r+c] = up[r-c] = True
yield None
cl.insert(i, c)
down[r+c] = up[r-c] = False
def pipeline(i):
for _ in q(i):
if i+1 < n:
yield from pipeline(i+1)
else:
yield cs
def toletter(x):
return 'abcdefghijklmnopqrstuvwxyz'[x]
for i in (pipeline(0)):
rl = sorted(toletter(v)+str(k+1)
for k, v in enumerate(i))
print(rl)
queens(8)
這個算法在8個橫行上執行縱列選擇函數q(r)的次數分別為：[1, 8, 42, 140, 344, 568, 550, 312]，共計1965次，q(r)在8個橫行上針對縱列執行函數place(c)的次數分別為：[8, 7, 6, 5, 4, 3, 2, 1]，每橫行的選擇數分別為：[8, 56, 252, 700, 1376, 1704, 1100, 312]，總計5508次，其中每橫行的成功存乎最終結果者之數分別為：[8, 36, 62, 80, 90, 90, 92, 92]，總計550個。
下面將其寫為過程式Python代碼，其執行方式和結果同於前述：
def queens(n):
cs = [0]*n
cl = [*range(0, n)]
down = [False]*(n*2-1)
up = [False]*(n*2-1)
rl = ['']*n
toletter = lambda x: \
'abcdefghijklmnopqrstuvwxyz'[x]
def q(r):
if r < n:
for i, c in enumerate(cl):
if down[r+c] == False == up[r-c]:
cs[r] = c
del cl[i]
down[r+c] = up[r-c] = True
q(r+1)
cl.insert(i, c)
down[r+c] = up[r-c] = False
else:
for k, v in enumerate(cs):
rl[k] = toletter(v)+str(k+1)
print(sorted(rl))
q(0)
queens(8)
最後將其寫為指令式Python代碼，其執行方式和結果同於前述：
def queens(n):
cs = [0]*n
ps = [0]*n
cl = [*range(0, n)]
down = [False]*(n*2-1)
up = [False]*(n*2-1)
rl = ['']*n
toletter = lambda x: \
'abcdefghijklmnopqrstuvwxyz'[x]
r = 0
while r >= 0:
p = ps[r]
if p != 0:
c = cs[r]
cl.insert(p-1, c)
down[r+c] = up[r-c] = False
for i, c in enumerate(cl[p:]):
if down[r+c] == False == up[r-c]:
cs[r] = c
ps[r] = p+i+1
break
if p != ps[r]:
del cl[p+i]
down[r+c] = up[r-c] = True
r += 1
else:
ps[r] = 0
r -= 1
if r == n:
for k, v in enumerate(cs):
rl[k] = toletter(v)+str(k+1)
print(sorted(rl))
r -= 1
queens(8)
C語言
[編輯]下面是求解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);
return 0;
}
使用回溯法進行求解八皇后問題
#include<stdio.h>
#define PRINTF_IN 1 //定义是否打印，1：打印，0：不打印
int queens(int Queens){
int i, k, flag, not_finish=1, count=0;
//正在处理的元素下标，表示前i-1个元素已符合要求，正在处理第i个元素
int a[Queens+1]; //八皇后问题的皇后所在的行列位置，从1幵始算起，所以加1
i=1;
a[1]=1; //为数组的第一个元素赋初值
printf("%d皇后的可能配置是:",Queens);
while(not_finish){ //not_finish=l:处理尚未结束
while(not_finish && i<=Queens){ //处理尚未结束且还没处理到第Queens个元素
for(flag=1,k=1; flag && k<i; k++) //判断是否有多个皇后在同一行
if(a[k]==a[i])
flag=0;
for (k=1; flag&&k<i; k++) //判断是否有多个皇后在同一对角线
if( (a[i]==a[k]-(k-i)) || (a[i]==a[k]+(k-i)) )
flag=0;
if(!flag){ //若存在矛盾不满足要求，需要重新设置第i个元素
if(a[i]==a[i-1]){ //若a[i]的值已经经过一圈追上a[i-1]的值
i--; //退回一步，重新试探处理前一个元素
if(i>1 && a[i]==Queens)
a[i]=1; //当a[i]为Queens时将a[i]的值置1
else
if(i==1 && a[i]==Queens)
not_finish=0; //当第一位的值达到Queens时结束
else
a[i]++; //将a[il的值取下一个值
}else if(a[i] == Queens)
a[i]=1;
else
a[i]++; //将a[i]的值取下一个值
}else if(++i<=Queens)
if(a[i-1] == Queens )
a[i]=1; //若前一个元素的值为Queens则a[i]=l
else
a[i] = a[i-1]+1; //否则元素的值为前一个元素的下一个值
}
if(not_finish){
++count;
if(PRINTF_IN){
printf((count-1)%3 ? " [%2d]:" : "\n[%2d]:", count);
for(k=1; k<=Queens; k++) //输出结果
printf(" %d", a[k]);
}
if(a[Queens-1]<Queens )
a[Queens-1]++; //修改倒数第二位的值
else
a[Queens-1]=1;
i=Queens -1; //开始寻找下一个满足条件的解
}
}
return count;
}
int main()
{
int Num ;
printf("输入一个N皇后数值：");
scanf("%d" , &Num);
printf("\n%d皇后有%d种配置\n",Num,queens(Num));
}
Pascal語言
[編輯]以下列出尼克勞斯·維爾特的Pascal語言程序[6]。此程序找出了八皇后問題的一個解。
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.
Java語言
[編輯]使用回溯法進行求解八皇后問題(Java版本)，可直接複製到N-Queens - LeetCode[7]測試。
class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> results = new ArrayList<>();
// 使用 char[][] 是为了展示结果时，直接使用 new String(char[])。
// 一般情况下，使用 boolean[][] 即可。
char[][] result = new char[n][n];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
result[i][j] = '.';
}
}
backtrack(results, result, 0);
return results;
}
private static void backtrack(List<List<String>> results, char[][] result, int x) {
for (int j = 0; j < result.length; ++j) {
if (isValid(result, x, j)) {
result[x][j] = 'Q';
if (x == result.length - 1) {
showResult(results, result);
// 可以直接 break
} else {
// 皇后问题中，不会出现一行出现多个，所以直接跳到下一行
backtrack(results, result, x + 1);
}
result[x][j] = '.';
}
}
}
private static boolean isValid(char[][] result, int x, int y) {
// ... (0, y)
// ... ......
// ... (x-1, y)
// ... (x, y)
for (int i = 0; i < x; ++i) {
if (result[i][y] == 'Q') {
return false;
}
}
// ...
// ... (x-1, y-1)
// ... .......... (x, y)
for (int i = x - 1, j = y - 1; i >= 0 && j >= 0; --i, --j) {
if (result[i][j] == 'Q') {
return false;
}
}
// ...
// ... ...... (x-1, y+1)
// ... (x, y)
for (int i = x - 1, j = y + 1; i >= 0 && j < result.length; --i, ++j) {
if (result[i][j] == 'Q') {
return false;
}
}
return true;
}
private static void showResult(List<List<String>> results, char[][] result) {
List<String> list = new ArrayList<>(result.length);
for (char[] value : result) {
list.add(new String(value));
}
results.add(list);
}
}
C++語言
[編輯]#include "iostream"
#include "cmath"
using namespace std;
#define Max 20 //定義棋盤的最大值
int a[Max];
int show(int S) //定義出函數
{
int i,p,q;
int b[Max][Max]={0}; //定義且初始化b[1][]輸出模組
for(i=1;i<=S;i++) //按橫列順序輸出a[i]的座標
{
b[i][a[i]]=1;
printf("(%d,%d)\t",i,a[i]);
}
printf("\n");
for(p=1;p<=S;p++) //按棋盤的橫列的順序標明的位置
{
for(q=1;q<=S;q++)
{
if(b[p][q]==1) //在第p行第q列放置一顆棋子
printf("x");
else
printf("o");
}
printf("\n");
}
return 0;
}
int check(int k) //定義check函數
{
int i;
for(i=1;i<k;i++)
{
if((a[i]==a[k]) || (a[i]-a[k]==k-i)|| (a[i]-a[k]==i-k) ) //檢查是否有多顆棋子在同一個直行上
{
return 0;
}
}
return 1;
}
void check_m(int num) //定義函數
{
int k=1,count=0;
printf("N皇后問題的所有解(包含經由旋轉的解):\n");
a[k]=1;
while(k>0)
{
if(k<=num && a[k]<=num) //從第k行第一列的位置開始，尋找之後的棋子的位置
{
if(check(k)==0) //第k行的a[k]列不能放置棋子
{
a[k]++; //繼續試探該前行的下一列：a[k+1]
}
else
{
k++; //第K行的位置已經確定完畢，繼續尋找第k+1行棋子的位置
a[k]=1; //從第k+1的第一列開始查找
}
}
else
{
if(k>num) //若滿足輸出數組的要求就輸出該數組
{
count++;
printf("[%d]: ",count);
show(num); //調用輸出函數show()
}
k--; //棋子位置不符合要求則退回前一步
a[k]++; //繼續尋找下一列位置
}
}
printf("總共有 %d \n",count,"個");
}
int main(void)
{
int N,d;
do
{
printf(" N皇后問題的解(N<20) \n");
printf("請輸入N的值：_");
scanf("%d",&N);
printf("\n");
if(N>0&&N<20)
{
check_m(N);
break;
}
else
{
printf("輸入錯誤，請重新輸入");
printf("\n\n");
break;
}
}
while(1);
system("pause");
return 0;
}
大眾文化
[編輯]在1990年代初期的著名電腦游戲《第七訪客》中，伊格（Ego，玩家）在史陶夫的府邸的游戲室裏碰到的象棋問題正是八個皇后問題[8]（pp. 48-49,289-290）。八皇后問題還在NDS平台的著名電子遊戲《雷頓教授與不可思議的小鎮》中出現。
延伸閱讀
[編輯]- Bell, Jordan; Stevens, Brett. A survey of known results and research areas for n-queens. Discrete Mathematics. 2009, 309 (1): 1–31. doi:10.1016/j.disc.2007.12.043.
- Watkins, John J. Across the Board: The Mathematics of Chess Problems
. Princeton: Princeton University Press. 2004. ISBN 978-0-691-11503-0. - 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.
- Allison, L.; Yee, C.N.; McGaughey, M. Three Dimensional NxN-Queens Problems. Department of Computer Science, Monash University, Australia. 1988 [2021-03-23]. （原始內容存檔於2009-07-01）.
- Nudelman, S. The Modular N-Queens Problem in Higher Dimensions. Discrete Mathematics. 1995, 146 (1–3): 159–167. doi:10.1016/0012-365X(94)00161-5.
- Engelhardt, M. Der Stammbaum der Lösungen des Damenproblems (in German, means The pedigree chart of solutions to the 8-queens problem. Spektrum der Wissenschaft. August 2010: 68–71 [2022-02-19]. （原始內容存檔於2013-01-28）.
- On The Modular N-Queen Problem in Higher Dimensions （頁面存檔備份，存於互聯網檔案館）, Ricardo Gomez, Juan Jose Montellano and Ricardo Strausz (2004), Instituto de Matematicas, Area de la Investigacion Cientifica, Circuito Exterior, Ciudad Universitaria, Mexico.
- Wirth, Niklaus, Algorithms + Data Structures = Programs, Prentice-Hall Series in Automatic Computation (Prentice-Hall), 1976, Bibcode:1976adsp.book.....W, ISBN 978-0-13-022418-7
- Wirth, Niklaus. The Eight Queens Problem. Algorithms and Data Structures (PDF). Oberon version with corrections and authorized modifications. 2004: 114–118 [updated 2012] [2021-03-23]. （原始內容存檔 (PDF)於2021-04-17）.
參考資料
[編輯]- ^ 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.
- ^ Bo Bernhardsson. Explicit Solutions to the N-Queens Problem for All N. ACM SIGART Bulletin. 1991, 2 (2): 7. S2CID 10644706. doi:10.1145/122319.122322.
- ^ Hoffman, E. J.; Loessi, J. C.; Moore, R. C. Constructions for the Solution of the m Queens Problem. Mathematics Magazine. 1969-03-01, 42 (2): 66. JSTOR 2689192. doi:10.2307/2689192 （英語）. 互聯網檔案館的存檔，存檔日期8 November 2016.
- ^ Wirth, 1976, p. 145
- ^ N-Queens - LeetCode （頁面存檔備份，存於互聯網檔案館）
- ^ DeMaria, Rusel. The 7th Guest: The Official Strategy Guide (PDF). Prima Games. 1993-11-15 [2021-04-22]. ISBN 978-1559584685. （原始內容存檔 (PDF)於2021-04-22）.
外部連結
[編輯]
維基教科書中的相關電子教學：Miscellaneous/N-Queens
- 埃里克·韋斯坦因. Queens Problem. MathWorld.
- GitHub上的queens-cpm頁面 Eight Queens Puzzle in Turbo Pascal for CP/M
- GitHub上的eight-queens.py頁面 Eight Queens Puzzle one line solution in Python
- Solutions in more than 100 different programming languages (on Rosetta Code)