八皇后问题

维基百科,自由的百科全书
跳转至: 导航搜索


a b c d e f g h
8
Chessboard480.svg
f8 白 后
d7 白 后
g6 白 后
a5 白 后
h4 白 后
b3 白 后
e2 白 后
c1 白 后
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个独立解,具体如下:


a b c d e f g h
8
Chessboard480.svg
d8 白 后
g7 白 后
c6 白 后
h5 白 后
b4 白 后
e3 白 后
a2 白 后
f1 白 后
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
独立解1


a b c d e f g h
8
Chessboard480.svg
e8 白 后
b7 白 后
d6 白 后
g5 白 后
c4 白 后
h3 白 后
f2 白 后
a1 白 后
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
独立解2


a b c d e f g h
8
Chessboard480.svg
d8 白 后
b7 白 后
g6 白 后
c5 白 后
f4 白 后
h3 白 后
e2 白 后
a1 白 后
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
独立解3


a b c d e f g h
8
Chessboard480.svg
d8 白 后
f7 白 后
h6 白 后
c5 白 后
a4 白 后
g3 白 后
e2 白 后
b1 白 后
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
独立解4


a b c d e f g h
8
Chessboard480.svg
c8 白 后
f7 白 后
h6 白 后
a5 白 后
d4 白 后
g3 白 后
e2 白 后
b1 白 后
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
独立解5


a b c d e f g h
8
Chessboard480.svg
e8 白 后
c7 白 后
h6 白 后
d5 白 后
g4 白 后
a3 白 后
f2 白 后
b1 白 后
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
独立解6


a b c d e f g h
8
Chessboard480.svg
e8 白 后
g7 白 后
d6 白 后
a5 白 后
c4 白 后
h3 白 后
f2 白 后
b1 白 后
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
独立解7


a b c d e f g h
8
Chessboard480.svg
d8 白 后
a7 白 后
e6 白 后
h5 白 后
f4 白 后
c3 白 后
g2 白 后
b1 白 后
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
独立解8


a b c d e f g h
8
Chessboard480.svg
c8 白 后
f7 白 后
d6 白 后
a5 白 后
h4 白 后
e3 白 后
g2 白 后
b1 白 后
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
独立解9


a b c d e f g h
8
Chessboard480.svg
f8 白 后
b7 白 后
g6 白 后
a5 白 后
d4 白 后
h3 白 后
e2 白 后
c1 白 后
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
独立解10


a b c d e f g h
8
Chessboard480.svg
d8 白 后
g7 白 后
a6 白 后
h5 白 后
e4 白 后
b3 白 后
f2 白 后
c1 白 后
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
独立解11


a b c d e f g h
8
Chessboard480.svg
f8 白 后
d7 白 后
g6 白 后
a5 白 后
h4 白 后
b3 白 后
e2 白 后
c1 白 后
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
独立解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皇后问题的解的个数。

示例程序[编辑]

以下列出尼克劳斯·维尔特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.

參考資料[编辑]

  1. ^ Watkins, John J. (2004). Across the Board: The Mathematics of Chess Problems. Princeton: Princeton University Press. ISBN 0-691-11503-6
  2. ^ W. W. Rouse Ball (1960) The Eight Queens Problem, in Mathematical Recreations and Essays, Macmillan, New York, pp 165-171.
  3. ^ 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.
  4. ^ Wirth, 1976, p. 145