当前位置： 移动技术网 > IT编程>开发语言>Java > java使用回溯法求解数独示例

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

2019年07月22日  | 移动技术网IT编程  | 我要评论

复制代码 代码如下:

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

}

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网