大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全家桶1年46,售后保障稳定
数独问题描述
标准的数独游戏是在一个 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账号...