java使用回溯法求解数独示例
发布时间:2023-08-17 14:39:10
import java.util.Calendar;
import java.util.Date;
public class Matrix {
private int matrix[][];
private long timeAfter=0;
private long timeBefore =0;
public Matrix(int m[][]) {
matrix = new int[9][9];
for (int i=0; i<9 ; i++)
for(int j= 0; j<9; j++)
matrix[i][j]=m[i][j];
this.timeBefore = Calendar.getInstance().getTimeInMillis();
}
public void backTrack(int i, int j)
{
//回收系统内存资源
System.gc();
if( i==8 && j>=9 )
{
this.timeAfter = Calendar.getInstance().getTimeInMillis();
//成功输出矩阵
this.showMatrix();
return;
}
if(j == 9) {j = 0; i++;}
if(matrix[i][j] == 0)
{
//数字为零
for(int k=1; k<=9; k++)
{
if(bound(i,j,k))
{
matrix[i][j] = k ;
//符合条件,查找下一个方格
backTrack(i,j+1);
matrix[i][j] = 0 ;
}
}
}else
{
//数字不为零,直接查找下一个
backTrack(i, j+1);
}
}
/**
* 判断要填入的数字和同行同列以及同一九宫格内数字是否重复
*/
private boolean bound(int i, int j, int k) {
int m = i/3;
int n = j/3;
for(int p = 0; p<9; p++)
{
if(k == matrix[i][p])
{
return false;
}
if(k == matrix[p][j])
{
return false;
}
if(k == matrix[3*m+p/3][3*n+p%3])
{
return false;
}
}
return true;
}
/**
* 打印解题时间
* @return
*/
public long printTime()
{
return this.timeAfter-this.timeBefore;
}
/**
* 打印矩阵
*/
public void showMatrix()
{
for(int i=0; i<9; i++)
{
for(int j=0; j<9; j++)
{
System.out.print(matrix[i][j]+" ");
}
System.out.println ();
}
System.out.println ();
System.out.println("解题时间: "+printTime()+"毫秒");
System.out.println ();
}
public static void main(String[] args) {
int matrix[][] = {
{3,0,6,0,5,7,0,0,0},
{7,9,0,0,2,4,0,0,0},
{0,5,0,6,0,0,9,7,4},
{8,0,1,0,0,9,0,0,0},
{0,2,0,3,0,8,0,0,7},
{4,0,0,0,6,0,5,0,0},
{0,0,4,0,3,6,0,5,0},
{2,0,3,7,0,5,0,0,1},
{0,0,7,4,1,0,6,0,0}};
int ma1[][]={
{0,3,0,0,0,5,0,6,0},
{0,1,0,0,0,3,0,8,0},
{0,4,0,0,0,0,0,0,7},
{0,0,7,0,2,4,0,0,0},
{5,0,0,0,9,0,0,0,0},
{0,8,0,3,0,0,5,0,0},
{0,0,0,8,0,0,0,0,0},
{0,0,9,0,0,0,0,7,3},
{0,5,0,9,0,0,0,0,2}};
int ma2[][]={
{0,0,0,0,8,4,0,0,0},//8
{0,0,0,2,0,3,0,8,0},
{8,3,0,9,0,0,0,5,0},
{0,5,3,0,9,0,7,0,0},
{0,0,0,6,3,7,0,4,5},//7
{0,7,0,5,0,0,0,0,0},
{0,0,6,8,0,0,0,0,0},
{3,0,0,0,2,9,0,0,0},
{2,0,9,3,0,0,0,0,1}};//3
// 号称世界上最难数独
int[][] sudoku = {
{ 8, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 3, 6, 0, 0, 0, 0, 0 },
{ 0, 7, 0, 0, 9, 0, 2, 0, 0 },
{ 0, 5, 0, 0, 0, 7, 0, 0, 0 },
{ 0, 0, 0, 0, 4, 5, 7, 0, 0 },
{ 0, 0, 0, 1, 0, 6, 0, 3, 0 },
{ 0, 0, 1, 0, 0, 0, 0, 6, 8 },
{ 0, 0, 8, 5, 0, 0, 0, 1, 0 },
{ 0, 9, 0, 0, 0, 0, 4, 0, 0 }};
Matrix m = new Matrix(sudoku);
m.backTrack(0, 0);
}
}
![](https://www.aspxhome.com/images/zang.png)
![](https://www.aspxhome.com/images/jiucuo.png)
猜你喜欢
- 一、前言环境:jdk 1.8,SpringCloud Greenwich.SR2。如题,springcloud config-client启
- Java读取json数据并存入数据库1. pom依赖<dependency> &nbs
- 本文实例为大家分享了Unity Shader实现黑幕过场效果的具体代码,供大家参考,具体内容如下一、效果演示二、实现Shader:黑幕过场着
- ActiveMQ 结合 Spring 收发消息直接使用 ActiveMQ 的方式需要重复写很多代码,且不利于管理,Spring 提供了一种更
- 一、引言大家都知道单例模式,通过一个全局变量来避免重复创建对象而产生的消耗,若系统存在大量的相似对象时,又该如何处理?参照单例模式,可通过对
- 我在5月份的时候就申请了洞态IAST企业版内测,算是比较早的一批用户了。聊聊几个我比较在意的问题,比如API接口覆盖率、第三方开源组件检测以
- instanceof判断某个对象是否是某个类的实例或者某个类的子类的实例。它的判断方式大概是这样的:public<T> bool
- 在网站开发中经常遇到级联数据的展示,比如选择城市的时候弹出的省市县选择界面。很多前端制作人员习惯于从JSON中而不是从数据库中获
- 前言泛型在java中有很重要的地位,无论是开源框架还是JDK源码都能看到它。毫不夸张的说,泛型是通用设计上必不可少的元素,所以真正理解与正确
- 知乎是一个真实的网络问答社区,社区氛围友好、理性、认真,连接各行各业的精英。他们分享着彼此的专业知识、经验和见解,为中文互联网源源不断地提供
- 介绍记录将elasticsearch集成到spring boot的过程,以及一些简单的应用和helper类使用。接入方式使用spring-b
- 本Demo为练手小项目,主要是熟悉目前主流APP的架构模式.此项目中采用MVC设计模式,纯代码和少许XIB方式实现.主要实现了朋友圈功能和摇
- 一、问题分析入门案例的内容已经做完了,在入门案例中我们创建过一个SpringMvcConfig的配置类,再回想前面咱们学习Spring的时候
- 1、阿里云DNS的SDK依赖<dependency> <groupId>com.aliyu
- SpringBoot读取外置logback配置文件springboot项目可以读取外置配置文件,避免了修改配置文件需要重新打包部署的问题。部
- MyBatis是一个支持普通SQL查询,存储过程和高级映射的优秀持久层框架。MyBatis消除了几乎所有的JDBC代码和参数的手工设置以及对
- 本文实例为大家分享了Java实现简单GUI登录和注册界面的具体代码,供大家参考,具体内容如下先看效果图:登陆界面:注册界面:实现代码如下:一
- 一. 假设需求场景在我们开发的过程中,经常出现两个对象存在一对多或多对一的关系。如何在程序在表明这两个对象的关系,以及如何利用这种关系优雅地
- 1、继承Thread类方式这种方式适用于执行特定任务,并且需要获取处理后的数据的场景。举例:一个用于累加数组内数据的和的线程。public
- 最近项目上用就hibernate+spring data jpa,一开始感觉还不错,但是随着对业务的复杂,要求处理一些复杂的sql,就顺便研