力扣37题:回溯算法之解数独

编写一个程序,通过填充空格来解决数独问题。

数独的解法需 遵循如下规则

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。(请参考示例图)

数独部分空格内已填入了数字,空白格用 '.' 表示。

大致思路:

枚举整个方格图形,对于每个空格的位置再枚举数字1-9,并判断是否符合数独的条件,如果符合则将该空格位置放入该数。当某个空格位置枚举数字1-9时都不满足数独条件,则说明该数独无解。当枚举到某个值而不满足数独条件时,则要进行回溯处理。当遍历完整个二维数组时,则填充出了满足数独条件的数独。

例如:从数字1-4中选择两个数分别填入红色格子和蓝色格子,使得出现的数字不重复。

回溯解题过程:

1.选择一个数填入红色格子

可见当选的数不满足条件时会进行回溯处理,最终红色格子填入2和4符合条件。所以要分别在此基础上选择一个数填入蓝色格子。

2.选一个数填入蓝色格子

最终只有两种填入方案符合条件。

回溯全过程图:

奉上本题代码:

int ROW,COL;//两个值可以直接改为9
bool IsValid(char**board,int row,int col,char k)//是否符合条件
{
    //行
    for(int i=0;i<COL;i++)
    {
        if(board[row][i]==k)
            return false;
    }
    //列
    for(int j=0;j<ROW;j++)
    {
        if(board[j][col]==k)
            return false;
    }
    //9宫格
    int startrow=row/3*3;
    int startcol=col/3*3;//九宫格的起始坐标
    for(int i=startrow;i<startrow+3;i++)
    {
        for(int j=startcol;j<startcol+3;j++)
        {
            if(board[i][j]==k)
                return false;
        }
    }
    return true;
}
bool bacjktracking(char**board)
{
    for(int i=0;i<ROW;i++)
    {
        for(int j=0;j<COL;j++)
        {
            if(board[i][j]=='.')//只能填入空格
            {
                for(char s='1';s<='9';s++)
                {
                    if(IsValid(board,i,j,s))
                    {
                        board[i][j]=s;
                        if(bacjktracking(board))//填入某个数符合条件
                            return true;
                        board[i][j]='.';
                    }
                }
                return false;//当某个格子填入任何数都不符合条件则,数独无解
            }
        }
    }
    return true;
}
void solveSudoku(char** board, int boardSize, int* boardColSize){
    ROW=boardSize;
    COL=*boardColSize;
    bool ans=bacjktracking(board);
}

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

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

相关文章

java-动态代理

为什么需要代理&#xff1f; 如何创建代理 注意&#xff1a;实现类和代理需要实现同一个接口 接口 public interface Star {String sing(String song);void dance(); }实现类 public class BigStar implements Star {private String name;public BigStar(String name) {this.…

开源博客项目Blog .NET Core源码学习(20:App.Hosting项目结构分析-8)

本文学习并分析App.Hosting项目中后台管理页面的个人资料页面、修改密码页面。 个人资料页面 个人资料页面用于显示和编辑个人信息&#xff0c;支持从本地上传个人头像。整个页面使用了layui中的表单、日期与时间选择、上传等样式或模块&#xff0c;通过layui.css文件设置样式…

精彩回顾|从 AI 到银幕:顶尖对话揭秘 AI 如何塑造影视新格局

4月17日&#xff0c;由万合天宜、三次元影业、NOVATECH、微软中国极客天团、微软 Reactor 共同推出的「从 AI 到银幕」顶尖对话在上海微软紫竹园区举办。中国内地著名导演、编剧、监制黄建新&#xff0c;微软&#xff08;中国&#xff09;有限公司首席技术官韦青&#xff0c;与…

基于SpringBoot+Vue高校实习管理系统的设计与实现

项目介绍&#xff1a; 如今社会上各行各业&#xff0c;都喜欢用自己行业的专属软件工作&#xff0c;互联网发展到这个时候&#xff0c;人们已经发现离不开了互联网。新技术的产生&#xff0c;往往能解决一些老技术的弊端问题。因为传统高校实习管理系统信息管理难度大&#xf…

atlas 500容器(ubuntu20.04)搭建

1.docker 及环境搭建略 2.宿主机驱动安装略 3.宿主机中能正确使用npu-smi 4.docker 拉取略 5.docker 容器启动 docker run -itd --device/dev/davinci0 --device/dev/davinci_manager --device/dev/devmm_svm --device/dev/hisi_hdc -v /run/board_cfg.ini:/run/b…

吴恩达2022机器学习专项课程(一)7.2 逻辑回归的简化成本函数

问题预览/关键词 本节课内容逻辑回归的损失函数简化之后的形式是&#xff1f;为什么可以简化&#xff1f;成本函数的通用形式是&#xff1f;逻辑回归成本函数的最终形式是&#xff1f;逻辑回归为什么用对数损失函数计算成本函数&#xff1f;为什么不直接给出逻辑回归损失函数的…

银河麒麟V10 ARM64 离线安装 新版Docker

查询当前发行版本 nkvers下载最新版本 卸载旧依赖 卸载已经安装的老版本 yum remove docker \containerd.io \docker-runc \docker-client \docker-client-latest \docker-common \docker-latest \docker-latest-logrotate \docker-logrotate \docker-engine \docker-compo…

