n- 皇后问题(DFS深度优先搜索)C++_c++深度优先搜索 n-皇后问题

参考自y总算法基础课，题目略有不同

题目：

在 N×N 的棋盘上放置 N 个皇后（N≤10）而彼此不受攻击（即在棋盘的任一行，任一列和任一对角线上不能放置 2 个皇后），编程求解所有的摆放方法。

输入格式:
一个整数 n。

输出格式:
每行输出一种方案，每种方案顺序输出皇后所在的列号，各个数之间有空格隔开。若无方案，则输出 no solute!

输入样例:
在这里给出一组输入。例如：

4
输出样例:
在这里给出相应的输出。例如：

2 4 1 3 
3 1 4 2

 题目分析：

这题考的是dfs深度优先搜索算法，首先定义布尔数组，以判断是否满足“在棋盘的任一行，任一列和任一对角线上不能放置 2 个皇后”。

1. 初始化棋盘：初始化一个N×N的棋盘，所有位置都标记为空（即没有皇后）。

2. 递归函数：主要的递归函数是dfs(int u)，其中u表示当前要放置皇后的行号。

3. 结束条件：如果u等于n，表示我们已经成功地在棋盘上放置了n个皇后，此时递归结束。

4. 搜索：在每一步中，我们从当前行的每一列开始搜索。对于每一列i，我们需要检查三个条件。如果这三个条件都满足（即当前位置可以放置皇后），我们就在该位置放置一个皇后，并标记该列、对角线和反对角线为已使用。然后递归调用dfs(u + 1)来尝试放置下一个皇后。

   • col[i]：当前列是否已经被放置了皇后。
   • dg[i + u]：当前列与之前放置的皇后在右对角线方向上是否有冲突。
   • udg[n - u + i]：当前列与之前放置的皇后在下对角线方向上是否有冲突。

5. 回溯：如果在某个列i中我们发现放置皇后会导致冲突，我们就会“回溯”。这意味着我们需要撤销在当前位置放置皇后的决定，并尝试下一个可能的列。

6. 结束：最终，如果递归结束时没有找到解决方案（即没有成功地在棋盘上放置n个皇后），我们就会返回一个标志，表示没有解。

代码如下：

#include <iostream>  
  
using namespace std;  
const int N = 20;   
  
// 定义三个布尔数组，用于标记棋盘上的列、对角线和反对角线是否已经有皇后  
bool col[N],dg[N],udg[N];  
  
int n; // n为皇后的数量  
  
// 定义一个二维字符数组g[N][N]，表示棋盘的状态，'.'表示没有皇后，'Q'表示有皇后  
char g[N][N];  
  
int flag = 0; // 用于标记是否找到皇后
  
// dfs用于寻找皇后的放置位置  
void dfs( int u )  
{  
    if( u == n ) // 当已经放置了n个皇后时，找到了一个解 
    {  
        for( int i = 0; i < n; i ++) 
        {  
            for( int j = 1; j <= n; j ++) // 遍历每一行的每一个位置  
            {  
                if(g[i][j] == 'Q') // 如果当前位置有皇后  
                {  
                    printf("%d ",j); // 输出皇后的列位置  
                    flag = 1; // 标记为已找到 
                }  
            }  
        }  
        printf("\n"); // 换行  
    }  
    for( int i = 1; i <= n; i ++) // 遍历每一列的每一个位置  
    {  
        if(!col[i] && !dg[i + u] && !udg[n - u + i]) // 如果当前位置所在的列、对角线和反对角线都没有皇后  
        {  
            g[u][i] = 'Q'; // 在当前位置放置一个皇后  
            col[i] = dg[i + u] = udg[n - u + i] = true; // 标记当前位置所在的列、对角线和反对角线已经有皇后  
            dfs( u + 1 ); // 继续放置下一个皇后  
            //若进入下一轮递归无法满足条件则发生回溯
            //将当前位置的皇后移除，并重置标记  
            col[i] = dg[i + u] = udg[n - u + i] = false;  
            g[u][i] = '.';  
        }  
    }  
}  
  
int main() // 主函数  
{  
    cin >> n; // 输入皇后的数量  
    for( int i = 0; i < n; i ++) // 初始化棋盘，所有位置都没有皇后  
    {  
        for( int j = 1; j <= n; j ++)  
        {  
            g[i][j] = '.';  
        }  
    }  
    dfs(0); // 从第一行开始放置第一个皇后，并开始搜索  
    if(flag == 0) // 如果标记为0，表示没有找到解  
    {  
        printf("no solute!"); // 输出没有解的信息  
    }  
    return 0; // 结束程序  
}