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

}