递归回溯解N皇后问题

#include<stdio.h>
#include<stdlib.h>
#define N 16//最多皇后数量
int q[N];//存放皇后的行列位置，下标为行，值是列
int cnt=0;//存放解的总个数
void dispasolution(int n){//解出n皇后的一个解
    printf("第%d个解:",++cnt);
    for(int i=1;i<=n;i++)
        printf("(%d,%d) ",i,q[i]);
    printf("\n");
}
bool place (int i,int j){//从第一行测试(i,j)位置能否摆放皇后
    if(i==1)
        return true;
    int k=1;
    while(k<i){
        if((q[k]==j)||(abs(q[k]-j)==abs(i-k)))
        //三角形两直角边长度不同，底(对角线)长度也不同，即不在同一对角线上
            return false;//不符合条件则回溯
        k++;//从第一行开始依次测试
    }
    return true;//符合条件则继续
}
void queen(int i,int n){//放置1~i的皇后
    if(i>n)//但递归到达最后一行时，i>n，说明该情况可行，直接输出
        dispasolution(n);
    else{
        for(int j=1;j<=n;j++)//j是列坐标，循环测试当前递归层的每一列可行性
            if(place(i,j)){
                q[i]=j;//存储当前行皇后的列坐标
                queen(i+1,n);
                //递归每一种情况，如果下一行无法放置皇后不满足if条件则结束递归并返回上一层循环并重新递归尝试该行其他列
            }
    }
}
int main(){
    int n;
    printf("皇后问题(n<16)请输入n值:");
    scanf("%d",&n);
    if(n>16)
        printf("n值太大，我不想运行\n");
    else{
        printf("%d皇后问题求解结果如下：\n",n);
        queen(1,n);//房子1~n的皇后
    }
}

图1

以上图为例(该图情况是不可通的)，该算法的过程是默认从第一行第一列开始放第一个皇后，然后开始递归(皇后数N即为递归层数)下一层，循环测试该行每列是否可行，有可行的列则进行下一层循环，所有列都不可行则结束当前递归，返回上一行重新选择另一列进行递归。直到递归到最后一行，也就是i==N,说明该解法可行，并输出该解。然后返回上一层循环，尝试剩余的所有列，直到第一层递归的循环结束，则说明所有解法均已走完，程序结束。

补充:该种解法的时间复杂度是O(n!)，第一行n种情况，第二行n-1种...第n行1种，所以一共n(n-1)...1=n!。

-------该算法摘自《算法设计与分析(第2版)》