回溯法（八皇后问题）

  回溯法解题思路
（1）针对所给问题，定义问题的解空间； 　　
（2）确定易于搜索的解空间结构； 　　
（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

回溯就是让计算机自动的去搜索，碰到符合的情况就结束或者保存起来，在一条路径上走到尽头也不能找出解，就回到原来的岔路口，选择一条以前没有走过的路继 续探测，直到找到解或者走完所有路径为止。就这一点，回溯和所谓的DFS（深度优先搜索）是一样的。那现在的关键是，怎么实现搜索呢？回溯既然一般使用递 归来实现，那个这个递归调用该如何来写呢？我现在的理解就是，进行回溯搜索都会有一系列的步骤，每一步都会进行一些查找。而每一步的情况除了输入会不一样 之外，其他的情况都是一致的。这就刚好满足了递归调用的需求。通过把递归结束的条件设置到搜索的最后一步，就可以借用递归的特性来回溯了。因 为合法的递归调用总是要回到它的上一层调用的，那么在回溯搜索中，回到上一层调用就是回到了前一个步骤。当在当前步骤找不到一种符合条件情况时，那么后续 情况也就不用考虑了，所以就让递归调用返回上一层（也就是回到前一个步骤）找一个以前没有尝试过的情况继续进行。当然有时候为了能够正常的进行继续搜索， 需要恢复以前的调用环境。

/*
     * 回溯法解N皇后问题
     * 使用一个一维数组表示皇后的位置
     * 其中数组的下标表示皇后所在的行
     * 数组元素的值表示皇后所在的列
     * 这样设计的棋盘，所有皇后必定不在同一行
     *
     * 假设前n-1行的皇后已经按照规则排列好
     * 那么可以使用回溯法逐个试出第n行皇后的合法位置
     * 所有皇后的初始位置都是第0列
     * 那么逐个尝试就是从0试到N-1
     * 如果达到N，仍未找到合法位置
     * 那么就置当前行的皇后的位置为初始位置0
     * 然后回退一行，且该行的皇后的位置加1，继续尝试
     * 如果目前处于第0行，还要再回退，说明此问题已再无解
     *
     * 如果当前行的皇后的位置还是在0到N-1的合法范围内
     * 那么首先要判断该行的皇后是否与前几行的皇后互相冲突
     * 如果冲突，该行的皇后的位置加1，继续尝试
     * 如果不冲突，判断下一行的皇后
     * 如果已经是最后一行，说明已经找到一个解，输出这个解
     * 然后最后一行的皇后的位置加1，继续尝试下一个解
     */
    #define MAX_LENGTH 1024
    /*
     * 检查第n行的皇后与前n-1行的皇后是否有冲突
     * 发生冲突的充分必要条件是：
     * a) 两皇后处于同一列，即a[i] == a[n]
     * b) 两皇后处于同一斜线，即|a[i] - a[n]| == |i - n| == n - i
     */
    int is_conflict(int *a, int n) {
        int flag = 0;
        int i;
        for ( i = 0; i < n; i++ ) {
            if ( a[i] == a[n] || a[i] - a[n] == n - i || a[n] - a[i] == n - i ) {
                flag = 1;
                break;
            }
        }
        return flag;
    }
    /*
     * 输出皇后的排列
     */
    void print_board(int *a, int n) {
        int i, j;
        for ( i = 0; i < n; i++ ) {
            for ( j = 0; j < a[i]; j++ ) {
                printf(" ");
            }
            printf("Q");
            for ( j = a[i] + 1; j < n; j++ ) {
                printf(" ");
            }
            printf("/n");
        }
        printf("--------/n");
    }
    /*
     * 初始化棋盘，所有皇后都在第0列
     */
    void init_board(int *a, int n) {
        int i;
        for ( i = 0; i < n; i++ ) {
            a[i] = 0;
        }
    }
    /*
     * 解决N皇后问题
     */
    int queen(int n) {
        int count = 0;
        int a[MAX_LENGTH];
        init_board(a, n);
        int i = 0;
        while ( 1 ) {
            if ( a[i] < n ) {
                // 如果皇后的位置尚未超出棋盘范围
                // 需要检查第i行的皇后是否与前i-1行的皇后冲突
                if ( is_conflict(a, i) ) {
                    // 如果冲突，尝试下一个位置
                    a[i]++;
                    continue;
                }
                if ( i >= n - 1 ) {
                    // 如果已经到最后一行，也即找到一个解，首先输出它
                    count++;
                    print_board(a, n);
                    // 然后尝试当前行的皇后的下一个位置
                    a[n-1]++;
                    continue;
                }
                // 没有冲突，尝试下一行
                i++;
                continue;
            }
            else {
                // 皇后的位置已经超出棋盘范围
                // 那么该行的皇后复位
                a[i] = 0;
                // 回退到上一行
                i--;
                if ( i < 0 ) {
                    // 已经不能再退了，函数结束
                    return count;
                }
                // 尝试上一行的皇后的下个位置
                a[i]++;
                continue;
            }
        }
    }
    int main(void) {
        int n = 8;
        int count = queen(n);
        printf("%d solutions in %d queens problem\n", count, n);
        return 0;
    }