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

历史
八皇后问题最早是由西洋棋棋手（Max Bezzel）于1848年提出。第一个解在1850年由弗朗兹·诺克（Franz Nauck）给出。并且将其推广为更一般的n皇后摆放问题。诺克也是首先将问题推广到更一般的n皇后摆放问题的人之一。

在此之后，陆续有数学家对其进行研究，其中包括高斯和康托，1874年，S.冈德尔提出了一个通过行列式来求解的方法，这个方法后来又被J.W.L.格莱舍加以改进。

1972年，艾兹格·迪杰斯特拉用这个问题为例来说明他所谓结构化编程的能力。他对深度优先搜索回溯算法有着非常详尽的描述2。

解题方法
八个皇后在8x8棋盘上共有4,426,165,368（64C8）种摆放方法，但皇后間互不攻擊只有11×8 + 1×4 = 92个“可行解”。如果将在旋转和反射下重合的可行解归为一种的话，则一共有12个“独立解”（fundamental solution），具体如下：

一个独立解通常有8个变体（含其最初形式），可以先对其进行旋转90°、180°和270°，加上其最初形式形成4个旋转变体，再针对一个固定位置比如纵轴进行反射（字母p的垂直反射是字母q），从而得到8个变体。但独立解10旋转180°形式与最初形式重合，并且旋转270°形式与旋转90°形式重合，所以只有4种变体即自身及其反射和90°旋转及其反射。

独立解11具有额外的性质。

独立解3的旋转90°再垂直反射（效果同于45°反射）的变体，体现了阶梯状模式而被称为“楼梯解”，n皇后问题对n ≥ 4可通过特定公式得到楼梯解：

如果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以及可行解D的个数：

可以注意到六皇后问题的解的个数比五皇后问题的解的个数要少。现在还没有已知公式可以对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
这里的算法核心环节是生成器委托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个可行解：

global n
procedure main()
local i, r, s, u, v, x
n := 8
s := "abcdefghijklmnopqrstuvwxyz"
every x := pipeline(1) do {
r := []
every i := 1 to n do put(r, s[x[i]] || i)
u := sort(r)
v := get(u)
every v ||:= "," || !u
write(v)
}
end
procedure pipeline(i)
if i
这里的算法核心环节是可逆赋值运算。将这段代码保存入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](n2-1)
up = [False](n2-1)
def q(r):
def place(c):
return col[c] is False is down[r+c] is 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
这里的算法核心环节是在生成器之间共享静态变量。将这段代码保存入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](n2-1)
up = [False](n2-1)
def q(r):
def place(c):
return down[r+c] is False is 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
这个算法在8个横行上执行纵列选择函数q(r)的次数同上，共计1965次，q(r)在8个横行上针对纵列执行函数place(c)的次数分别为：[8, 7, 6, 5, 4, 3, 2, 1]，每横行的选择数分别为：[8, 56, 252, 700, 1376, 1704, 1100, 312]，总计5508次，其中每横行的成功存乎最终结果者之数同上，总计550个。

下面将其写为过程式Python代码，其执行方式和结果同于前述：

def queens(n):
cs = [0]*n
cl = [*range(0, n)]
down = [False](n2-1)
up = [False](n2-1)
rl = []n
toletter = lambda x: \
'abcdefghijklmnopqrstuvwxyz'[x]
def q(r):
if r
最后将其写为指令式Python代码，其执行方式和结果同于前述：

def queens(n):
cs = [0]*n
ps = [0]*n
cl = [*range(0, n)]
down = [False](n2-1)
up = [False](n2-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] is False is 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

#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

使用回溯法进行求解八皇后问题：

#include

#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 && i1 && 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

Pascal语言
以下列出尼克劳斯·维尔特的Pascal语言程序。此程序找出了八皇后问题的一个解。

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

Java语言
使用回溯法进行求解八皇后问题(Java版本)，可直接复制到N-Queens - LeetCode测试。

class Solution {

public List> solveNQueens(int n) {
List> results = new ArrayList<>();
// 使用 char[][] 是为了展示结果时，直接使用 new String(char[])。
// 一般情况下，使用 boolean[][] 即可。
char[][] result = new char[n][n];
for (int i = 0; i results, char[][] result, int x) {
for (int j = 0; j = 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 results, char[][] result) {
List 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;i0) {
if (knum) { //若滿足輸出數組的要求就輸出該數組
count++;
printf("[%d]: ",count);
show(num); //調用輸出函數show()
}
k--; //棋子位置不符合要求則退回前一步
a[k]++; //繼續尋找下一列位置
}
}
printf("總共有 %d \n",count,"個");
}

int main(void)
{
int N,d;
do {
printf(" N皇后問題的解(N0&&N

大众文化
在1990年代初期的著名電腦游戲《第七訪客》中，伊格（Ego，玩家）在史陶夫的府邸的游戲室裏碰到的象棋問題正是八個皇后問題。八皇后问题还在NDS平台的著名电子游戏《雷顿教授与不可思议的小镇》中出现。

八皇后问题

如果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)。

评论 (0)