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

搜索经典题——填充 9*9矩阵

题目:给定一个九行九列矩阵,填充矩阵元素,要求:

1、每一行每一列,每个小九宫格(图片画粗的地方就是)不能包含相同元素

2、每一行,每一列,每个小九宫格均会完整出现1-9的数字 

思路:DFS回溯填充数字,一行一行填充,当填充到第十行说明填充成功,每填充一个位置,都需要用"istrue"函数验证一下该位置是否合法(需要判断每一行,每一列,每个小九宫格是否包含了相同元素,唯一难点就是判断当前填充位置的小九宫格起点位置)  

//分治回溯 回溯的应用 之 数独问题
/*
判断填入的数据是否满足条件 一行中没有相同的 并且 一列中没有相同的 并且 当前方格所在的子方块中没有相同的
虽然数独问题只有一个解 但是我们解决数独问题时 是向多个解的方向去求解的*/
public class SudoKu {//表示第count个解private static int count = 0;//表示存放数独数据的矩阵容器private static int[][] board= new int[9][9];public static void main(String[] args) throws IOException {readFile("SudoKu_data"); //读取数独文件solve(0, 0); //向数独矩阵中添加元素}//向数独矩阵中添加元素/*向下一个位置递归的 列的更新为:col=(col+1)%9行的更新:更新行必须将col递归到当前行的末尾时才能更新 更新为:row=row+(col+1)/9先判断递归临界条件 当行row递归到9时 则表示已经出现了一个解了否则判断指定位置(row,col)是否已经有数字了如果已经有数字了 直接跳过当前位置 向下一个位置继续递归即可否则 循环数字1-9 判断指定位置能够填入的数字(1-9中的哪个数字) 将其填入再向下一个位置继续递归即可当一种填法行不通时 必须要将当前位置填入的数字清空后 再向上回溯*/private static void solve(int row, int col) {if(row == 9){ //判断递归临界条件count++;System.out.println("第" + count + "个解");printBoard();}else{//如果当前位置没有数字if(board[row][col] == 0){//就要填入1-9中满足条件的数字for(int num = 1; num <= 9; num++){//判断当前位置要填入的数字 是否满足条件/*条件:一行中没有与要填入的数字num相同的 并且 一列中没有与要填入的数字num相同的并且 当前方格所在的子方块中没有与要填入的数字num相同的*/if(!isExist(row, col, num)){//将满足条件的数字填入到指定位置board[row][col] = num;//向下递归 解决下一个格子solve(row + (col + 1) / 9, (col + 1) % 9);}board[row][col] = 0; //如果此处没解 必须清零此处的数字}}else{//已经存在一个已知数字 直接跳过去解决下一个格子solve(row + (col + 1) / 9, (col + 1) % 9);}}}/*判断当前位置要填入的数字 是否满足条件 如果指定范围中包含要添加的数字 则返回true若没有包含 表示可以将数字添加到指定方格中 返回false*/private static boolean isExist(int row, int col, int num) {//同一行中是否包含指定元素numfor(int c = 0; c < 9; c++){if(board[row][c] == num){return true;}}//同一列中是否包含指定元素numfor(int r = 0; r < 9; r++){if(board[r][col] == num){return true;}}//在子方格(九宫格)中是否包含指定元素num 若总共是9*9 则就有九个3*3的子方格int rowMin = 0; //子方格中最小行的编号,默认值为0int colMin = 0; //子方格中最小列的编号,默认值为0int rowMax = 0; //子方格中最大行的编号,默认值为0int colMax = 0; //子方格中最大列的编号,默认值为0//设置子方格中的最小行,最小列,最大行,最大列的值 即子方格的行 列范围if(row >= 0 && row <= 2){rowMin = 0;rowMax = 2;}if(row >= 3 && row <= 5){rowMin = 3;rowMax = 5;}if(row >= 6 && row <= 8){rowMin = 6;rowMax = 8;}if(col >= 0 && col <= 2){colMin = 0;colMax = 2;}if(col >= 3 && col <= 5){colMin = 3;colMax = 5;}if(col >= 6 && col <= 8){colMin = 6;colMax = 8;}//遍历子方格 判断其中是否包含指定元素numfor(int r = rowMin; r <= rowMax; r++){for(int c = colMin; c < colMax; c++){if(board[r][c] == num){return true;}}}//若以上条件都不满足 则返回false 表示指定位置可以填入数字return false;}//读取文件中的数独矩阵private static void readFile(String fileName) throws IOException {File file = new File(fileName);FileReader fr = new FileReader(file);BufferedReader br = new BufferedReader(fr);int row = 0;String line = null;while ((line = br.readLine()) != null){for(int col = 0; col < line.length(); col++){board[row][col] = Integer.parseInt(line.charAt(col) + "");}row++;}}//打印数独矩阵private static void printBoard() {for(int i = 0; i < 9; i++){for(int j = 0; j < 9; j++){System.out.print(board[i][j] + " ");}System.out.println();}}
}

