package hlc.shudu.src;/* * 數獨的幫助類，里面提供數據所需的所有算法 */public class ShuduHelper { //數獨地圖數組 private static int[][] maps = new int[9][9]; //每個小九宮格可放置位置的數 private static int[] canPutSum = new int[9]; //用來存儲之前放置過的位置 static int[] used = new int[9]; //是否已經完成地圖的生成 static boolean isOk = true; /*  * 得到數獨地圖數組  */ public static int[][] getMap() { //判斷是否已經完成地圖的生成，要是沒有完成就重新生成。 //從這里就可以看出算法還有待優化，如果回溯的好的話就一直可以通過回溯來重新生成，而這里是通過重新執行生成算法來重新生成。希望感興趣的朋友可以去實現以下。  do{   isOk = true;   initMaps();  }while(!isOk);  return maps; } /*  * 初始化maps  */ private static void initMaps() {  // 初始化地圖數組中沒有填入任何數字  for (int i = 0; i < 9; i++) {   for (int j = 0; j < 9; j++) {    maps[i][j] = -1;   }  }  // 依次填入1~9  for (int num = 1; num <= 9; num++) {   for (int i = 0; i < 9; i++) {    used[i] = -1;    canPutSum[i] = -1;   }   // 遍歷大九宮格中的每個小九宮格   for (int i = 0; i < 9; i++) {    if (canPutSum[i]==-1) {     canPutSum[i] = getCanPutSum(i, num);    }    if (canPutSum[i]==1) {     used[i] = -1;    }    if (canPutSum[i] == 0) {     canPutSum[i] = -1;     used[i] = -1;     // 如果當前小九宮格中不能放入數字num，則回到前一個小九宮格     if (i > 0) {      // 將前一個九宮格中放num的位置清空      if (used[i-1]!=-1) {       //maps[(int) (Math.floor(used[i-1]/3)+Math.floor((i-1)/3)*3)][used[i-1]%3+((i-1)%3)*3]=-1;       clearNum(i - 1, num);      }      // i回退一個，因為等會for循環灰給i加一，所以這里減2      i -= 2;      continue;     } else {      isOk = false;      return;     }    } else {     // 將num放入當前小九宮格中     boolean flag = false;     while (!flag) {      int j = (int) (Math.random() * 9);      // 當前小方格橫坐標      int ii = (i / 3) * 3 + j / 3;      // 當前小方格縱坐標      int jj = (i % 3) * 3 + j % 3;      //System.out.println("num:"+num+"/tii:"+ii+"/tjj:"+jj);      // 如果可以放置num則放置      if (maps[ii][jj] == -1 && j!=used[i] && isCanPut(ii, jj, num)) {       maps[ii][jj] = num;       used[i] = j;       canPutSum[i] -= 1;       flag = true;      }     }    }   }  } } /*  * 清空第i個小九宮格中的num  */ private static void clearNum(int i, int num) {  for (int j = 0; j < 9; j++) {   // 當前小方格橫坐標   int ii = (i / 3) * 3 + j / 3;   // 當前小方格縱坐標   int jj = (i % 3) * 3 + j % 3;   // 判斷當前小方格是否可以放置   if (maps[ii][jj] == num) {    maps[ii][jj] = -1;   }  } } /*  * 得到當前小九宮格可以放入數字num的位置數目  */ private static int getCanPutSum(int i, int num) {  int sum = 0;  // 遍歷小九宮格  for (int j = 0; j < 9; j++) {   // 當前小方格橫坐標   int ii = (i / 3) * 3 + j / 3;   // 當前小方格縱坐標   int jj = i % 3 * 3 + j % 3;   // 判斷當前小方格是否可以放置   if (maps[ii][jj] == -1 && isCanPut(ii, jj, num)) {    ++sum;   }  }  return sum; } /*  * 指定橫縱坐標點是否可以放置num  */ private static boolean isCanPut(int ii, int jj, int num) {  // 判斷指定坐標點的同行或同列是否有相同數字，要是有則為false  for (int i = 0; i < 9; i++) {   if (maps[ii][i] == num) {    return false;   }   if (maps[i][jj] == num) {    return false;   }  }  return true; }}