算法学习系列(五):N皇后、数独

目录

  • 引言
  • 一、N皇后问题
    • 代码实现
    • 测试
  • 二、数独问题
    • 代码实现
    • 测试

引言

这个N皇后问题是很典型的一个递归问题,就是还是要掌握,所谓递归其实就是dfs,一层一层深入下去。数独和N皇后的思路是一样的,只不过一些细节不同而已。

一、N皇后问题

首先介绍一下八皇后问题,那么N皇后就是N*N个棋盘里,放入N个棋子,要求同行同列同斜线不能有重复的棋子
在这里插入图片描述

代码实现

这个思路就是暴力枚举,从第一行第一列开始,如果满足要求就落棋子,接着进入下一行,如果一直到了第n+1行说明前n行都满足要求,说明符合情况,就次数加一,然后把该情况打印一下。如果该行结束了,那么就回退到上一行中,把之前落得棋子拾起来,然后再判断下一列是否能够放棋子,一直到第一行结束。
跟下图的思想是一样的,唯一不同的是第二行条件不满足的时候,就进入下一列而不进入下一层
在这里插入图片描述

#include<iostream>

using namespace std;

const int N = 10;
int g[N][N];  //0代表不落棋子,1代表落棋子
int n, cnt;
int dir[3][2] = { -1,-1, -1,0, -1,1 };  //代表方向,分别是左上、上、右上

bool check(int row, int col)
{
	for (int i = 0; i < 3; ++i)
	{
		int x = row, y = col;
		while (1)
		{
			x += dir[i][0];
			y += dir[i][1];
			if (x < 0 || x >= n || y < 0 || y >= n) break;
			if (g[x][y]) return false;
		}
	}

	return true;
}

void dfs(int row)
{
	if (row >= n)
	{
		cnt++;
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < n; ++j)
			{
				printf("%d ", g[i][j]);
			}
			puts("");
		}
		puts("");
	}

	for (int j = 0; j < n; ++j)
	{
		if (check(row, j))
		{
			g[row][j] = 1;
			dfs(row + 1);
			g[row][j] = 0;
		}
	}
}

int main()
{
	cin >> n;
	dfs(0);

	return 0;
}

测试

输入4可以看出是正确的
在这里插入图片描述
输入10,并把输出信息改为最后输出cnt,所得结果也是正确的
在这里插入图片描述

二、数独问题

9*9的格子里,填充数字1~9,要求同行同列不能重复,同一个田字格也不能重复

代码实现

#include<iostream>

using namespace std;

int g[9][9] = { 0,0,5,3,0,0,0,0,0,
				8,0,0,0,0,0,0,2,0,
				0,7,0,0,1,0,5,0,0,
				4,0,0,0,0,5,3,0,0,
				0,1,0,0,7,0,0,0,6,
				0,0,3,2,0,0,0,8,0,
				0,6,0,5,0,0,0,0,9,
				0,0,4,0,0,0,0,3,0,
				0,0,0,0,0,9,7,0,0 };  //0代表没放 1~9代表放的该数字
int cnt;

bool check(int row, int col, int num)
{
	if (g[row][col]) return false;
	for (int i = 0, j = col; i < 9; ++i)
	{
		if (g[i][j] == num) return false;
	}

	for (int i = row, j = 0; j < 9; ++j)
	{
		if (g[i][j] == num) return false;
	}

	int x1 = row / 3 * 3, y1 = col / 3 * 3;
	for (int i = x1; i < x1 + 3; ++i)
	{
		for (int j = y1; j < y1 + 3; ++j)
		{
			if (g[i][j] == num) return false;
		}
	}

	return true;
}

void dfs(int row, int col)
{
	if (row >= 9)
	{
		cnt++;
		for (int i = 0; i < 9; ++i)
		{
			for (int j = 0; j < 9; ++j)
			{
				printf("%d ", g[i][j]);
			}
			puts("");
		}
		puts("");
		return;
	}

	if (g[row][col] == 0)
	{
		for (int num = 1; num <= 9; ++num)
		{
			if (check(row, col, num))
			{
				g[row][col] = num;
				dfs(row + (col + 1) / 9, (col + 1) % 9);
				g[row][col] = 0;
			}
		}
	}
	else
	{
		dfs(row + (col + 1) / 9, (col + 1) % 9);
	}
}

