当前位置：首页 > article >正文

深入浅出深度优先搜索（DFS）——以经典N皇后问题为例

article 2025/2/8 6:21:42

引言：当算法遇见棋盘

想象你面前有一张 $8 * 8$ 的国际象棋棋盘，现在需要摆放 $8$ 个皇后，使得任意两个皇后都无法互相攻击。这个看似简单的谜题，自 $1848$ 年被提出以来吸引了无数数学家与计算机科学家的目光。当我们把棋盘扩展到 $N * N$ 规格时，就诞生了著名的N皇后问题。本文将带您通过这个经典问题，深入理解深度优先搜索（DFS）这一重要的算法思想。

一、深度优先搜索原理剖析

1.1 算法核心思想

深度优先搜索（Depth-First Search）采用"不撞南墙不回头"的策略，其运行过程就像探险者深入洞穴：

选择一条路径走到尽头
遇到死胡同后回退到最近分叉点
尝试其他未探索的分支
重复直到找到解或遍历所有可能

1.2 算法实现框架

def dfs(当前状态):
    if 到达终止条件:
        记录/处理结果
        return
    
    for 所有可能的选择:
        if 选择合法:
            做出选择
            dfs(新状态)
            撤销选择

1.3 算法特性分析

时间复杂度： $O(b^d)$ （b为分支因子，d为最大深度）
空间复杂度： $O (d)$ （递归栈深度）
优势：实现简单，适合寻找所有解
局限：可能陷入深度路径效率低下

二、N皇后问题建模

2.1 问题描述

在 $N * N$ 的棋盘上放置 $N$ 个皇后，要求：

每行恰好一个皇后
每列最多一个皇后
每条对角线最多一个皇后

2.2 问题转化

将棋盘建模为状态空间树：

树节点：已放置 $k$ 个皇后的部分解
树边：在第 $k + 1$ 行放置皇后的选择
叶子节点：有效解或冲突状态

三、DFS解法的实现

ACWing N皇后问题

3.1 关键数据结构

#include <iostream>
using namespace std;

const int MAX_N = 10; // 最大棋盘尺寸

int board[MAX_N][MAX_N] = {0}; // 棋盘状态，0表示空，1表示皇后
int col_used[MAX_N] = {0};     // 列占用标记

// 打印当前棋盘状态
void print_board(int n) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout << (board[i][j] ? "Q" : ".");
        }
        cout << endl;
    }
    cout << endl;
}

// 检查当前位置(x,y)是否安全
bool is_safe(int x, int y, int n) {
    // 检查两条对角线
    for (int i = 1; i < x; i++) {
        // 左上到右下对角线
        if (y - x + i > 0 && board[i][y - x + i]) return false;
        // 右上到左下对角线
        if (y + x - i <= n && board[i][y + x - i]) return false;
    }
    return true;
}

// 递归求解N皇后问题
void find_queen(int row, int placed, int n) {
    // 找到一组解
    if (placed == n) {
        print_board(n);
        return;
    }

    // 尝试在当前行的每一列放置皇后
    for (int col = 1; col <= n; col++) {
        // 跳过已被占用的列
        if (col_used[col]) continue;
        
        // 检查对角线是否安全
        if (!is_safe(row, col, n)) continue;

        // 放置皇后
        board[row][col] = 1;
        col_used[col] = 1;

        // 递归处理下一行
        find_queen(row + 1, placed + 1, n);

        // 回溯：移除皇后
        board[row][col] = 0;
        col_used[col] = 0;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    // 参数说明：
    // 1: 从第1行开始
    // 0: 当前已放置0个皇后
    // n: 棋盘大小
    find_queen(1, 0, n);
    
    return 0;
}