当前位置: 首页 > news >正文

dfs +剪枝sudoku———poj2676

目录

前言

   lowbit函数

   数独         

suduku

   问题描述    

   输入

   输出

问题分析

   子网格位置

   优化搜索顺序剪枝1

   优化搜索顺序剪枝2

   可行性剪枝

代码


前言

   lowbit函数

                这是一个利用二进制位运算取出二进制数最后一位’1‘的函数

   数独         

        数独大家肯定都玩过,本题就是利用计算机尝试模拟人做数独游戏时的情形,每次从空白最少的行开始填写,每次填写都比对这个数字是否符合要求,如果没有符合要求的数字,则重新填写上一个数字,大家可以回忆下做数独时的情形,也可以为剪枝提供思路

suduku

   问题描述    

         给定一个9*9的网格,又将该网格细分为九个3*3的子网格,现给出部分数字,编写程序填满该网格,要求每行,每列,每个子网格,只能出现1~9中的数字,且每行,每列,每个子网格中不能有重复的数字,若有多个答案,只输出其中一个即可。

   输入

        有多个测试用例,第一行输入一个整数t,代表测试个数,对于每个测试,输入一个9*9的字符串数组

   输出

        输出一种符合条件的答案

问题分析

   子网格位置

        首先要解决子网格位置问题,给定一个点(x,y)的坐标给如何知道该点位于哪个子网格中,我们先对各个子网格编号

123
456
789

然后我们再找规律:

最笨但是最实用的方法就是用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‘的函数 数独 数独大家肯定都玩过&#xff0c;…...

机器学习:关联规则:Apriori算法、FP - Growth算法的原理、应用场景及优缺点介绍

一、关联规则算法概述 关联规则挖掘是数据挖掘中的一个重要任务&#xff0c;用于发现数据集中不同项之间的关联关系。 二、Apriori算法 原理 频繁项集生成&#xff1a;Apriori算法基于一个先验原理&#xff0c;即如果一个项集是频繁的&#xff0c;那么它的所有子集也是频繁的…...

从0开始深度学习(7)——线性回归的简洁实现

在从0开始深度学习&#xff08;5&#xff09;——线性回归的逐步实现中&#xff0c;我们手动编写了数据构造模块、损失函数模块、优化器等&#xff0c;但是在现代深度学习框架下&#xff0c;这些已经包装好了 本章展示如果利用深度学习框架简洁的实现线性回归 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生成(仅供学习参考)

前端页面模块修改成可动态生成数据模块&#xff1a; 这些案例展示了如何通过Blade模板将前端页面模块变成可动态生成的模板。通过巧妙使用Blade语法、控制结构、CSS/JS分离、组件复用等技巧&#xff0c;可以大大提高代码的灵活性和复用性。在Laravel的Controller中准备好数据并…...

5.错误处理在存储过程中的重要性(5/10)

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

【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的演变发展

中国等保测评的演变 作为中国强化网络安全监管制度的重要组成部分&#xff0c;信息安全等级保护测评不是一个新概念&#xff0c;可以追溯到1994年和2007年发布的多项管理规则&#xff08;通常称为等保测评 1.0规则&#xff09;&#xff0c;根据这些规则&#xff0c;网络运营商…...

yum 源配置

在/etc/yum.repo.d目录下 格式&#xff1a; [repository_name] nameRepository description baseurlhttp://repository_url enabled1 gpgcheck0 gpgkeyfile:///etc/pki/rpm-gpg/RPM-GPG-KEY-CentOS-7 其中&#xff1a; [repository_name]&#xff1a;源的标识名称&#xff0c;…...

通过AI技术克服自动化测试难点(上)

本文我们一起分析一下AI技术如何解决现有的自动化测试工具的不足和我们衍生出来的新的测试需求。 首先我们一起看一下计算机视觉的发展历史&#xff0c;在上世纪70年代&#xff0c;处于技术萌芽期&#xff0c;由字符的识别技术慢慢进行演化&#xff0c;发展到现在&#xff0c;人…...

等保测评:如何建立有效的网络安全监测系统

等保测评中的网络安全监测系统建立 在建立等保测评中的网络安全监测系统时&#xff0c;应遵循以下步骤和策略&#xff1a; 确定安全等级和分类&#xff1a;首先&#xff0c;需要根据信息系统的安全性要求、资产的重要性和风险程度等因素&#xff0c;确定网络系统的安全等级&…...

yjs12——pandas缺失值的处理

1.缺失值的表示 正常来说&#xff0c;pandas缺失值是“nan”表示&#xff0c;但是有且文件可能自己改成了相应的别的符号 2.如何将缺失值符号改成nan xxx.replace(to_replace"...",valuenp.nan) 3.判断是否有缺失值 1.pd.notnull(xxx)————如果有缺失&#xff0c;…...

