八皇后问题

回溯法

像迷宫游戏一样，走到一个分支路口时，下一步要选择没走过的分支走，如果所有分支都走过了，就返回上一个分支路口按此规则继续，直到返回起点或者走到终点。

八皇后问题

要递归的函数结构：
终止条件：行row==8（从0计数）,说明0-7每行都找到了一个可行的位置，得出一种解法。返回上一层。
处理部分：看当前层当前列是否有合适位置，有，进入下一层，没有,看下一列。下一层返回后要清除掉当前位置的做的标记，这样不会影响下一个位置。(就是返回前要把做的更改改回去）
处理部分2：如果当前行所有位置都不合适，返回上一层。

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
//定义棋盘
#define MaxRow 8
int chess[MaxRow][MaxRow] = {0};
//解法计数
int count = 0;

//判断当前位置是否可行，可行返回1，不可行返回0
int CanPlace(int row,int col){
    //看同一列有没有皇后
    for (int i = 0; i < row; i++) {
        if (chess[i][col] == 1) return 0;
    }
    //看左上有没有皇后
    for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
        if (chess[i][j] == 1) return 0;
    }
    //看右上有没有皇后
    for (int i = row, j = col; i >= 0 &&j <= MaxRow - 1;i--,j++) {
        if (chess[i][j] == 1) return 0;
    }
    return 1;
}


//打印棋盘,皇后为Q空为*
void print(){
    for (int i = 0; i < MaxRow; i++) {
        for (int j = 0; j < MaxRow; j++) {
            if (chess[i][j] == 1) {
                printf("Q ");
            }
            else
            {
                printf("* ", chess[i][j]);
            }
        }
        printf("\n");
    }
    printf("-----------------------------------\n");
}

//寻找解法并打印，输入当前处理行数row（从0开始计数）
void EightQueens(int row) {
    //如果row==MaxRow，说明已经找到一种解法，打印，count++，返回上一层
    if (row == MaxRow) {
        count++;
        printf("第%d种解法:\n",count);
        print();
        return;
    }
    //看当前层当前列是否有合适位置，有，进入下一层，没有,看下一列
    for (int col = 0; col < MaxRow; col++) {
        if (CanPlace(row, col)) {
            chess[row][col] = 1; //可行，对应位置设为1
            EightQueens(row + 1);//进入下一层
            chess[row][col] = 0; //恢复棋盘
        }
    }
    //当前层都没有合适位置，返回上一层
    return;
}


int main() {
    EightQueens(0);
    printf("结束，解法总数：%d\n", count);

    return 0;
}