编辑代码

#include <stdio.h>
#include <math.h>
//递归算法-回溯-N皇后
/*要求在一个nxn格的棋盘上放置n个皇后，使得任何两个皇后不能被放在同一行或同一列或同一条斜线上*/

//常量
#define N 4
//存储皇后的列号，一维数组，下标代表行号（两个皇后不能被放在同一行或同一列或同一条斜线上）
int q[N + 1];
int answer = 0;
//检查第j个皇后的位置是否合法
int check(int j){
    int i;
    for (i=1;i<j;i++){
        //是否同一列 q[i] == q[j]；是否同一斜线-正反 abs(i-j) == abs( q[i] - q[j])
        if(q[i] == q[j] || abs(i-j) == abs( q[i] - q[j])){
            return 0;//不合法
        }
    }
    return 1;//合法
}
void showLog(){
    int i;
    printf("%d 皇后-方案%d：", N, answer);
    for(i = 1; i<= N; i++){
        printf("%d ",q[i]);//打印方案
    }
    printf("\n");
}
//求解 N皇后方案
void queen(int j){//j=行号
    int i;
    for(i = 1; i <= N; i++){//i=列号
        q[j] = i;
        if(check(j)){//当前第 j 个皇后 找到一个合法的摆放位置
            if(j == N){// 找到了 N皇后的一组解
                answer = answer + 1;
                showLog();
            }else{//通过递归 自动回溯
                queen(j + 1);//递归摆放下一个皇后的位置
            }
        }
    }
}
int main () {
    printf("递归算法-回溯-N皇后     - c.jsrun.net.\n");
    queen(1);
/*方案1：2 4 1 3 
方案2：3 1 4 2*/
    return 0;
}