java使用回溯法求解数独示例

代码如下:

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);
 }

}

(0)

相关推荐

  • java求100之内的素数(质数)简单示例

    质数又称素数.一个大于1的自然数,如果除了1和它自身外,不能被其他自然数整除的数:否则称为合数.根据算术基本定理,每一个比1大的整数,要么本身是一个质数,要么可以写成一系列质数的乘积:而且如果不考虑这些质数在乘积中的顺序,那么写出来的形式是唯一的.下面是一个java求100之内的素数简单示例 复制代码 代码如下: public class test { public static void main(String[] args) {  int i,n,k=0;     for (n = 3; n

  • java 二维数组矩阵乘法的实现方法

    复制代码 代码如下: public interface IMatrixMultiple {     public int[][] mmltiple(int[][]a ,int [][]b); } ?public class MatrixMultiple implements IMatrixMultiple { @Override    public int[][] mmltiple(int[][] a, int[][] b) {         int [][] result = new int

  • java实现任意矩阵Strassen算法

    本例输入为两个任意尺寸的矩阵m * n, n * m,输出为两个矩阵的乘积.计算任意尺寸矩阵相乘时,使用了Strassen算法.程序为自编,经过测试,请放心使用.基本算法是: 1.对于方阵(正方形矩阵),找到最大的l, 使得l = 2 ^ k, k为整数并且l < m.边长为l的方形矩阵则采用Strassen算法,其余部分以及方形矩阵中遗漏的部分用蛮力法. 2.对于非方阵,依照行列相应添加0使其成为方阵. StrassenMethodTest.java package matrixalgorit

  • java数据结构与算法之双向循环队列的数组实现方法

    本文实例讲述了java数据结构与算法之双向循环队列的数组实现方法.分享给大家供大家参考,具体如下: 需要说明的是此算法我并没有测试过,这里给出的相当于伪代码的算法思想,所以只能用来作为参考! package source; public class Deque { private int maxSize; private int left; private int right; private int nItems; private long[] myDeque; //constructor p

  • java 矩阵乘法的mapreduce程序实现

    java 矩阵乘法的mapreduce程序实现 map函数:对于矩阵M中的每个元素m(ij),产生一系列的key-value对<(i,k),(M,j,m(ij))> 其中k=1,2.....知道矩阵N的总列数;对于矩阵N中的每个元素n(jk),产生一系列的key-value对<(i , k) , (N , j ,n(jk)>, 其中i=1,2.......直到i=1,2.......直到矩阵M的总列数. map package com.cb.matrix; import stati

  • java求数组最大值和最小数示例分享

    复制代码 代码如下: /** * 判断数组中的最大数 * @param args * @return */public static int getMaxNum(int args[]){int max=0;for(int i=0;i<args.length;i++){if(args[i]>args[max])max=i;}return args[max];} /** * 判断数组中的最小数 * @param args * @return */public static int getMinNu

  • Java中打乱一个数组的2种公平算法分享

    公平算法,打乱数组 这是前几天面试的时候遇见的一道题目,看到这个题首先想到了洗牌程序: 方法一:洗牌程序原理 在java.util包中的Collections类中的 shuffle方法,现在手工实现以下代码如下: package test.ms; import java.util.Random; public class Redistribute2 { public static void main(String[] args) { //define the array int[] s = {1

  • 简单讲解奇偶排序算法及在Java数组中的实现

    奇偶排序是一个比较有个性的排序,基本思路是奇数列排一趟序,偶数列排一趟序,再奇数排,再偶数排,直到全部有序 举例吧, 待排数组 [6 2 4 1 5 9] 第一次比较奇数列,奇数列与它的邻居偶数列比较,如6和2比,4和1比,5和9比 [6 2 4 1 5 9] 交换后变成 [2 6 1 4 5 9] 第二次比较偶数列,即6和1比,5和5比 [2 6 1 4 5 9] 交换后变成 [2 1 6 4 5 9] 第三趟又是奇数列,选择的是2,6,5分别与它们的邻居列比较 [2 1 6 4 5 9] 交

  • Java实现求小于n的质数的3种方法

    质数概念 质数,又称素数,指在一个大于1的自然数中,除了1和此整数自身外,无法被其他自然数整除的数(也可定义为只有1和本身两个因数的数). 最小的素数是2,也是素数中唯一的偶数:其他素数都是奇数.质数有无限多个,所以不存在最大的质数. 一:根据定义去求解: 也是最笨的方式,效率比较低: package test.ms; public class FindPrime { // find the prime between 1 to 1000; public static void main(Str

  • Java实现的求逆矩阵算法示例

    本文实例讲述了Java实现的求逆矩阵算法.分享给大家供大家参考,具体如下: package demo; public class MatrixInverse { public static double Det(double [][]Matrix,int N)//计算n阶行列式(N=n-1) { int T0; int T1; int T2; double Num; int Cha; double [][] B; if(N>0) { Cha=0; B=new double[N][N]; Num=

  • 详解Java数据结构和算法(有序数组和二分查找)

    一.概述 有序数组中常常用到二分查找,能提高查找的速度.今天,我们用顺序查找和二分查找实现数组的增删改查. 二.有序数组的优缺点 优点:查找速度比无序数组快多了 缺点:插入时要按排序方式把后面的数据进行移动 三.有序数组和无序数组共同优缺点 删除数据时必须把后面的数据向前移动来填补删除项的漏洞 四.代码实现 public class OrderArray { private int nElemes; //记录数组长度 private long[] a; /** * 构造函数里面初始化数组 赋值默

  • Java对数组实现选择排序算法的实例详解

    一. 算法描述     选择排序:比如在一个长度为N的无序数组中,在第一趟遍历N个数据,找出其中最小的数值与第一个元素交换,第二趟遍历剩下的N-1个数据,找出其中最小的数值与第二个元素交换......第N-1趟遍历剩下的2个数据,找出其中最小的数值与第N-1个元素交换,至此选择排序完成. 以下面5个无序的数据为例: 56 12 80 91 20(文中仅细化了第一趟的选择过程) 第1趟:12 56 80 91 20 第2趟:12 20 80 91 56 第3趟:12 20 56 91 80 第4趟

随机推荐