八皇后问题

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

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

历史[编辑]

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

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

八皇后问题在1990年代初期的著名电子游戏第七访客NDS平台的著名电子游戏雷顿教授与不可思议的小镇中都有出现。

八皇后問題的解[编辑]

八皇后问题一共有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皇后问题的解的个数。

參考資料[编辑]

  1. ^ Watkins, John J. (2004). Across the Board: The Mathematics of Chess Problems. Princeton: Princeton University Press. ISBN 0-691-11503-6
  2. ^ 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.