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

创作时间:

作者:

@小白创作中心

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

引用

CSDN

https://blog.csdn.net/qqqqqwerttwtwe/article/details/145501926

深度优先搜索（DFS）是一种重要的算法思想，在许多领域都有广泛的应用。本文通过经典的N皇后问题，深入浅出地介绍了DFS的核心思想、实现框架、时间空间复杂度分析，并给出了详细的代码实现和优化建议。

引言：当算法遇见棋盘

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

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

1.1 算法核心思想

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

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

1.2 算法实现框架


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

1.3 算法特性分析

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

二、N皇后问题建模

2.1 问题描述

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

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

2.2 问题转化

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

树节点：已放置k kk个皇后的部分解
树边：在第k + 1 k+1k+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;
}