当前位置: 首页 > 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;它是以后端直接渲染模板完成响应为主的一种开发模式。以前后端不…...

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

华为云AI开发平台ModelArts

华为云ModelArts&#xff1a;重塑AI开发流程的“智能引擎”与“创新加速器”&#xff01; 在人工智能浪潮席卷全球的2025年&#xff0c;企业拥抱AI的意愿空前高涨&#xff0c;但技术门槛高、流程复杂、资源投入巨大的现实&#xff0c;却让许多创新构想止步于实验室。数据科学家…...

7.4.分块查找

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

【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15

缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下&#xff1a; struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...

Appium+python自动化(十六)- ADB命令

简介 Android 调试桥(adb)是多种用途的工具&#xff0c;该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具&#xff0c;其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利&#xff0c;如安装和调试…...

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...

【JavaWeb】Docker项目部署

引言 之前学习了Linux操作系统的常见命令&#xff0c;在Linux上安装软件&#xff0c;以及如何在Linux上部署一个单体项目&#xff0c;大多数同学都会有相同的感受&#xff0c;那就是麻烦。 核心体现在三点&#xff1a; 命令太多了&#xff0c;记不住 软件安装包名字复杂&…...

HubSpot推出与ChatGPT的深度集成引发兴奋与担忧

上周三&#xff0c;HubSpot宣布已构建与ChatGPT的深度集成&#xff0c;这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋&#xff0c;但同时也存在一些关于数据安全的担忧。 许多网络声音声称&#xff0c;这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...

高防服务器价格高原因分析

高防服务器的价格较高&#xff0c;主要是由于其特殊的防御机制、硬件配置、运营维护等多方面的综合成本。以下从技术、资源和服务三个维度详细解析高防服务器昂贵的原因&#xff1a; 一、硬件与技术投入 大带宽需求 DDoS攻击通过占用大量带宽资源瘫痪目标服务器&#xff0c;因此…...

React从基础入门到高级实战:React 实战项目 - 项目五:微前端与模块化架构

React 实战项目&#xff1a;微前端与模块化架构 欢迎来到 React 开发教程专栏 的第 30 篇&#xff01;在前 29 篇文章中&#xff0c;我们从 React 的基础概念逐步深入到高级技巧&#xff0c;涵盖了组件设计、状态管理、路由配置、性能优化和企业级应用等核心内容。这一次&…...