dfs +剪枝sudoku———poj2676
目录
前言
lowbit函数
数独
suduku
问题描述
输入
输出
问题分析
子网格位置
优化搜索顺序剪枝1
优化搜索顺序剪枝2
可行性剪枝
代码
前言
lowbit函数
这是一个利用二进制位运算取出二进制数最后一位’1‘的函数
数独
数独大家肯定都玩过,本题就是利用计算机尝试模拟人做数独游戏时的情形,每次从空白最少的行开始填写,每次填写都比对这个数字是否符合要求,如果没有符合要求的数字,则重新填写上一个数字,大家可以回忆下做数独时的情形,也可以为剪枝提供思路
suduku
问题描述
给定一个9*9的网格,又将该网格细分为九个3*3的子网格,现给出部分数字,编写程序填满该网格,要求每行,每列,每个子网格,只能出现1~9中的数字,且每行,每列,每个子网格中不能有重复的数字,若有多个答案,只输出其中一个即可。
输入
有多个测试用例,第一行输入一个整数t,代表测试个数,对于每个测试,输入一个9*9的字符串数组
输出
输出一种符合条件的答案
问题分析
子网格位置
首先要解决子网格位置问题,给定一个点(x,y)的坐标给如何知道该点位于哪个子网格中,我们先对各个子网格编号
1 | 2 | 3 |
4 | 5 | 6 |
7 | 8 | 9 |
然后我们再找规律:
最笨但是最实用的方法就是用9个if语句判断一下确定位置,别瞧不起它,这个是真的有用
不开玩笑了,哈哈,其实这个是有公式的:
解决了这个问题,我们在考虑剪枝
优化搜索顺序剪枝1
会玩数独的伙伴肯定清楚,填数字要从数字最多的一行开始填,也就是空白最少的一行,因为这样很可能提前确定一些数字,计算机也是这样,网格中的数字越多,dfs需要递归的次数就越少,所以每次我们都选择0(也就是空白)最少的一行开始填写
优化搜索顺序剪枝2
很简单的道理,如果1~9中有数字前面已经搜索过了,那么就没有必要再搜了,直接剪掉,这里多说两句,实现这个方法的办法有两种,一种是用一个9位二进制代表1~9,然后用lowbit()函数逐一取出二进制数中的最后一个1,这样可以实现上述剪枝,更简单的就是用循环实现,但是需要加一点小改动,详见代码
可行性剪枝
这个就是根据题意来的,每行,每列,每个子网格中不能存在相同的数字
代码
#include<iostream>
#include <cstring>
#include <algorithm>
using namespace std;
bool flag=false;
int map[15][15]; //九宫格
struct node{int row; //行的编号int num; //该行中0的数量
}cnt[15];
bool row[15][15]; //row[i][x] 标记在第i行中数字x是否出现
bool col[15][15]; //col[j][y] 标记在第j列中数字y是否出现
bool grid[15][15]; //grid[k][x] 标记在第k个3*3子格中数字x是否出现bool cmp(node a, node b) {return a.num < b.num; //升序排列
}int query(int x, int y) {if (y <= 3 && x <= 3) return 1;if (y > 3 && y <= 6 && x <= 3) return 2;if (y > 6 && x <= 3) return 3;if (y <= 3 && x > 3 && x <= 6) return 4;if (y > 3 && y <= 6 && x > 3 && x <= 6) return 5;if (y > 6 && x > 3 && x <= 6) return 6;if (y <= 3 && x > 6) return 7;if (y > 3 && y <= 6 && x > 6) return 8;if (y > 6 && x > 6) return 9;
}void DFS(int x, int y,int pos,int p){if (flag) {//结束dfsreturn;}if (p == 10) {//打印结果,在dfs内打印优势是可以借助dfs本身的回溯将row,col,grid初始化for (int i = 1; i <= 9; i++) {for (int j = 1; j <= 9; j++) {cout << map[i][j];}cout << endl;}flag = true;return;}//剪枝,如果map中该位置已经有数字那么直接下一个,或者下一层if (map[x][y]){if (y == 9) DFS(cnt[p+1].row, 1,1,p+1); //这里用了一个辅助p,帮助计数else DFS(x, y + 1,pos,p);return;}//int k = query(x, y); //最直接方法int k = 3 * ((x - 1) / 3) + (y - 1) / 3 + 1; //公式法//#define lowbit(x) ((x)&-(x))for (int i = pos; i <= 9; i++) { //其实这里可以用一个九位二进制数代表1~9这几个数字是否可选,用lowbit()函数取出第一个1(这个是树状数组中的函数),这样就可以实现减少重复次数,但我觉得使用pos变量也可以实现同样的效果if (!row[x][i] && !col[y][i] && !grid[k][i]) { //利用这仨进行可行性剪枝/*同样的,这里的row,col,grid数组都可以是用九个九位二进制数来代替,但这样编码起来太麻烦了,我写不出来,所以干脆用数组,感兴趣的伙伴可以试一下,写出来了@我一下,第一时间给你点赞*/map[x][y] = i;row[x][i] = true;col[y][i] = true;grid[k][i] = true;//优化搜索顺序剪枝,每次填写0最少的一行if (y == 9) DFS(cnt[p+1].row, 1, 1, p + 1);else DFS(x, y + 1,pos,p); //最优化剪枝,如果前面已经搜过,就代表一定标记过了,就不需要继续了,下一次循环从pos开始//回溯map[x][y] = 0;row[x][i] = false;col[y][i] = false;grid[k][i] = false;}}return ;
}int main(){int t;cin >> t;while (t--){//注意有多个测试用例每次都要将这仨初始化,使用memset的时候要加cstring头文件,但如果在dfs内部输出结果则不需要手动初始化/*memset(row, false, sizeof(row));memset(col, false, sizeof(col));memset(grid, false, sizeof(grid));*///注意题目说的是输入的是字符串,一开始没注意被坑惨了char Map[10][10];for (int i = 1; i <= 9; i++) {for (int j = 1; j <= 9; j++){cin >> Map[i][j];map[i][j] = Map[i][j] - '0'; //-'0'字符串变数字,+'0'数字变字符串,欸,不查资料还真记不住//初始化if (map[i][j]){//int k = query(i, j);//这个公式很好推的,加油int k = 3 * ((i - 1) / 3) + (j - 1) / 3 + 1;row[i][map[i][j]] = true;col[j][map[i][j]] = true;grid[k][map[i][j]] = true;}else {//对每行的索引用0的多少进行排列,首先要知道每行0的数量cnt[i].num++;cnt[i].row = i;}}}//每次填写0少的一行,我们玩数独也是这样玩的吧sort(cnt + 1, cnt + 9 + 1, cmp);//这是打印搜索行顺序代码/*for (int k = 1; k <= 9; k++) {cout << cnt[k].row<<" ";}cout<<endl;*///开始dfsDFS(cnt[1].row, 1,1,1);//记得将flag重置flag = false;}return 0;
}
相关文章:

dfs +剪枝sudoku———poj2676
目录 前言 lowbit函数 数独 suduku 问题描述 输入 输出 问题分析 子网格位置 优化搜索顺序剪枝1 优化搜索顺序剪枝2 可行性剪枝 代码 前言 lowbit函数 这是一个利用二进制位运算取出二进制数最后一位’1‘的函数 数独 数独大家肯定都玩过,…...
机器学习:关联规则:Apriori算法、FP - Growth算法的原理、应用场景及优缺点介绍
一、关联规则算法概述 关联规则挖掘是数据挖掘中的一个重要任务,用于发现数据集中不同项之间的关联关系。 二、Apriori算法 原理 频繁项集生成:Apriori算法基于一个先验原理,即如果一个项集是频繁的,那么它的所有子集也是频繁的…...
从0开始深度学习(7)——线性回归的简洁实现
在从0开始深度学习(5)——线性回归的逐步实现中,我们手动编写了数据构造模块、损失函数模块、优化器等,但是在现代深度学习框架下,这些已经包装好了 本章展示如果利用深度学习框架简洁的实现线性回归 0 导入头文件 im…...
【网络安全 | Java代码审计】华夏ERP(jshERP)v2.3
未经许可,不得转载。 文章目录 技术框架开发环境代码审计权限校验绕过SQL注入Fastjson反序列化命令执行存储型XSS越权/未授权重置密码越权/未授权删除用户信息越权/未授权修改用户信息会话固定安全建议项目地址:https://github.com/jishenghua/jshERP 技术框架 核心框架:Sp…...
Setting the value of ‘*‘ exceeded the quota
H5之localStorage限额报错quota_exceeded the quota-CSDN博客 Uncaught DOMException: Failed to set a named property on Storage: Setting the value of background exceeded the quota. 超出了 localStorage 的最大长度。...
前端页面模块修改成可动态生成数据模块——大部分数据为GPT生成(仅供学习参考)
前端页面模块修改成可动态生成数据模块: 这些案例展示了如何通过Blade模板将前端页面模块变成可动态生成的模板。通过巧妙使用Blade语法、控制结构、CSS/JS分离、组件复用等技巧,可以大大提高代码的灵活性和复用性。在Laravel的Controller中准备好数据并…...

5.错误处理在存储过程中的重要性(5/10)
错误处理在存储过程中的重要性 引言 在数据库编程中,存储过程是一种重要的组件,它允许用户将一系列SQL语句封装成一个单元,以便重用和简化数据库操作。然而,像任何编程任务一样,存储过程中的代码可能会遇到错误或异常…...

【WebGis开发 - Cesium】如何确保Cesium场景加载完毕
目录 引言一、监听场景加载进度1. 基础代码2. 加工代码 二、进一步封装代码1. 已知存在的弊端2. 封装hooks函数 三、使用hooks方法1. 先看下效果2. 如何使用该hooks方法 三、总结 引言 本篇为Cesium开发的一些小技巧。 判断Cesium场景是否加载完毕这件事是非常有意义的。 加载…...

【数据结构】6道经典链表面试题
目录 1.返回倒数第K个节点【链接】 代码实现 2.链表的回文结构【链接】 代码实现 3.相交链表【链接】 代码实现 4.判断链表中是否有环【链接】 代码实现 常见问题解析 5.寻找环的入口点【链接】 代码实现1 代码实现2 6.随机链表的复制【链接】 代码实现 1.…...

等保测评1.0到2.0的演变发展
中国等保测评的演变 作为中国强化网络安全监管制度的重要组成部分,信息安全等级保护测评不是一个新概念,可以追溯到1994年和2007年发布的多项管理规则(通常称为等保测评 1.0规则),根据这些规则,网络运营商…...
yum 源配置
在/etc/yum.repo.d目录下 格式: [repository_name] nameRepository description baseurlhttp://repository_url enabled1 gpgcheck0 gpgkeyfile:///etc/pki/rpm-gpg/RPM-GPG-KEY-CentOS-7 其中: [repository_name]:源的标识名称,…...

通过AI技术克服自动化测试难点(上)
本文我们一起分析一下AI技术如何解决现有的自动化测试工具的不足和我们衍生出来的新的测试需求。 首先我们一起看一下计算机视觉的发展历史,在上世纪70年代,处于技术萌芽期,由字符的识别技术慢慢进行演化,发展到现在,人…...
等保测评:如何建立有效的网络安全监测系统
等保测评中的网络安全监测系统建立 在建立等保测评中的网络安全监测系统时,应遵循以下步骤和策略: 确定安全等级和分类:首先,需要根据信息系统的安全性要求、资产的重要性和风险程度等因素,确定网络系统的安全等级&…...
yjs12——pandas缺失值的处理
1.缺失值的表示 正常来说,pandas缺失值是“nan”表示,但是有且文件可能自己改成了相应的别的符号 2.如何将缺失值符号改成nan xxx.replace(to_replace"...",valuenp.nan) 3.判断是否有缺失值 1.pd.notnull(xxx)————如果有缺失,…...
噪声分布 双峰,模拟函数 或者模拟方法 python人工智能 深度神经网络
在Python中模拟双峰分布,可以通过多种方法实现。以下是一些常用的方法: 1. **使用正态分布混合**: 可以通过组合两个正态分布来创建一个双峰分布。每个正态分布都有其自己的均值(mu)和标准差(sigma&…...

5个免费ppt模板网站推荐!轻松搞定职场ppt制作!
每次过完小长假,可以明显地感觉到,2024这一年很快又要结束了,不知此刻的你有何感想呢?是满载而归,还是准备着手制作年终总结ppt或年度汇报ppt呢? 每当说到制作ppt,很多人的第一反应,…...
HTML5+Css3(背景属性background)
css背景属性 background 1. background-color背景颜色 背景颜色可以用“十六进制”、“rgb()”、“rgba()”或“英文单词”表示 2. background-image:url(路径);背景图片 也可以写成 background:url(); 3. background-repeat背景重复 属性值: - repeat:x,y平铺…...

高亚科技助力优巨新材,打造高效数字化研发项目管理平台
近日,中国企业管理软件资深服务商高亚科技与广东优巨先进新材料股份有限公司(以下简称“优巨新材”)正式签署合作协议,共同推进产品研发管理数字化升级。此次合作的主要目标是通过8Manage PM项目管理系统,提升优巨新材…...

用布尔表达式巧解数字电路图
1.前置知识 明确AND,OR,XOR,NOR,NOT运算的规则 参见:E25.【C语言】练习:修改二进制序列的指定位 这里再补充一个布尔运算符:NOR,即先进行OR运算,再进行NOT运算 如下图为其数字电路的符号 注意到在OR符号的基础上,在尾部加了一个(其实由简化而来) 附:NOR的真值表 2.R-S触发…...
面试--开源框架面试题集合
Spring 谈谈自己对于 Spring IoC 的了解什么是 IoC?IoC 解决了什么问题?什么是 Spring Bean?将一个类声明为 Bean 的注解有哪些?Component 和 Bean 的区别是什么?注入 Bean 的注解有哪些?Autowired 和 Resource 的区别是什么?…...

7.4.分块查找
一.分块查找的算法思想: 1.实例: 以上述图片的顺序表为例, 该顺序表的数据元素从整体来看是乱序的,但如果把这些数据元素分成一块一块的小区间, 第一个区间[0,1]索引上的数据元素都是小于等于10的, 第二…...

【JavaEE】-- HTTP
1. HTTP是什么? HTTP(全称为"超文本传输协议")是一种应用非常广泛的应用层协议,HTTP是基于TCP协议的一种应用层协议。 应用层协议:是计算机网络协议栈中最高层的协议,它定义了运行在不同主机上…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)
可以使用Sqliteviz这个网站免费编写sql语句,它能够让用户直接在浏览器内练习SQL的语法,不需要安装任何软件。 链接如下: sqliteviz 注意: 在转写SQL语法时,关键字之间有一个特定的顺序,这个顺序会影响到…...
VTK如何让部分单位不可见
最近遇到一个需求,需要让一个vtkDataSet中的部分单元不可见,查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行,是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示,主要是最后一个参数,透明度…...

微信小程序云开发平台MySQL的连接方式
注:微信小程序云开发平台指的是腾讯云开发 先给结论:微信小程序云开发平台的MySQL,无法通过获取数据库连接信息的方式进行连接,连接只能通过云开发的SDK连接,具体要参考官方文档: 为什么? 因为…...

【Linux】Linux 系统默认的目录及作用说明
博主介绍:✌全网粉丝23W,CSDN博客专家、Java领域优质创作者,掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围:SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...

mac 安装homebrew (nvm 及git)
mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用: 方法一:使用 Homebrew 安装 Git(推荐) 步骤如下:打开终端(Terminal.app) 1.安装 Homebrew…...

[大语言模型]在个人电脑上部署ollama 并进行管理,最后配置AI程序开发助手.
ollama官网: 下载 https://ollama.com/ 安装 查看可以使用的模型 https://ollama.com/search 例如 https://ollama.com/library/deepseek-r1/tags # deepseek-r1:7bollama pull deepseek-r1:7b改token数量为409622 16384 ollama命令说明 ollama serve #:…...
Leetcode33( 搜索旋转排序数组)
题目表述 整数数组 nums 按升序排列,数组中的值 互不相同 。 在传递给函数之前,nums 在预先未知的某个下标 k(0 < k < nums.length)上进行了 旋转,使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...
十九、【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建
【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建 前言准备工作第一部分:回顾 Django 内置的 `User` 模型第二部分:设计并创建 `Role` 和 `UserProfile` 模型第三部分:创建 Serializers第四部分:创建 ViewSets第五部分:注册 API 路由第六部分:后端初步测…...