相关文章:

搜索经典题——填充 9*9矩阵

题目&#xff1a;给定一个九行九列矩阵&#xff0c;填充矩阵元素&#xff0c;要求&#xff1a; 1、每一行每一列&#xff0c;每个小九宫格&#xff08;图片画粗的地方就是&#xff09;不能包含相同元素 2、每一行&#xff0c;每一列&#xff0c;每个小九宫格均会完整出现1-9的数…...

Vue待办事项(组件,模块化)

//html页面代码 <!DOCTYPE html> <html> <head> <meta charset"utf-8"> <title></title> <style> * { padding: 0; margin: 0; }…...

Vue中的组件

在应用程序的开发中&#xff0c;组件是不可缺少的。在Vue的使用中&#xff0c;同样也会用到组件。   vue组件的一般知识点&#xff1a;   1、组件的名字唯一&#xff1b;   2、组件以Html形式书写&#xff1b;   3、组件可以复用&#xff1b;   4、组件可以嵌套&…...

svg矢量图标在wpf中的使用

在wpf应用程序开发中&#xff0c;为支持图标的矢量缩放&#xff0c;及在不同分辨率下界面中图标元素的矢量无损缩放&#xff0c;所以常常用到svg图标&#xff0c;那么如果完 美的将svg图标运用到wpf日常的项目开发中呢&#xff0c;这里分享一下我的个人使用经验和详细步骤。 步…...

如何在云端加速缓存构建

缓存是指将某类数据存储起来以便以后重复使用的过程&#xff0c;它的运用在开发场景中非常普遍。类似于你习惯把最常用的调料放在厨房台面上&#xff0c;而不是橱柜里&#xff0c;这样你在准备大餐时就可以轻松取用。 但对于一个更为技术性、更精确的用例&#xff0c;比如像谷…...

JavaWeb-Cookie与Session

一、概念 是否还记得我们在HTTP概念中提到&#xff1a;HTTP的一大特点是无状态&#xff0c;这意味着多次HTTP请求之间是无法共享数据的。而在请求之间共享一些数据又是我们期望达到的效果。&#xff08;例如登录的记住我功能&#xff09;于是便有了会话跟踪技术&#xff0c;而…...

ZABBIX根据IP列表,主机描述,或IP子网批量创建主机的维护任务

有时候被ZABBIX监控的主机可能需要关机重启等维护操作,为了在此期间不触发告警,需要创建主机的维护任务,以免出现误告警 ZABBIX本身有这个API可供调用(不同版本细节略有不同,本次用的ZABBIX6.*),实现批量化建立主机的维护任务 无论哪种方式(IP列表,主机描述,或IP子网)创建维护…...

PMIS_ENT_STD

...

32 登录页组件

效果演示 实现了一个登录页面的样式&#xff0c;包括一个容器、左侧和右侧部分。左侧部分是一个背景图片&#xff0c;右侧部分是一个表单&#xff0c;包括输入框、复选框、按钮和忘记密码链接。整个页面的背景色为白色&#xff0c;容器为一个圆角矩形&#xff0c;表单为一个半透…...

Docker(一)简介和基本概念:什么是 Docker?用它会带来什么样的好处?

作者主页&#xff1a; 正函数的个人主页 文章收录专栏&#xff1a; Docker 欢迎大家点赞 &#x1f44d; 收藏 ⭐ 加关注哦&#xff01; 一、简介 本章将带领你进入 Docker 的世界。 什么是 Docker&#xff1f; 用它会带来什么样的好处&#xff1f; 好吧&#xff0c;让我们带…...

【Linux】进程的概念 进程状态 进程优先级

Content 一、什么是进程1. 进程的概念2. 进程的描述 - 进程控制块&#xff08;PCB&#xff09;3. Linux下的进程 二、进程状态1. 教科书中的进程状态运行状态阻塞状态挂起状态 2. Linux下的进程状态R&#xff08;running&#xff09;- 运行状态S&#xff08;sleeping) - 睡眠状…...

Go语言热重载和优雅地关闭程序

Go语言热重载和优雅地关闭程序 我们有时会因不同的目的去关闭服务&#xff0c;一种关闭服务是终止操作系统&#xff0c;一种关闭服务是用来更新配置。 我们希望优雅地关闭服务和通过热重载重新加载配置&#xff0c;而这两种方式可以通过信号包来完成。 1、代码实现 package…...

Python实现两个列表相加的方法汇总

