回溯算法入门：用 C 和 Python 解决 8 皇后问题

回溯算法是很多人系统学习搜索问题时绕不开的一道坎。它表面上像“暴力枚举”，但真正的关键不是把所有情况都试一遍，而是：在搜索过程中，尽早发现不合法的选择，并立刻回退。

8 皇后问题正是一个非常经典的回溯入门题。规则不复杂，但足够典型，刚好能把回溯中的“做选择、递归、撤销选择”讲清楚。

这篇文章就从零开始，用最标准的“回溯 + 剪枝”思路，带你一步一步解决 8 皇后问题，并分别给出 C 和 Python 的完整实现。

一、什么是 8 皇后问题

8 皇后问题的要求是：

在一个 8 × 8 的棋盘上放置 8 个皇后，使得任意两个皇后都不能互相攻击。

皇后的攻击方式包括：

• 同一行
• 同一列
• 同一条主对角线
• 同一条副对角线

因此，我们需要找到所有满足条件的摆放方式，并统计总解数。

8 皇后的经典结论是：一共有 92 个解。

二、为什么这道题适合用回溯

如果完全不加思考地暴力枚举，每个格子都可能放或不放，搜索空间会非常大。

但这道题有一个天然的突破口：

按行放皇后。

也就是说：

• 第 0 行放一个皇后
• 第 1 行放一个皇后
• 第 2 行放一个皇后
• ……
• 一直放到第 7 行

这样做有两个好处：

• 每一行只放一个皇后，所以“行冲突”自动消失
• 我们只需要额外检查列冲突和对角线冲突

于是问题就变成了：

在当前这一行，尝试把皇后放到某一列；如果合法，就继续递归到下一行；如果不合法，就换一个位置继续试。

这就是回溯最典型的结构。

三、回溯算法的三步

回溯的核心可以概括成三句话：

1. 做选择
2. 递归进入下一层
3. 撤销选择

放到 8 皇后问题里，对应关系非常直接：

• 做选择：把当前行的皇后尝试放到某一列
• 递归：继续去处理下一行
• 撤销选择：把刚才放下的皇后拿掉，恢复状态，尝试别的列

这里“撤销选择”非常重要。因为回溯并不是一条路走到底，而是一旦发现当前分支走不通，就要退回上一步，重新选。

四、状态怎么设计

如果想让程序写得清楚，先要想清楚到底需要记录哪些信息。

1. 用 board[row] = col 表示皇后位置

比如：

board[0] = 0
board[1] = 4
board[2] = 7

表示：

• 第 0 行皇后放在第 0 列
• 第 1 行皇后放在第 4 列
• 第 2 行皇后放在第 7 列

2. 用 cols[col] 记录列是否被占用

如果某一列已经放过皇后，那么当前行就不能再放到这一列。

3. 用 main_diag[row - col + n - 1] 记录主对角线

主对角线的特点是：row - col 相同。

由于这个值可能为负数，所以通常加上偏移量 n - 1。

4. 用 anti_diag[row + col] 记录副对角线

副对角线的特点是：row + col 相同。

5. 为什么不用单独记录“行是否被占用”

因为我们本来就是按行递归：

• 递归到第 0 层，就处理第 0 行
• 递归到第 1 层，就处理第 1 行
• 递归到第 2 层，就处理第 2 行

所以每一层天然只会给一行放一个皇后，不需要再额外记录行状态。

五、剪枝到底剪掉了什么

所谓剪枝，就是在还没有搜索到底的时候，提前发现“这条路不可能成功”，于是直接停止往下搜。

在 8 皇后问题里，如果当前准备把皇后放在 (row, col)，只要满足下面任意一个条件，就可以直接跳过：

• 这一列已经有皇后
• 这条主对角线已经有皇后
• 这条副对角线已经有皇后

这就是为什么我们说 8 皇后是“回溯 + 剪枝”的经典题：它不是盲目试探，而是边试边排除无效分支。

六、搜索过程怎么展开

整个搜索过程可以理解成一棵树：

• 每一层代表一行
• 每个分支代表这一行选择某一列
• 如果该位置不合法，就不再继续深入这条分支

举个简单例子：

• 第 0 行先尝试放在第 0 列
• 进入第 1 行，从左到右试探
• 如果第 1 行没有任何合法位置，说明第 0 行放在第 0 列这条路走不通
• 于是退回第 0 行，改试第 1 列

这就是回溯中的“往前试、走不通就退回来”。

七、Python 实现

下面先给出 Python 版本。它会打印全部解，并在最后统计总解数。

N = 8
cols = [False] * N
main_diag = [False] * (2 * N - 1)
anti_diag = [False] * (2 * N - 1)
board = [-1] * N
solution_count = 0


def print_board():
    for row in range(N):
        line = ["."] * N
        line[board[row]] = "Q"
        print(" ".join(line))
    print()


