数独解法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)


相关推荐

  • 渗透测试工具下载

    渗透测试工具下载好多工具资源

  • Centos7磁盘阵列部署与修复「建议收藏」

    Centos7磁盘阵列部署与修复「建议收藏」Centos7磁盘阵列部署与修复一、部署RAID10#1、虚拟机添加4块20G的硬盘设备#2、mdadm命令,其中-n4代表使用4块磁盘,-l10代表使用RAID10技术mdadm-Cv/dev/md0-ayes-n4-l10/dev/sdb/dev/sdc/dev/sdd/dev/sde#3、制作好的RAID磁盘阵列格式化为ext4mkfs.ext4/dev/md0#4、创建挂载点,进行磁盘设备挂载mkdir/RAIDmount/dev/md0/RA

  • 进程处于挂起状态表示_挂起进程转换图

    进程处于挂起状态表示_挂起进程转换图文章目录引言挂起状态是什么?挂起状态和阻塞状态有什么区别?如何主动挂起程序总结引言以前对于这个概念始终比较模糊,遂在解决后记录博客,希望帮助到有同样问题的朋友。挂起状态是什么?我们一般认为进程有五个状态,即新建态,就绪态,阻塞态,运行态,终止态。而在这些状态之外还存在着一个状态,我们称之为挂起状态,它既可以是我们客户主动使得进程挂起,也可以是操作系统因为某些原因使得进程挂起。总而言之引入挂起状态的原因有以下几种:用户的请求:可能是在程序运行期间发现了可疑的问题,需要暂停进程。父进程的请求:

    2022年10月29日
  • JDBC预处理对象prepareStatement[通俗易懂]

    JDBC预处理对象prepareStatement[通俗易懂]JDBC预处理对象prepareStatement概述一、SQL注入问题SQL注入:用户输入的内容作为了SQL语句语法的一部分,改变了原有SQL真正的意义。假设有登录案例SQL语句如下:SELECT*FROM用户表WHERENAME=用户输入的用户名ANDPASSWORD=用户输的密码;此时,当用户输入正确的账号与密码后,查询到了信息则让用户登录。但是当用户输入的账…

  • openwrt旁路由的设置「建议收藏」

    openwrt旁路由的设置「建议收藏」1:旁路由必须和主路由在同一网段2:旁路由的网关必须指向主路由3:防火墙开启IP动态伪装

  • mysql 多表删除

    mysql 多表删除

发表回复

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

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