【数据结构7-1-查找-线性-二分法-二叉树-哈希表】

目录 1 查找基本概念2 线性表的查找2.1 顺序查找2.2 二分法查找2.3 分块查找 3 树表的查询3.1 二叉排序树3.1.1 定义3.1.2 二叉树的建立、遍历、查找、增加、删除&#xff1a;3.1.3 代码实现&#xff1a; 3.2 平衡二叉树3.2.1 平横因子3.2.2 不平横树的调整-左旋3.2.3 不平横树…

c++高级篇(三) ——Linux下IO多路复用之poll模型

poll模型 前言 poll模型与select的实现原理相近&#xff0c;所以绝大数的原理其实可以参考select&#xff0c;我们这里对二者的相同点不做过多探究&#xff0c;如果有需要可以去看一下博主的上一篇文章&#xff1a; c高级篇(二) ——Linux下IO多路复用之select模型 这里我们只…

【Jenkins】持续集成与交付 (三):有关报错解决(Jenkins (2.387.3) or higher required)

🟣【Jenkins】持续集成与交付 (三):有关报错解决Jenkins (2.387.3) or higher required 一、Jenkins主页报错二、安装Jenkins插件报错三、解决过程(解压替换jenkins.war)四、重新访问登录💖The Begin💖点点关注,收藏不迷路💖 一、Jenkins主页报错 New version …

51单片机两个中断及中断嵌套

文章目录 前言一、中断嵌套是什么&#xff1f;二、两个同级别中断2.1 中断运行关系2.2 测试程序 三、两个不同级别中断实现中断嵌套3.1 中断运行关系3.2 测试程序 总结 前言 提示&#xff1a;这里可以添加本文要记录的大概内容&#xff1a; 课程需要&#xff1a; 提示&#x…

【电路笔记】-RC振荡器电路

RC振荡器电路 文章目录 RC振荡器电路1、概述2、RC 相移网络3、基本RC振荡器电路4、运算放大器RC振荡器5、运算放大器相位滞后RC振荡器电路6、RC振荡器示例11、概述 RC 振荡器使用放大器和 RC 反馈网络的组合,由于级之间的相移而产生输出振荡。 当单级晶体管放大器作为共发射…

疯狂的爬虫案例(2)文末附源码

软件版本号&#xff1a; python --version Python 3.8.0 pip show selenium Version: 4.20.0 chromedriver.exe -version 109.0.5414.74 主题&#xff1a;爬取10条动态网页内容&#xff08;电影票房&#xff09; 1.根据xpath获取网页节点&#xff08;CtrlF&#xff09; 2.…

spring高级篇(五)

1、参数解析器 前篇提到过&#xff0c;参数解析器是HandlerAdapters中的组件&#xff0c;用于解析controller层方法中加了注解的参数信息。 有一个controller&#xff0c;方法的参数加上了各种注解&#xff1a; public class Controller {public void test(RequestParam("…

Python-100-Days: Day06 Functions and Modules

函数的作用 编程大师Martin Fowler先生曾经说过&#xff1a;“代码有很多种坏味道&#xff0c;重复是最坏的一种&#xff01;”&#xff0c;要写出高质量的代码首先要解决的就是重复代码的问题。可以将特定的功能封装到一个称之为“函数”的功能模块中&#xff0c;在需要的时候…

MyBatis(环境配置+基本CRUD)

文章目录 1.基本介绍1.为什么需要MyBatis&#xff1f;2.MyBatis介绍3.MyBatis工作示意图4.MyBatis的优势 2.快速入门文件目录1.需求分析2.数据库表设计3.父子模块环境配置1.创建maven父项目2.删除父项目的src目录3.pom.xml文件文件解释 4.创建子模块1.新建一个Module2.创建一个…

面向对象编程三大特征:封装、继承、多态

封装、继承、多态 1. 封装 1.1 介绍 封装(encapsulation)就是把抽象出的数据 [属性] 和对数据的操作 [方法] 封装在一起,数据被保护在内部,程序的其它部分只有通过被授权的操作 [方法] ,才能对数据进行操作。 1.2 封装的理解和好处 1) 隐藏实现细节:方法(连接数据库)<…

UE Snap03 启动参数设置

UE Snap03 启动参数设置 UE打包后传入自定义参数及解析。 void UGameInstance::StartGameInstance() {Super::StartGameInstance();UE_LOG(LogTemp, Warning, TEXT("--StartGameInstance--"));FString param;FParse::Value(FCommandLine::Get(), TEXT("-UserN…

Python | Leetcode Python题解之第50题Pow(x,n)

题目&#xff1a; 题解&#xff1a; class Solution:def myPow(self, x: float, n: int) -> float:def quickMul(N):ans 1.0# 贡献的初始值为 xx_contribute x# 在对 N 进行二进制拆分的同时计算答案while N > 0:if N % 2 1:# 如果 N 二进制表示的最低位为 1&#xf…

新手一文掌握 ea怎么注册?ea官网注册账号的详细教程

新手一文掌握 ea怎么注册&#xff1f;ea官网注册账号的详细教程 知名游戏平台EA平台&#xff0c;说到这个各位游戏玩家肯定不会陌生是全球知名的互动娱乐软件公司美国艺电&#xff08;Electronic Arts&#xff09;旗下的游戏平台。该平台主营电子游戏的开发、出版和销售业务&…