N皇后问题详解:回溯算法的应用与实践(dfs)

这篇具有很好参考价值的文章主要介绍了N皇后问题详解:回溯算法的应用与实践(dfs)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

N皇后问题详解:回溯算法的应用与实践(dfs),算法入门,深度优先,算法,图搜索算法

一.问题描述

N皇后问题详解:回溯算法的应用与实践(dfs),算法入门,深度优先,算法,图搜索算法
题目如上图所示,在一个n*n的国际象棋棋盘上怎么摆放能使得皇后互相攻击不到(也就是在任意一列、一行、一条对角线上都不存在两个皇后

二.思路分析

1.DFS

想要解决这个问题,我们可以使用dfs也就是深度优先遍历,深度优先搜索的步骤为先递归到底再回溯上来,顾名思义,dfs是以深度为目标,一条路走到底,直到达到无路可走时,退回到上一步的状态,走其他路回溯上来。
这题我们就可以定义数组当做棋盘,遍历所有位置判断是否可以放置皇后(需要满足任意一列、一行、一条对角线上都不存在两个皇后),在遍历的过程中需要考虑剪枝的情况,减少解题时间复杂度。

三.代码实现与解析

1.分析

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

#include <iostream>
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 < n; i++)
		for (int m = 0; m < n; m++)
			ret[i][m] = '.';

	dfs(0);//dfs算法函数
	return 0;
}

紧接着就是dfs函数代码的实现逻辑:

void dfs(int u)
{
	if (u == n)
	{
		for (int i = 0; i < n; i++)
		{
			cout << ret[i] << endl;;
		}
		cout<< endl;
		return;
	}

	for (int i = 0; i < n; i++)
	{
		if (!col[i] && !dg[u + i] && !udg[n + i - u])
		{
			ret[u][i] = 'Q';
			col[i] = dg[u + i] = udg[n + i - u] = true;
			dfs(u + 1);
			ret[u][i] = '.';
			col[i] = dg[u + i] = udg[n + i - u] = false;
		}
	}
}

需要重点理解的在for循环中i代表的是列数(遍历的是列),u代表的是层数,if判断当行、对角线均暂无皇后时,则可以在此放置皇后,并标识为已经放置,此时这一层的放置就结束了,所以接着就要递归下一层,之后就会分为两种情况:
1.递归到最后一层成功打印了这次的方案。接着就会向上回溯

ret[u][i] = '.';
col[i] = dg[u + i] = udg[n + i - u] = false;

执行恢复逻辑。
2.在后续层数遍历放置时,出现了不合法的情况(列数到达阈值依旧没有放置),此时就会剪枝,也是会回溯到上图代码进行恢复。文章来源地址https://www.toymoban.com/news/detail-843481.html

2.完整代码

#include <iostream>
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 < n; i++)
		for (int m = 0; m < n; m++)
			ret[i][m] = '.';

	dfs(0);
	return 0;
}
void dfs(int u)
{
	if (u == n)
	{
		for (int i = 0; i < n; i++)
		{
			cout << ret[i] << endl;;
		}
		cout<< endl;
		return;
	}

	for (int i = 0; i < n; i++)
	{
		if (!col[i] && !dg[u + i] && !udg[n + i - u])
		{
			ret[u][i] = 'Q';
			col[i] = dg[u + i] = udg[n + i - u] = true;
			dfs(u + 1);
			ret[u][i] = '.';
			col[i] = dg[u + i] = udg[n + i - u] = false;
		}
	}
}

到了这里,关于N皇后问题详解:回溯算法的应用与实践(dfs)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

