递归与回溯：八皇后问题

八皇后问题，可以说是递归回溯的经典入门题了。我第一次接触它是在大学的数据结构课上，当时觉得这玩意儿真神奇——八个皇后放在棋盘上，居然能用几十行代码搞定所有解。后来工作后，我在一个排课系统的冲突检测模块里，又用到了类似的回溯思想。嗯，今天我们就来好好聊聊它。

问题是什么？

简单说：在一个 8×8 的国际象棋棋盘上，放 8 个皇后。要求它们互相不能攻击。皇后可以横着走、竖着走、斜着走，所以任意两个皇后不能在同一行、同一列、同一对角线上。

说白了，就是找一种摆法，让这 8 个皇后「和平共处」。

你想想看，总共有多少种摆法？暴力枚举的话，从 64 个格子里选 8 个，组合数 C(64,8) 大约是 44 亿种。这显然不现实。但用递归回溯，我们只需要检查 15720 种情况——这就是算法的力量。

核心思路：一行一行放

我个人习惯用「逐行放置」的策略。为什么？因为皇后不能在同一行，所以每行只能放一个。我们按行号从 0 到 7 依次尝试，每行放一个皇后，然后检查是否与之前放的冲突。

伪代码大概是这样的：

void solve(row) {
    if (row == 8) {
        // 找到一组解，打印
        return;
    }
    for (col = 0; col < 8; col++) {
        if (isSafe(row, col)) {
            placeQueen(row, col);
            solve(row + 1);  // 递归下一行
            removeQueen(row, col);  // 回溯，撤销选择
        }
    }
}

这里的关键就是 isSafe 函数。它要检查三个方向：同一列、左上到右下的对角线、右上到左下的对角线。

如何判断冲突？

我见过不少新手在这里踩坑。他们用二维数组存棋盘，每次检查都要循环遍历，效率很低。其实有更优雅的做法——用三个一维数组来标记冲突。

• col[8]：标记每一列是否已被占用
• diag1[15]：标记左上到右下的对角线。规律：行号 - 列号 + 7 是常数
• diag2[15]：标记右上到左下的对角线。规律：行号 + 列号是常数

举个例子：皇后在 (2, 3)，那么它所在的左上-右下对角线编号是 2 - 3 + 7 = 6，右上-左下对角线编号是 2 + 3 = 5。

这样，isSafe 就变成了 O(1) 的检查：

int isSafe(int row, int col) {
    return !col[col] && !diag1[row - col + 7] && !diag2[row + col];
}

简洁，高效。我在项目中处理类似的「位置冲突」问题时，也经常用这种「空间换时间」的思路。

完整代码实现

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

int col[8] = {0};
int diag1[15] = {0};
int diag2[15] = {0};
int board[8][8] = {0};
int count = 0;

void printBoard() {
    printf("解 %d:\n", ++count);
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            printf("%c ", board[i][j] ? 'Q' : '.');
        }
        printf("\n");
    }
    printf("\n");
}

void solve(int row) {
    if (row == 8) {
        printBoard();
        return;
    }
    for (int c = 0; c < 8; c++) {
        if (!col[c] && !diag1[row - c + 7] && !diag2[row + c]) {
            // 放置皇后
            board[row][c] = 1;
            col[c] = 1;
            diag1[row - c + 7] = 1;
            diag2[row + c] = 1;

            solve(row + 1);

            // 回溯，撤销
            board[row][c] = 0;
            col[c] = 0;
            diag1[row - c + 7] = 0;
            diag2[row + c] = 0;
        }
    }
}

int main() {
    solve(0);
    printf("共有 %d 种解法\n", count);
    return 0;
}

运行结果会输出 92 种解法。没错，八皇后问题一共有 92 个不同的解。

回溯过程的可视化

为了让你更直观地理解回溯的过程，我画了一张流程图：

避坑指南

我曾经在写回溯时犯过一个低级错误——忘记在递归调用后撤销标记。结果程序只输出了一组解，然后就卡死了。排查了半天才发现，原来是标记位没清干净，导致后面的分支全被堵死了。

所以记住：回溯的「撤销」操作，和「放置」操作一样重要。你可以在写代码时先把放置和撤销写在一起，养成习惯：

// 放置
mark(row, col);
solve(row + 1);
// 撤销
unmark(row, col);

这样就不容易漏掉了。

性能与优化

92 种解，对于现代计算机来说就是一瞬间的事。但如果你把问题扩展到 N 皇后呢？比如 12 皇后有 14200 种解，15 皇后有 2279184 种解。随着 N 增大，解的数量爆炸式增长。

这时候可以考虑一些优化：

• 对称性剪枝：棋盘有旋转和镜像对称性，找到一组解后，可以通过对称变换生成其他解，减少搜索量
• 位运算加速：用整数的二进制位来标记列和对角线，比数组更快
• 启发式搜索：优先尝试「冲突最少」的位置，提前剪枝

不过对于学习阶段，先把基础版本写对，再谈优化。这是我一贯的建议。

小结

八皇后问题虽然经典，但它背后的思想——递归回溯——才是真正值钱的东西。我在实际项目中处理过排课冲突、地图着色、数独求解，本质上都是同一套思路：尝试、检查、递归、回溯。

你把这个套路练熟了，以后遇到类似的问题，脑子里自然就会浮现出那个「一行一行放皇后」的画面。

---

公众号:蓝海资料掘金营，微信deep3321