当前位置:   article > 正文

N皇后问题的DFS 解法(深度优先搜索解法)——极易理解_n皇后深度优先算法

n皇后深度优先算法

问题描述

N 皇后问题是指在 n x n 的棋盘上要摆 n皇后
要求:任何两个皇后不同行不同列也不在同一条斜线上,
求给一个整数n,返回 n 皇后的摆法数

在这里插入图片描述

思路

对于这个问题,因为是求最终的摆法数,也就是要遍历所有可能的状态,由此想到应该用DFS(深度优先搜索)解决

1.由于只有棋盘n行,要求每个皇后不同行,那么我们可以确定每行有且仅有一个皇后
2. 我们使用DFS依次对每行的皇后进行位置安排,即从第0行、第1行……第n-1
3. 对于每一行,遍历所有可能的列,从而确定一个皇后的位置,并且使该列的状态被标记为已被第i行的皇后占领
4.递归调用求下一个皇后的位置
5.如果递归到n个皇后,方案数+1,然后返回

在这里插入图片描述

代码实现

N皇后问题
#include <iostream>
#include <vector>
using namespace std;
int ans = 0;
int n;
vector<int> col;
bool dgcheck(int row, int co);
void dfs(int k);

int main()
{
    cin >> n;
    col.resize(n);
    for (int i = 0; i < n; i++)
        col[i] = -1;
    dfs(0);
    cout << ans;
}
bool dgcheck(int row, int co)//判断当前列是否被占用以及当前位置(row,co)对角线上是否有其他皇后
{
    if (col[co] != -1)
        return false;
    for (int i = max(-row, -co); i + row < n && i + co < n && i + row >= 0 && i + co >= 0; i++)
    {
        if (col[co + i] == row + i)
            return false;
    }
    for (int i = max(-row, co - n + 1); i + row < n &&  co-i < n && i + row >= 0 && co-i >= 0; i++)
    {
        if (col[co - i] == row + i)
            return false;
    }
    return true;
}
void dfs(int k)
{
    if (k == n)
    {
        ans++;
        return;
    }
    for (int i = 0; i < n; i++)
    {
        if (dgcheck(k, i))
        {
            col[i] = k;//将第k个皇后放在第i列
            dfs(k + 1);
            col[i] = -1;//将第k个皇后不放在第i列
        }
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52

2023.12.12更新
可以用dg和ndg数组来记录对角线上是否有皇后,关键在于给同一对角线上的元素建立唯一映射

#include<iostream>
using namespace std;
const int N = 20;
int n;
char grid[N][N];
int col[N],dg[N],ndg[N];
void dfs(int u)
{
    if(u==n)
    {
        for(int i = 0;i<n;i++)puts(grid[i]);
        puts("");
    }
    for(int i = 0;i<n;i++)
    {
        if(col[i] == 0&&dg[i-u]==0&&ndg[i+u]==0)
        {
            grid[u][i] = 'Q';
            col[i]=dg[i-u]=ndg[i+u] = 1;
            dfs(u+1);
            grid[u][i] = '.';
            col[i]=dg[i-u]=ndg[i+u] = 0;
        }
    }
}
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n;
    for(int i = 0;i<n;i++)
    {
        for(int j =0;j<n;j++)
        {
            grid[i][j] = '.';
        }
    }
    dfs(0);
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/运维做开发/article/detail/825485
推荐阅读
相关标签
  

闽ICP备14008679号