int main()
{
	dfs(0,0);
	//0 1 2   3 4 5   6 7 8

	return 0;
}

测试

可以看出来是正确的
在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/221093.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

使用pyscenedetect进行视频场景切割

1. 简介 在视频剪辑有转场一词&#xff1a;一个视频场景转换到另一个视频场景&#xff0c;场景与场景之间的过渡或转换&#xff0c;就叫做转场。 本篇介绍一个强大的开源工具PySceneDetect&#xff0c;它是一款基于opencv的视频场景切换检测和分析工具&#xff0c;项目地址: h…

探秘 Sass 之路:掌握强大的 CSS 预处理器(上)

&#x1f90d; 前端开发工程师&#xff08;主业&#xff09;、技术博主&#xff08;副业&#xff09;、已过CET6 &#x1f368; 阿珊和她的猫_CSDN个人主页 &#x1f560; 牛客高级专题作者、在牛客打造高质量专栏《前端面试必备》 &#x1f35a; 蓝桥云课签约作者、已在蓝桥云…

uni-app 微信小程序之swiper轮播图

1. 实现效果 2. 完成代码 <template><view class"components-home"><view style"margin-top:-50rpx;height: 486rpx; position: relative;margin-bottom: 80rpx;"><image srchttps://xxx.com/img/wccQQP.png modewidthFix classpng …

AI助力智慧农业,基于YOLOv3开发构建农田场景下的庄稼作物、田间杂草智能检测识别系统

智慧农业随着数字化信息化浪潮的演变有了新的定义&#xff0c;在前面的系列博文中&#xff0c;我们从一些现实世界里面的所见所想所感进行了很多对应的实践&#xff0c;感兴趣的话可以自行移步阅读即可&#xff1a; 《自建数据集&#xff0c;基于YOLOv7开发构建农田场景下杂草…

Ubuntu系统下使用apt-get安装Redis

记录一下Ubuntu20.04 64位系统下使用apt-get安装Redis 首先检查一下系统是否安装过redis whereis redismywmyw-K84HR:~$ whereis redis redis: mywmyw-K84HR:~$ 更新软件包 sudo apt-get update -y安装redis sudo apt-get install redis-server -ymywmyw-K84HR:~$ sudo apt…

ELasticsearch:什么是语义搜索?

语义搜索定义 语义搜索是一种解释单词和短语含义的搜索引擎技术。 语义搜索的结果将返回与查询含义匹配的内容&#xff0c;而不是与查询中的单词字面匹配的内容。 语义搜索是一组搜索引擎功能&#xff0c;其中包括根据搜索者的意图及其搜索上下文理解单词。 此类搜索旨在通过…

【S32K3环境搭建】-0.1-安装S32 Design Studio for S32 Platform 3.5

目录&#xff08;S32DS安装步骤详细&#xff09; 1 安装S32 Design Studio for S32 Platform 3.5准备工作 2 下载S32 Design Studio for S32 Platform 3.5安装包 2.1 获取S32DS的License许可 3 安装S32 Design Studio for S32 Platform 3.5 4 打开S32 Design Studio for S…

【网络奇缘】- 如何自己动手做一个五类|以太网|RJ45|网络电缆

​ ​ &#x1f308;个人主页: Aileen_0v0&#x1f525;系列专栏: 一见倾心,再见倾城 --- 计算机网络~&#x1f4ab;个人格言:"没有罗马,那就自己创造罗马~" 本篇文章关于计算机网络的动手小实验---如何自己动手做一个网线&#xff0c; 也是为后面的物理层学习进…

【LabVIEW学习】5.数据通信之TCP协议,控制电脑的一种方式

一。tcp连接以及写数据&#xff08;登录&#xff09; 数据通信--》协议--》TCP 1.tcp连接 创建while循环&#xff0c;中间加入事件结构&#xff0c;创建tcp连接&#xff0c;写入IP地址与端口号 2.写入tcp数据 登录服务器除了要知道IP地址以及端口以外&#xff0c;需要用户名与密…

nodejs+vue+微信小程序+python+PHP在线购票系统的设计与实现-计算机毕业设计推荐