原文地址:https://blog.csdn.net/qq_43289447/article/details/136417225

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 八皇后问题,秒懂递归回溯(有图详解|c语言)

    目录 👸🏻前言 👸🏻题目介绍 👸🏻引入: 👸🏻解决思路: 👸🏻理论存在,实践开始! 👸🏻难点1:如何表示对角线被占领? 👸🏻难点2:如何用递归的方法来放皇后? 👸🏻难点3:如何实现回溯? 👸🏻难点4:如何实现皇后位置的输出? 👸🏻全部代码如下: 👸

    2024年02月02日
    浏览(6)
  • 【算法】递归、回溯、剪枝、dfs 算法题练习(组合、排列、总和问题;C++)

    后面的练习是接着下面链接中的文章所继续的,在对后面的题练习之前,可以先将下面的的文章进行了解👇: 【算法】{画决策树 + dfs + 递归 + 回溯 + 剪枝} 解决排列、子集问题(C++) 思路 题意分析 :要求根据给出的数字,算出合法的括号组成个数。根据题目,我们可以总

    2024年02月22日
    浏览(7)
  • 动态规划、DFS 和回溯算法:二叉树问题的三种视角

    在计算机科学中,算法是解决问题的核心。特别是对于复杂的问题,不同的算法可以提供不同的解决方案。在本篇博客中,我们将探讨三种算法:动态规划、深度优先搜索(DFS)和回溯算法,它们如何从不同的角度解决以二叉树为基础的问题。 二叉树是一种非常基础的数据结

    2024年02月04日
    浏览(8)
  • DFS(深度优先遍历、N皇后问题、2N皇后问题)

    目录 一、回溯法与深度优先搜索(DFS) 二、DFS与二叉树的前序遍历 2.1、二叉树的前序遍历 2.2、DFS 全排列  2.3、分析 三、N皇后问题 1. 回溯法: 是一种通过探索所有可能的候选解来找出所有解的算法。如果候选解被确认不是一个解的话(或者至少不是最后一个解),回溯法

    2024年03月21日
    浏览(18)
  • 八皇后问题(回溯法)

    目录 什么是八皇后 八皇后问题怎么解决? 什么是回溯法 回溯法的模板 八皇后问题的核心代码 判断皇后位置是否可行 总体实现代码 每日一句: 种一棵树的最好时间是十年前,其次是现在。 八皇后问题(英文:Eight queens),是由国际西洋棋棋手马克斯·贝瑟尔于1848年提出的

    2023年04月09日
    浏览(11)
  • 回溯法求解八皇后问题

    问题提出 :八皇后问题是一个古老而著名的问题。该问题是十九世纪著名的数学家高斯1850 提出在 8x8 格的国际象棋上摆放八皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志

    2023年04月08日
    浏览(7)
  • 回溯法--n皇后问题

    回溯法有两个模板--子集树、排列树,他们有回溯法的共同特点:深度优先搜索,如果一条路走不通,再退回来(类似递归) 八皇后问题最早是由国际象棋棋手马克斯·贝瑟尔(Max Bezzel)于1848年提出。第一个解在1850年由弗朗兹·诺克(Franz Nauck)给出。并且将其推广为更一般

    2024年02月02日
    浏览(10)
  • 3.2 回溯法—N皇后问题

    1. 问题描述 在 n × n ntimes n n × n 的棋盘上摆放 n n n 个皇后,使任意两个皇后都不能处于同一行、同一列或同一斜线上 2. 问题分析 下以求解4皇后问题为例,分析4皇后问题的排列树以及回溯过程: 搜索及回溯过程: 解空间树: 3. 算法设计 1. 算法思想 ①用数组x[]存放皇后的

    2024年02月04日
    浏览(9)
  • 温故知新:dfs模板-843. n-皇后问题

    n−n−皇后问题是指将 nn 个皇后放在 n×nn×n 的国际象棋棋盘上,使得皇后不能相互攻击到,即任意两个皇后都不能处于同一行、同一列或同一斜线上。 现在给定整数 nn,请你输出所有的满足条件的棋子摆法。 输入格式 共一行,包含整数 nn。 输出格式 每个解决方案占 

    2024年02月07日
    浏览(13)
  • C#八皇后算法:回溯法 vs 列优先法 vs 行优先法 vs 对角线优先法

    目录 1.八皇后算法(Eight Queens Puzzle) 2.常见的八皇后算法解决方案 (1)列优先法(Column-First Method): (2)行优先法(Row-First Method): (3)对角线优先法(Diagonal-First Method): (4)回溯法(Backtracking):        皇后问题是一个古老而著名的问题,它实质上就是使棋

    2024年03月22日
    浏览(11)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包