噪声分布 双峰,模拟函数 或者模拟方法 python人工智能 深度神经网络

在Python中模拟双峰分布&#xff0c;可以通过多种方法实现。以下是一些常用的方法&#xff1a; 1. **使用正态分布混合**&#xff1a; 可以通过组合两个正态分布来创建一个双峰分布。每个正态分布都有其自己的均值&#xff08;mu&#xff09;和标准差&#xff08;sigma&…...

5个免费ppt模板网站推荐!轻松搞定职场ppt制作!

每次过完小长假&#xff0c;可以明显地感觉到&#xff0c;2024这一年很快又要结束了&#xff0c;不知此刻的你有何感想呢&#xff1f;是满载而归&#xff0c;还是准备着手制作年终总结ppt或年度汇报ppt呢&#xff1f; 每当说到制作ppt&#xff0c;很多人的第一反应&#xff0c…...

HTML5+Css3(背景属性background)

css背景属性 background 1. background-color背景颜色 背景颜色可以用“十六进制”、“rgb()”、“rgba()”或“英文单词”表示 2. background-image:url(路径);背景图片 也可以写成 background:url(); 3. background-repeat背景重复 属性值&#xff1a; - repeat:x,y平铺…...

高亚科技助力优巨新材,打造高效数字化研发项目管理平台

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

用布尔表达式巧解数字电路图

1.前置知识 明确AND,OR,XOR,NOR,NOT运算的规则 参见:E25.【C语言】练习:修改二进制序列的指定位 这里再补充一个布尔运算符:NOR,即先进行OR运算,再进行NOT运算 如下图为其数字电路的符号 注意到在OR符号的基础上,在尾部加了一个(其实由简化而来) 附:NOR的真值表 2.R-S触发…...

面试--开源框架面试题集合

Spring 谈谈自己对于 Spring IoC 的了解什么是 IoC?IoC 解决了什么问题?什么是 Spring Bean&#xff1f;将一个类声明为 Bean 的注解有哪些?Component 和 Bean 的区别是什么&#xff1f;注入 Bean 的注解有哪些&#xff1f;Autowired 和 Resource 的区别是什么&#xff1f;…...

练习(含atoi的模拟实现,自定义类型等练习)

一、结构体大小的计算及位段 &#xff08;结构体大小计算及位段 详解请看&#xff1a;自定义类型&#xff1a;结构体进阶-CSDN博客&#xff09; 1.在32位系统环境&#xff0c;编译选项为4字节对齐&#xff0c;那么sizeof(A)和sizeof(B)是多少&#xff1f; #pragma pack(4)st…...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

css3笔记 (1) 自用

outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size&#xff1a;0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格&#xff…...

Yolov8 目标检测蒸馏学习记录

yolov8系列模型蒸馏基本流程&#xff0c;代码下载&#xff1a;这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中&#xff0c;**知识蒸馏&#xff08;Knowledge Distillation&#xff09;**被广泛应用&#xff0c;作为提升模型…...

tomcat入门

1 tomcat 是什么 apache开发的web服务器可以为java web程序提供运行环境tomcat是一款高效&#xff0c;稳定&#xff0c;易于使用的web服务器tomcathttp服务器Servlet服务器 2 tomcat 目录介绍 -bin #存放tomcat的脚本 -conf #存放tomcat的配置文件 ---catalina.policy #to…...

Monorepo架构: Nx Cloud 扩展能力与缓存加速

借助 Nx Cloud 实现项目协同与加速构建 1 &#xff09; 缓存工作原理分析 在了解了本地缓存和远程缓存之后&#xff0c;我们来探究缓存是如何工作的。以计算文件的哈希串为例&#xff0c;若后续运行任务时文件哈希串未变&#xff0c;系统会直接使用对应的输出和制品文件。 2 …...

用 Rust 重写 Linux 内核模块实战:迈向安全内核的新篇章

用 Rust 重写 Linux 内核模块实战&#xff1a;迈向安全内核的新篇章 ​​摘要&#xff1a;​​ 操作系统内核的安全性、稳定性至关重要。传统 Linux 内核模块开发长期依赖于 C 语言&#xff0c;受限于 C 语言本身的内存安全和并发安全问题&#xff0c;开发复杂模块极易引入难以…...

李沐--动手学深度学习--GRU

1.GRU从零开始实现 #9.1.2GRU从零开始实现 import torch from torch import nn from d2l import torch as d2l#首先读取 8.5节中使用的时间机器数据集 batch_size,num_steps 32,35 train_iter,vocab d2l.load_data_time_machine(batch_size,num_steps) #初始化模型参数 def …...