数独解法Java实现「建议收藏」

数独解法Java实现「建议收藏」数独问题描述标准的数独游戏是在一个9X9的棋盘上填写1–9这9个数字,规则是这样的:棋盘分成上图所示的9个区域(不同颜色做背景标出,每个区域是3X3的子棋盘),在每个子棋盘中填充1–9且不允许重复,下面简称块重复每一行不许有重复值,下面简称行重复每一列不许有重复值,下面简称列重复如上红色框出的子区域中的亮黄色格子

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46,售后保障稳定

数独问题描述

sudoku_1

标准的数独游戏是在一个 9 X 9 的棋盘上填写 1 – 9 这 9 个数字,规则是这样的:

  • 棋盘分成上图所示的 9 个区域(不同颜色做背景标出,每个区域是 3 X 3 的子棋盘),在每个子棋盘中填充 1 – 9 且不允许重复 ,下面简称块重复
  • 每一行不许有重复值 ,下面简称行重复
  • 每一列不许有重复值 ,下面简称列重复

如上红色框出的子区域中的亮黄色格子只能填 8。

解决思路一描述:

1.使用二维数组表示数独,不确定的数使用0填充。

2.从位置(0,0)开始遍历二维数组。

3.跳过已确定的数字,直到找到第一个不确定的数(即数值0)。如果找不到不确定的数字,则表示数独已填充完成。

4.根据当前数值0的位置,排除到同行、同列、同一个小宫格中已经出现的数字,得到当前位置所有允许填充的数字。

5.如果不存在允许填充的数字,则当前数独无解。

6.尝试填充每一个允许的数字,并递归填充下一个不确定的数字。

7.如果递归填充成功,返回成功。

8.如果递归填充失败,回退步骤6中填充的数字,并跳转到6继续尝试下一个允许的数字。

相关代码后续补充。

缺点:数独中每一个未确定的值都需要递归穷举,最大的递归层级等于未确定值的数目。

改进方式:每填充一个值,在递归填充之前,动态计算每个待填充值的候选数字,删除不再符合规则的候选数字。如果有位置的候选数字为空,则数独无解。如果有位置的候选数字只有唯一一个,则直接填充该数字。通过上述两种方式可以有效减少递归的层次。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/234906.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • Memwatch使用说明

    Memwatch使用说明linux下的测试工具真是少之又少,还不好用,最近试用了memwatch,感觉网上的介绍不太好,所以放在这里跟大家分享 。其实大部分都是看的帮助,很多地方翻译得不好还有错,请原谅指出最好看原文。如果转载或引用,请注明我的博客地址,谢谢。 1介绍MemWatch由 Johan Lindh 编写,是一个开放源代码 C 语言内存错误检测工具。MemWatch支持 ANSI C,它提供结果日志纪录

  • 魔兽世界端口怎么禁止(服务器端口怎么开)

    匿名用户1级2009-03-11回答cn4.grunt.wowchina.com,3724121.14.80.114,121.14.80.115,121.14.80.116,121.14.80.109121.14.80.110,121.14.80.111,121.14.80.112,121.14.80.113[二/六区],cn6.grunt.wowchina.comcn6.grun…

  • mysql 提示表不存在的解决方法error: 1146: Table doesn‘t exist

    mysql 提示表不存在的解决方法error: 1146: Table doesn‘t exist直接拷贝数据库导致提示表不存在的解决方法电脑重装系统后把原来的mysqldata复制进去后大部分表是可以访问的,但是有几个表提示表不存在:error:1146:Table’a_content’doesn’texist这种情况就是要把原来mysql安装目录data里的ibdata1也要拷贝过去INNODB是MYSQL数据库一种流行的数据库引擎,支持事务(行级),在企业级应…

  • FAT32文件系统结构详解[通俗易懂]

    FAT32文件系统结构详解[通俗易懂]1.SD卡中FAT32文件系统快速入门1.1.理论知识1.1.1.MBR(MainBootRecord)主引导记录,占446字节,为计算机启动后从可启动介质上首先装入内存并且执行的代码,通常用来解释分区结构1.1.2.DBR(DOSBootRecord)DOS引导记录,为操作系统进入文件系统以后可以访问的第一个扇区,通常用来解释文件系统,DBR是由硬盘的MBR装…

    2022年10月22日
  • Fuel 5.1安装openstack I版本号环境

    Fuel 5.1安装openstack I版本号环境

  • mysql主从复制原理面试_数据库主从复制 读写分离

    mysql主从复制原理面试_数据库主从复制 读写分离为什么要做主从复制在业务复杂的系统中,有这么一个情景,有一句sql语句需要锁表,导致暂时不能使用读的服务,那么就很影响运行中的业务,使用主从复制,让主库负责写,从库负责读,这样,即使主库出现了锁表的情景,通过读从库也可以保证业务的正常运行。做数据的热备,主库宕机后能够及时替换主库,保证业务可用性。架构的扩展。业务量越来越大,I/O访问频率过高,单机无法满足,此时做多库的存储,降低磁盘I/O……

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号