编辑代码

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

//常量
#define N 4
//存储皇后的列号，一维数组，下标代表行号（两个皇后不能被放在同一行或同一列或同一条斜线上）
int q[N + 1];
//检查第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 answer){
    int i;
    printf("%d 皇后-方案%d：", N, answer);
    for(i = 1; i<= N; i++){
        printf("%d ",q[i]);//打印方案
    }
    printf("\n");
}
//求解 N皇后方案
void queen(){
    int i;
    for(i = 1; i<= N; i++){
        q[i] = 0;//>>>>>>>初始化 一维数组，都为0
    }
    int answer = 0;//方案数
    int j = 1; //正在摆放第 j 个皇后，值=行号
    while(j >= 1){//如果第一行位置找完，就会向上回溯成 -1行，然后退出
        q[j] = q[j] + 1;//让第 j 个皇后向后一列摆放
        while (q[j] <= N && !check(j)){//判断是否越界、第j个皇后的位置是否合法
            q[j] = q[j] + 1;//不合法就往后一个位置摆放，值=列下标+1
        }
        if(q[j] <= N){//找到合法位置，j=行
            if(j == N){//找到了 N皇后 的一组解，j=最后一行
                answer = answer + 1;
                showLog(answer);
            }else{
                j = j+1;//继续摆放下一个皇后，下一行
            }
        }else{//找不到合法位置
            q[j] = 0;//还原第j个皇后的位置
            j = j-1;//回溯上一个行
        }
    }
}
int main () {
    printf("非递归算法-回溯-N皇后     - c.jsrun.net.\n");
    queen();
/*方案1：2 4 1 3 
方案2：3 1 4 2
+-------+
|x|o|x|x|
+-------+
|x|x|x|o|
+-------+
|o|x|x|x|
+-------+
|x|x|o|x|
+-------+*/
    return 0;
}