欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2024-02-15 20:17:28
复制代码 代码如下:import java.util.calendar;import java.util.date; public class matrix { &nb...

复制代码 代码如下:

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

}