跳转到内容

八皇后问题

维基百科，自由的百科全书
（重定向自N皇后問題）
abcdefgh
8
f8 white queen
d7 white queen
g6 white queen
a5 white queen
h4 white queen
b3 white queen
e2 white queen
c1 white queen
8
77
66
55
44
33
22
11
abcdefgh
八皇后问题的唯一对称解（重合于旋转和反射变换）

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

历史

[编辑]

八皇后问题最早是由国际象棋棋手马克斯·贝瑟尔（英语：Max Bezzel）（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）种摆放方法，但只有11×8 + 1×4 = 92个可行（皇后间互不攻击）的解。如果将旋转和对称的解归为一种的话，则一共有12个独立解，具体如下：

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

abcdefgh
8
d8 white queen
g7 white queen
c6 white queen
h5 white queen
b4 white queen
e3 white queen
a2 white queen
f1 white queen
8
77
66
55
44
33
22
11
abcdefgh
八皇后的楼梯解

独立解11具有额外的性质无三皇后在一线（英语：No-three-in-line problem）。

独立解3的旋转90°再反射的变体，体现了阶梯状模式而被称为“楼梯解”，n皇后问题对n ≥ 4可通过特定公式得到楼梯解[4][5]：

  1. 如果n除以6的余数不是2或者3，则这个列表简单的就是不大于n的所有偶数以及随后的所有奇数。
  2. 否则，写出偶数和奇数的单独列表，比如：(2, 4, 6, 8 – 1, 3, 5, 7)。
  3. 如果余数是2，在奇数列表中交换1和3并移动5到末尾，比如：(3, 1, 7, 5)。
  4. 如果余数是3，在偶数列表中移动2到末尾并在奇数列表中移动1和3到末尾，比如：(4, 6, 8, 2 – 5, 7, 9, 1, 3)。
  5. 将奇数列表附加在偶数列表之后并从左至右的在这些横行上放置皇后，比如：(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 all(x[1] != r+c and x[2] != r-c
                for x in pl[0])
        return ((pl[0]+[(c, r+c, r-c)], pl[1]-{c})
            for c in pl[1] if place(c))
    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
    def pipeline(pl, i):
        for ipl in q(pl, i):
            if i+1 < n:
                yield from pipeline(ipl, i+1) 
            else:
                yield [x[0] for x in ipl[0]]
    for i in fund_solut(pipeline(([], {*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[1] as $r 
        | $pl[2] as $cl | $cl[] | . as $c
        | def place: 
            all($pl[0][]; 
                .[1] != $r+$c and .[2] != $r-$c); 
          select(place)
        | [$pl[0]+[[$c, $r+$c, $r-$c]], $r+1, $cl-[$c]];
    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);
    def pipeline(n): 
        q | if n > 1 then pipeline(n-1) end;
    fund_solut([[], 0, [range(0; n)]] | pipeline(n)
        | .[0] | map(.[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"]

求可行解

[编辑]

Python语言

[编辑]

下面采用Python语言基于共享变量，生成八皇后问题的92个可行解： 

def queens(n):
    queue = [()]*n
    cs = [0]*n
    cl = [*range(0, n)]
    def q(r):
        def place(c): 
            return all(x[0] != r+c and x[1] != r-c
                for x in queue[0:r])
        for i, c in enumerate(cl):
            if place(c):
                queue[r] = (r+c, r-c)
                cs[r] = c
                del cl[i]
                yield None
                cl.insert(i, c)
    def toletter(x): 
        return 'abcdefghijklmnopqrstuvwxyz'[x]
    def pipeline(i):
        for _ in q(i):
            if i+1 < n:
                yield from pipeline(i+1)
            else:
                yield cs
    for i in (pipeline(0)):
        rl = sorted(toletter(v)+str(k+1) for k, v in enumerate(i))
        print(rl)
queens(8)

这里的算法核心环节是在生成器之间共享静态变量。将这段代码保存入queens.py文件中，下面演示其执行结果： 

$ 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']

还可以用下面的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] == down[r+c] == up[r-c] == False
        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 toletter(x): 
        return 'abcdefghijklmnopqrstuvwxyz'[x]
    def pipeline(i):
        for r in q(i):
            if i+1 < n:
                for s in pipeline(i+1):
                    yield r + s
            else:
                yield r
    for i in (pipeline(0)):
        rl = sorted(toletter(v)+str(k+1) for k, v in enumerate(i))
        print(rl)
queens(8)

这段代码的执行方式和结果同于前述。

下面是过程式Python代码，生成八皇后问题的92个可行解： 

def queens(n):
    cs = [0]*n
    ps = [0]*n
    cl = [*range(0, n)]
    down = [False]*(n*2-1)
    up = [False]*(n*2-1)
    flag = [True]*n
    def q(r):
        def place(c): 
            return down[r+c] == up[r-c] == False
        if flag[r]:
            p = 0
        else:
            c = cs[r]
            p = ps[r]+1
            cl.insert(ps[r], c)
            down[r+c] = up[r-c] = False
        for i, c in enumerate(cl[p:]):
            if place(c):
                cs[r] = c
                ps[r] = p+i
                del cl[p+i]
                down[r+c] = up[r-c] = True
                flag[r] = False
                return True
        flag[r] = True
        return False   
    def toletter(x): 
        return 'abcdefghijklmnopqrstuvwxyz'[x]
    def pipeline(i):
        while q(i):
            if i+1 < n:
                pipeline(i+1)
            else:
                rl = sorted(toletter(v)+str(k+1)
                    for k, v in enumerate(cs))
                print(rl)
    pipeline(0)
queens(8)

这段代码的执行方式和结果同于前述。

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 < n then
        suspend [q(i)] ||| pipeline(i+1)
    else 
        suspend [q(i)]
end
procedure q(r)
    suspend place(r, 1 to n)
end
procedure place(r, c)
    static col, up, down
    initial {
        col := list(n, 0) 
        down := list(n*2-1, 0)
        up := list(n*2-1, 0) 
    }
    if col[c] = down[r+c-1] = up[r-c+n] = 0 then
        suspend col[c] <- down[r+c-1] <- up[r-c+n] <- c
end

这里的算法核心环节是可逆赋值运算<-。将这段代码保存入queens.icn文件中，下面演示其执行结果并提取其前两个解： 

$ 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

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;
}

大众文化

[编辑]
  • 电脑游戏《第七访客》中，伊格（Ego，玩家）在史陶夫的府邸的游戏室里碰到的象棋问题正是八个皇后问题。[8]（pp. 48-49,289-290）

延伸阅读

[编辑]
  • 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）. 

参考资料

[编辑]
  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（英语：W. W. Rouse Ball） (1960) The Eight Queens Problem, in Mathematical Recreations and Essays, Macmillan, New York, pp 165-171.
  3. ^ 奥利-约翰·达尔, 艾兹赫尔·戴克斯特拉, 东尼·霍尔 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. ^ 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. 
  5. ^ 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.
  6. ^ Wirth, 1976, p. 145
  7. ^ N-Queens - LeetCode （页面存档备份，存于互联网档案馆）
  8. ^ 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）. 
检索自“https://zh.wikipedia.org/w/index.php?title=八皇后问题&oldid=86547331”