1. 使用 “” 运算符 通过 “” 运算符将两个列表相加&#xff0c;得到一个新的列表。例如&#xff1a; list1 [1, 2, 3] list2 [4, 5, 6] result list1 list2 print(result) # [1, 2, 3, 4, 5, 6]2. 使用 extend 方法 使用 extend 方法将一个列表中的元素逐个添加到另…...

debian12.4配置

文章目录 debian12.4配置概述笔记将非root用户添加到sudo组更换国内源配置ssh的客户端访问END debian12.4配置 概述 在虚拟机中装了一个debian12.4, 想配置ssh客户端连接, 出了问题. 配置乱了, 还好长了个心眼, 做了快照. 发现2个问题: debian12.4默认安装完, 有ssh, 先检查…...

linux切换root用户su - root和su root的区别

这里说一下login shell和 no login shell的区别 通过tty客户端登陆的shell就是login shell&#xff0c;通过在图形界面使用ctrlshiftt的方式新建的shell是no login shell login shell 主要读取两个配置文件/etc/profile和~/.bash_profile no login shell 读取的文件和顺序为&am…...

SQL Server Management Studio创建数据表

文章目录 一、建表注意事项1.1 数据类型1.2 建立数据表的基本SQL语法 二、实例说明2.1 创建数据表2.2 实例2 三、标识列和主键示例&#xff1a; 一、建表注意事项 1.1 数据类型 可以看这个去了解数据类型&#xff1a; 1.2 建立数据表的基本SQL语法 建立数据表的基本 SQL 语…...

【AI的未来 - AI Agent系列】【MetaGPT】4.1 细说我在ActionNode实战中踩的那些坑

文章目录 1. MetaGPT 0.5.2 版本的坑1.1 坑一&#xff1a;cannot import name "ActionNode" from "metagpt.actions.action"1.2 坑二&#xff1a;simple_fill 没有参数 schema1.3 坑三&#xff1a;ActionNode一直在循环执行&#xff0c; 2. 升级成 MetaGP…...

Android学习(五):常用控件

Android学习&#xff08;五&#xff09;&#xff1a;常用控件 常用控件 TextViewEditTextButtonRadioButtonImageView 1、TextView控件 1.1、简介 TextView是用于显示文字(字符串)的控件&#xff0c;可在代码中通过设置属性改变文字的大小、颜色、样式等功能。 1.2、示例…...

基于YOLOv8的学生课堂行为检测,引入BRA注意力和Shape IoU改进提升检测能力

&#x1f4a1;&#x1f4a1;&#x1f4a1;本文摘要&#xff1a;介绍了学生课堂行为检测&#xff0c;并使用YOLOv8进行训练模型&#xff0c;以及引入BRA注意力和最新的Shape IoU提升检测能力 1.SCB介绍 摘要&#xff1a;利用深度学习方法自动检测学生的课堂行为是分析学生课堂表…...

【前后端分离与不分离的区别】

Web 应用的开发主要有两种模式&#xff1a; 前后端不分离 前后端分离 理解它们的区别有助于我们进行对应产品的测试工作。 前后端不分离 在早期&#xff0c;Web 应用开发主要采用前后端不分离的方式&#xff0c;它是以后端直接渲染模板完成响应为主的一种开发模式。以前后端不…...

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例

使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件&#xff0c;常用于在两个集合之间进行数据转移&#xff0c;如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model&#xff1a;绑定右侧列表的值&…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

PL0语法,分析器实现!

简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...

【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)

要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况&#xff0c;可以通过以下几种方式模拟或触发&#xff1a; 1. 增加CPU负载 运行大量计算密集型任务&#xff0c;例如&#xff1a; 使用多线程循环执行复杂计算&#xff08;如数学运算、加密解密等&#xff09;。运行图…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

什么是Ansible Jinja2

理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具&#xff0c;可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板&#xff0c;允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板&#xff0c;并通…...

Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问&#xff08;基础概念问题&#xff09; 1. 请解释Spring框架的核心容器是什么&#xff1f;它在Spring中起到什么作用&#xff1f; Spring框架的核心容器是IoC容器&#…...

Web中间件--tomcat学习

Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机&#xff0c;它可以执行Java字节码。Java虚拟机是Java平台的一部分&#xff0c;Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...

BLEU评分:机器翻译质量评估的黄金标准

BLEU评分&#xff1a;机器翻译质量评估的黄金标准 1. 引言 在自然语言处理(NLP)领域&#xff0c;衡量一个机器翻译模型的性能至关重要。BLEU (Bilingual Evaluation Understudy) 作为一种自动化评估指标&#xff0c;自2002年由IBM的Kishore Papineni等人提出以来&#xff0c;…...