伴随着信息时代的到来&#xff0c;以及不断发展起来的微电子技术&#xff0c;这些都为在线购票带来了很好的发展条件。同时&#xff0c;在线购票的范围不断增大&#xff0c;这就需要有一种既能使用又能使用的、便于使用的、便于使用的系统来对其进行管理。在目前这种大环境下&a…

FairGuard无缝兼容小米澎湃OS、ColorOS 14 、鸿蒙4!

随着移动互联网时代的发展&#xff0c;各大手机厂商为打造生态系统、构建自身的技术壁垒&#xff0c;纷纷投身自研操作系统。 而对于一款游戏安全产品&#xff0c;在不同操作系统下&#xff0c;是否能够无缝兼容并且提供稳定的、高强度的加密保护&#xff0c;成了行业的一大痛…

Kafka中的Partition详解与示例代码

在Apache Kafka中&#xff0c;Partition&#xff08;分区&#xff09;是一个关键的概念。分区的引入使得Kafka能够处理大规模数据&#xff0c;并提供高性能和可伸缩性。本文将深入探讨Kafka中的Partition&#xff0c;包括分区的作用、创建、配置以及一些实际应用中的示例代码。…

C++ day55 判断子序列 不同的子序列

题目1&#xff1a;392 判断子序列 题目链接&#xff1a;判断子序列 对题目的理解 判断字符串s是否为t的子序列 字符串s和字符串t的长度大于等于0&#xff0c;字符串s的长度小于等于字符串t的长度&#xff0c;本题其实和最长公共子序列的那道题很相似&#xff0c;相当于找两…

gitlab高级功能之容器镜像仓库

今天给大家介绍一个gitlab的高级功能 - Container Registry&#xff0c;该功能可以实现docker镜像的仓库功能&#xff0c;将gitlab上的代码仓的代码通过docker构建后并推入到容器仓库中&#xff0c;好处就是无需再额外部署一套docker仓库。 文章目录 1. 参考文档2. Container R…

yolov8添加ca注意力机制

创建文件 coordAtt.py 位置&#xff1a;ultralytics/nn/modules/coordAtt.py ###################### CoordAtt #### start by AI&CV ############################### # https://zhuanlan.zhihu.com/p/655475515 import torch import torch.nn as nn import t…

在Windows11(WSL)中如何迁移Docker

前言&#xff1a; 在Windows 10中Docker是默认安装到WSL中的&#xff0c;而安装到WSL中的任意分发版都是默认放在C盘中的。这样会让我们的C盘资源极度紧张&#xff0c;而且也限制了Docker的镜像数量。 迁移步骤 假设我有一个临时目录“D:\docker”用来存放临时文件&#xff0c;…

【开源】基于Vue和SpringBoot的在线课程教学系统

项目编号&#xff1a; S 014 &#xff0c;文末获取源码。 \color{red}{项目编号&#xff1a;S014&#xff0c;文末获取源码。} 项目编号&#xff1a;S014&#xff0c;文末获取源码。 目录 一、摘要1.1 系统介绍1.2 项目录屏 二、研究内容2.1 课程类型管理模块2.2 课程管理模块2…

黑马头条数据管理平台项目总结

今天主要看了该项目的介绍&#xff0c;这个黑马头条数据管理平台项目主要包括登录、用户的权限判断、文章内容列表的筛选和分页、文章的增删查改还有图片和富文本编辑器这几大部分组成&#xff0c;项目配套了素材代码&#xff0c;像资源文件、第三方插件、页面文件夹、工具插件…

【MySQL】表的增删查改

增创建库创建表表插入表更新插入表替换插入查询结果 查全列查找指定列查找查找结果去重where条件查找筛选分页结果 改对查询到的结果进行列值更新 删delete 和 truncate 的区别 增 创建库创建表 create database 库名称;use 进入的库名称;create table 表名称; select * from…

Apollo新版本Beta技术沙龙

有幸参加Apollo开发者社区于12月2日举办的Apollo新版本(8.0)的技术沙龙会&#xff0c;地址在首钢园百度Apollo Park。由于去的比较早&#xff0c;先参观了一下这面的一些产品&#xff0c;还有专门的讲解&#xff0c;主要讲了一下百度无人驾驶的发展历程和历代产品。我对下面几个…