八皇后問題

八皇后問題是一個以西洋棋為背景的問題：如何能夠在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｜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個獨立解：

```python
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`文件中，下面演示其執行結果：

```console
$ 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個獨立解：

```python
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`文件中，下面演示其執行結果：

```console
$ 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個可行解：

```icon
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] = 0 = down[r+c-1] = up[r-c+n] then
        suspend col[c] <- down[r+c-1] <- up[r-c+n] <- c
end
```

這裡的算法核心環節是可逆賦值運算`<-`。將這段代碼保存入`queens.icn`文件中，下面演示其執行結果並提取其`92`個解中的前兩個解：

```console
$ 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個可行解：

```python
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] 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 < 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`個解中的前兩個解：

```console
$ 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代碼，其執行方式和結果同於前述：

```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] 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 < 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)`的次數同上，共計`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代碼，其執行方式和結果同於前述：

```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] is False is 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代碼，其執行方式和結果同於前述：

```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] 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個皇后以及選擇是否列印出具體解。

```C
#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;
}
```

使用回溯法進行求解八皇后問題：

```C
#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語言程序。此程序找出了八皇后問題的一個解。

```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 < 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測試。

```Java
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++語言

```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，玩家）在史陶夫的府邸的游戲室裏碰到的象棋問題正是八個皇后問題。八皇后問題還在NDS平台的著名電子遊戲《雷頓教授與不可思議的小鎮》中出現。

## 延伸閱讀

- O.-J. Dahl, E. W. Dijkstra, C. A. R. Hoare Structured Programming, Academic Press, London, 1972 see pp. 72–82 for Dijkstra's solution of the 8 Queens problem.
- 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.

## 外部連結

- sblendorio/queens-cpm Eight Queens Puzzle in Turbo Pascal for CP/M
- gitpel/python-for-fun/blob/master/eight-queens.py Eight Queens Puzzle one line solution in Python
- Solutions in more than 100 different programming languages (on Rosetta Code)