N皇后问题回溯算法实现 - C语言代码详解 - 常规

N皇后问题回溯算法实现 - C语言代码详解

问题描述：

N皇后问题是指在一个N*N的棋盘上放置N个皇后，使得任意两个皇后都不能在同一行、同一列或同一斜线上。

代码实现：

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int x;
    int y;
} Queen;

int n; //皇后个数
int cnt; //解的个数
Queen* stack; //栈
int top; //栈顶指针

void push(Queen q) {
    stack[++top] = q;
}

Queen pop() {
    return stack[top--];
}

int canPlace(Queen q) {
    int i;
    for (i = 1; i <= top; ++i) {
        if (stack[i].y == q.y // 同列
            || abs(stack[i].x - q.x) == abs(stack[i].y - q.y)) { // 同对角线
            return 0;
        }
    }
    return 1;
}

void showSolution() {
    int i, j;
    printf("Solution %d:\n", ++cnt);
    for (i = 1; i <= top; ++i) {
        for (j = 1; j <= n; ++j) {
            if (stack[i].y == j) {
                printf("Q ");
            } else {
                printf(". ");
            }
        }
        printf("\n");
    }
}

void solve() {
    top = 0;
    Queen q = {1, 1};
    while (1) {
        while (q.y <= n && !canPlace(q)) {
            ++q.y;
        }
        if (q.y > n) {
            if (top == 0) {
                break; // 搜索结束
            }
            q = pop();
            ++q.y;
        }
        else {
            push(q);
            if (top == n) {
                showSolution(); // 找到一组解
                q = pop();
                ++q.y;
            }
            else {
                ++q.x;
                q.y = 1;
            }
        }
    }
}

int main() {
    printf("Please input the number of Queens: ");
    scanf("%d", &n);
    stack = malloc(sizeof(Queen) * (n + 1));
    solve();
    free(stack);
    return 0;
}

代码详解：

数据结构
- Queen 结构体：用于表示一个皇后的位置，包含行坐标 x 和列坐标 y。
- stack 数组：使用栈来存储已经放置的皇后，方便回溯操作。
- top：栈顶指针，指向栈顶元素的位置。
函数说明
- push(Queen q)：将一个皇后 q 放入栈中。
- pop()：从栈中弹出栈顶元素。
- canPlace(Queen q)：判断当前位置 q 是否可以放置皇后，如果与之前放置的皇后冲突，返回 0，否则返回 1。
- showSolution()：输出找到的一组解。
- solve()：求解 N 皇后问题的主函数，使用回溯算法进行搜索。
- main()：主函数，负责输入皇后个数 n，分配栈空间，调用 solve() 函数进行求解，最后释放栈空间。

算法思路：

回溯算法的核心思想是不断尝试并回溯，尝试将皇后放置在棋盘上的每个位置，如果发现冲突就回溯到上一步，重新尝试。

初始化：将第一个皇后放在第一行第一列。
循环：循环遍历棋盘上的每个位置，尝试将皇后放置在当前位置。
判断冲突：使用 canPlace 函数判断当前位置是否可以放置皇后，如果可以，将皇后放入栈中。
继续扩展：如果栈已经满了，说明找到了一组解，输出解并回溯到上一层。
回溯：如果当前行没有可以放置的位置，就回溯到上一行，并将皇后放置在该行的下一个位置。
结束：当所有位置都尝试过并且没有找到解时，结束搜索。

时间复杂度：

回溯算法的时间复杂度是指数级的，因为需要尝试所有可能的位置，但相比于穷举算法，回溯算法的效率更高，因为它可以通过判断当前状态是否合法来减少不必要的搜索。

代码特点：

代码清晰易懂，注释详细。
使用栈来存储已经放置的皇后，方便回溯操作。
采用回溯算法，有效地减少了搜索空间，提高了算法效率。

学习建议：

尝试理解回溯算法的思路，并将其应用到其他问题中。
可以尝试修改代码，使其可以输出所有解。
可以尝试使用不同的数据结构和算法来实现 N 皇后问题。

希望这份代码和讲解对您学习 N 皇后问题和回溯算法有所帮助！