def backtrack(row: int) -> None:
    global solution_count

    if row == N:
        solution_count += 1
        print(f"Solution {solution_count}:")
        print_board()
        return

    for col in range(N):
        d1 = row - col + N - 1
        d2 = row + col

        if cols[col] or main_diag[d1] or anti_diag[d2]:
            continue

        board[row] = col
        cols[col] = True
        main_diag[d1] = True
        anti_diag[d2] = True

        backtrack(row + 1)

        cols[col] = False
        main_diag[d1] = False
        anti_diag[d2] = False
        board[row] = -1


def solve_eight_queens() -> None:
    backtrack(0)
    print(f"Total solutions: {solution_count}")


if __name__ == "__main__":
    solve_eight_queens()

这段代码最关键的地方

• row == N 说明 8 行都已经成功放置皇后，此时找到一个完整解
• if cols[col] or main_diag[d1] or anti_diag[d2] 用来做合法性判断
• 递归前先标记占用状态，递归后再恢复状态

这就是标准回溯模板最典型的写法。

八、C 实现

再看一版 C 实现。算法逻辑和 Python 版本完全一致，只是写法更偏底层。

#include <stdbool.h>
#include <stdio.h>

#define N 8

static bool cols[N];
static bool main_diag[2 * N - 1];
static bool anti_diag[2 * N - 1];
static int board[N];
static int solution_count = 0;

void print_board(void) {
    for (int row = 0; row < N; row++) {
        for (int col = 0; col < N; col++) {
            if (board[row] == col) {
                printf("Q ");
            } else {
                printf(". ");
            }
        }
        printf("\n");
    }
    printf("\n");
}

void backtrack(int row) {
    if (row == N) {
        solution_count++;
        printf("Solution %d:\n", solution_count);
        print_board();
        return;
    }

    for (int col = 0; col < N; col++) {
        int d1 = row - col + N - 1;
        int d2 = row + col;

        if (cols[col] || main_diag[d1] || anti_diag[d2]) {
            continue;
        }

        board[row] = col;
        cols[col] = true;
        main_diag[d1] = true;
        anti_diag[d2] = true;

        backtrack(row + 1);

        cols[col] = false;
        main_diag[d1] = false;
        anti_diag[d2] = false;
        board[row] = -1;
    }
}

void solve_eight_queens(void) {
    backtrack(0);
    printf("Total solutions: %d\n", solution_count);
}

int main(void) {
    for (int i = 0; i < N; i++) {
        board[i] = -1;
    }

    solve_eight_queens();
    return 0;
}

虽然语言不同，但思路完全一样：

• 当前处理第 row 行
• 枚举这一行所有可能的列
• 合法就递归
• 递归回来之后撤销状态

九、示例输出

按照“从左到右尝试列”的顺序，程序找到的第一组解对应的列下标是：

[0, 4, 7, 5, 2, 6, 1, 3]

对应棋盘如下：

Q . . . . . . .
. . . . Q . . .
. . . . . . . Q
. . . . . Q . .
. . Q . . . . .
. . . . . . Q .
. Q . . . . . .
. . . Q . . . .

程序最终会输出：

Total solutions: 92

十、时间复杂度和空间复杂度

时间复杂度

8 皇后本质上仍然是搜索问题，严格的时间复杂度不容易写成一个非常精确的简单公式，但从量级上可以理解为接近 O(N!)。

原因是：

• 第 0 行最多尝试 N 个位置
• 第 1 行最多尝试 N - 1 个位置
• 第 2 行最多尝试 N - 2 个位置
• 后面依次递减

不过真实搜索量会更少，因为剪枝会提前砍掉大量不合法分支。

空间复杂度

空间开销主要来自：

• 递归深度 O(N)
• 列和对角线状态数组 O(N)

因此整体空间复杂度可以看作 O(N)。

十一、这道题真正值得学会的东西

8 皇后最重要的，不只是“做出一道题”，而是掌握下面这些回溯思想：

1. 先定义搜索层次，比如这里的“按行递归”
2. 明确哪些状态必须记录
3. 把不合法分支尽早剪掉
4. 递归返回时撤销之前的选择

当你真正理解了这些，再去看全排列、组合、子集、数独、括号生成等问题时，会发现它们的底层结构非常相似。

十二、总结

8 皇后问题是理解回溯算法的一个非常好的起点，因为它同时具备：

• 清晰的搜索结构
• 典型的剪枝条件
• 直观的状态设计
• 标准的“做选择 → 递归 → 撤销选择”流程

如果你刚开始接触回溯，建议先把这版标准写法真正敲一遍。等你把这套框架吃透之后，再去看位运算优化版，会更容易理解“状态压缩”到底优化了什么。

如果你想继续往下看，可以接着读这篇进阶文章：

回溯算法进阶：用位运算优化 8 皇后（C / Python）