N皇后问题详解：回溯算法的应用与实践（dfs）

目录

• 一.问题描述
• • 二.思路分析
  • • 1.DFS
    • 三.代码实现与解析
    • 1.分析
    • 2.完���代码

      一.问题描述

      题目如上图所示，在一个n*n的国际象棋棋盘上怎么摆放能使得皇后互相攻击不到（也就是在任意一列、一行、一条对角线上都不存在两个皇后）

      二.思路分析

      1.DFS

      想要解决这个问题，我们可以使用dfs也就是深度优先遍历，深度优先搜索的步骤为先递归到底再回溯上来，顾名思义，dfs是以深度为目标，一条路走到底，直到达到无路可走时，退回到上一步的状态，走其他路回溯上来。

      这题我们就可以定义数组当做棋盘，遍历所有位置判断是否可以放置皇后（需要满足任意一列、一行、一条对角线上都不存在两个皇后），在遍历的过程中需要考虑剪枝的情况，减少解题时间复杂度。

      三.代码实现与解析

      1.分析

      首先我们创建完数组模拟棋盘后，先要依据题意，将数组初始化为.

      #include const int N = 20;using namespace std;char ret[N][N];bool col[N], dg[N], udg[N];//标记列、对角线上是否已经有皇后int n = 0;void dfs(int u);int main(){cin >> n;for (int i = 0; i  
      紧接着就是dfs函数代码的实现逻辑：
       
      void dfs(int u){if (u == n){for (int i = 0; i