八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：
在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

思路：

  1. 一维数组array存放皇后位置，array[i]=j 表示i行j列有一个皇后。
  2. 判断该位置放置皇后是否合法。
  3. 该位置合法，则进行下一行放置。
  4. 该位置非法则列值j++，进行第2步的判断。
  5. 当放满8个皇后(即i从0–>7)时，找到结果+1。
  6. 当某行中的列值(即array[i])>=8时，说明该行在前面行的摆放情况下无解。
  7. 则回退到上一行，对上一行的列值j++，进行2步判断。
  8. 当row回退到第一行(i=0)，且第一行的列值超出范围(array[0]>=8)时，代表搜索结束。
  9. 输出所有可行解。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <stdio.h>
#include <stdlib.h>

#define N 8

int check(int *q, int row)
{
    if(row == 0)
    {
        return 1;
    }
    else
    {
        int y;
        int x0 = q[row]; /* row行的列值 */
        for(y = 0; y < row; y++)
        {
            int x = q[y];   /* 前row行每列的值 */
            if(x == x0)     /* 列值不能相同 */
                return 0;
            else if(x - x0 == row - y)  /* 对角线方向1 */
                return 0;
            else if(x0 - x == row - y)  /* 对角线方向2 */
                return 0;
        }
    }
    return 1;
}

int queen()
{
    /****************************************
      q[N]记录各行可行的摆放位置。下标是行坐标，
      对应下标存储的值是可行解的列坐标。
    *****************************************/
    int q[N]    = {0};
    int found   = 0;    /* 记录可行解的个数 */
    int row     = 0;    /* 行 */
    int done    = 0;

    while(done == 0)
    {
        if(check(q, row))
        {
            if(row == N-1)  /* 所有位置都可行后，得到一个解 */
            {
                found++;
            }
            else
            {
                row++;      /* 新一行 */
                q[row] = 0;
                continue;
            }
        }
        q[row] += 1;        /* 列值+1 */
        while(q[row] >= N)  /* 当前行的列超出范围时 */
        {
            row--;          /* 上一行 */
            if(row >= 0)
            {
                q[row]++;   /* 对应行的列值+1 */
            }
            else            /* row < 0寻找结束 */
            {
                done = 1;
                break;
            }
        }
    }
    return found;
}

int main()
{
    int found;
    found = queen();
    printf("found = %d\n",found);
    return 0;
}

递归版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int search(int *array, int row)
{
    int count = 0;
    int i;
    for(i = 0; i < N; i++)
    {
        array[row] = i;
        if(check(array, row))
        {
            if(row == N - 1)
            {
                count++;
            }
            else
            {
                count += search(array, row + 1);
            }
        }
    }
    return count;
}

int queen()
{
    int array[N] = {0};
    return search(array, 0);
}