八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于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
#include <stdio.h>
2
#include <stdlib.h>
3
4
#define N 8
5
6
int check(int *q, int row)
7
{
8
    if(row == 0)
9
    {
10
        return 1;
11
    }
12
    else
13
    {
14
        int y;
15
        int x0 = q[row]; /* row行的列值 */
16
        for(y = 0; y < row; y++)
17
        {
18
            int x = q[y];   /* 前row行每列的值 */
19
            if(x == x0)     /* 列值不能相同 */
20
                return 0;
21
            else if(x - x0 == row - y)  /* 对角线方向1 */
22
                return 0;
23
            else if(x0 - x == row - y)  /* 对角线方向2 */
24
                return 0;
25
        }
26
    }
27
    return 1;
28
}
29
30
int queen()
31
{
32
    /****************************************
33
      q[N]记录各行可行的摆放位置。下标是行坐标，
34
      对应下标存储的值是可行解的列坐标。
35
    *****************************************/
36
    int q[N]    = {0};
37
    int found   = 0;    /* 记录可行解的个数 */
38
    int row     = 0;    /* 行 */
39
    int done    = 0;
40
41
    while(done == 0)
42
    {
43
        if(check(q, row))
44
        {
45
            if(row == N-1)  /* 所有位置都可行后，得到一个解 */
46
            {
47
                found++;
48
            }
49
            else
50
            {
51
                row++;      /* 新一行 */
52
                q[row] = 0;
53
                continue;
54
            }
55
        }
56
        q[row] += 1;        /* 列值+1 */
57
        while(q[row] >= N)  /* 当前行的列超出范围时 */
58
        {
59
            row--;          /* 上一行 */
60
            if(row >= 0)
61
            {
62
                q[row]++;   /* 对应行的列值+1 */
63
            }
64
            else            /* row < 0寻找结束 */
65
            {
66
                done = 1;
67
                break;
68
            }
69
        }
70
    }
71
    return found;
72
}
73
74
int main()
75
{
76
    int found;
77
    found = queen();
78
    printf("found = %d\n",found);
79
    return 0;
80
}

递归版本：

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