回溯算法解决N皇后问题以及个人理解

算法定义：回溯算法（Backtracking）是一种通过尝试所有可能的解，并在搜索过程中进行剪枝来找到问题的解的算法。它通常用于解决组合优化问题，如排列、组合、子集和图的遍历等。

思想：

回溯算法的基本思想是通过逐步构建候选解，并在构建的过程中进行选择和限制条件的判断。当发现当前构建的候选解无法满足问题的限制条件时，会回溯（回退）到上一步，尝试其他的选择。通过不断地构建和回溯，最终找到满足问题要求的解，或者确定解不存在。

回溯算法通常通过递归来实现，每一层递归对应问题的一个决策点。在每个决策点上，尝试所有可能的选择，并根据问题的限制条件进行剪枝，以避免无效的搜索。当找到一个解时，可以继续搜索寻找其他解，或者直接返回结果。

C语言代码实现

#include 
#include 

#define N 8

// 打印棋盘
void printBoard(char board[N][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            printf("%c ", board[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

// 检查在 board[row][col] 放置皇后是否安全
bool isSafe(char board[N][N], int row, int col) {
    // 检查当前列是否有皇后
    for (int i = 0; i < row; i++) {
        if (board[i][col] == 'Q') {
            return false;
        }
    }

    // 检查左上方是否有皇后
    for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] == 'Q') {
            return false;
        }
    }

    // 检查右上方是否有皇后
    for (int i = row, j = col; i >= 0 && j < N; i--, j++) {
        if (board[i][j] == 'Q') {
            return false;
        }
    }

    return true; // 位置安全
}

// 在第 row 行放置皇后
void placeQueen(char board[N][N], int row) {
    // 所有行都放置完毕，打印结果
    if (row == N) {
        printBoard(board);
        return;
    }

    // 在当前行的每个列尝试放置皇后
    for (int col = 0; col < N; col++) {
        if (isSafe(board, row, col)) {
            board[row][col] = 'Q'; // 放置皇后

            // 递归放置下一行的皇后
            placeQueen(board, row + 1);

            board[row][col] = '.'; // 回溯，撤销皇后位置
        }
    }
}

// 解决 N 皇后问题
void solveNQueens() {
    char board[N][N];

    // 初始化棋盘
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            board[i][j] = '.';
        }
    }

    placeQueen(board, 0); // 从第 0 行开始放置皇后
}

int main() {
    solveNQueens();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81