java版數(shù)獨(dú)游戲核心算法（一）

package hlc.shudu.src;

/*
 * 數(shù)獨(dú)的幫助類，里面提供數(shù)據(jù)所需的所有算法
 */
public class ShuduHelper {
 //數(shù)獨(dú)地圖數(shù)組
 private static int[][] maps = new int[9][9];
 //每個(gè)小九宮格可放置位置的數(shù)
 private static int[] canPutSum = new int[9];
 //用來(lái)存儲(chǔ)之前放置過(guò)的位置
 static int[] used = new int[9];
 //是否已經(jīng)完成地圖的生成
 static boolean isOk = true;

 /*
  * 得到數(shù)獨(dú)地圖數(shù)組
  */
 public static int[][] getMap() {
 //判斷是否已經(jīng)完成地圖的生成，要是沒(méi)有完成就重新生成。
 //從這里就可以看出算法還有待優(yōu)化，如果回溯的好的話就一直可以通過(guò)回溯來(lái)重新生成，而這里是通過(guò)重新執(zhí)行生成算法來(lái)重新生成。希望感興趣的朋友可以去實(shí)現(xiàn)以下。
  do{
   isOk = true;
   initMaps();
  }while(!isOk);
  return maps;
 }

 /*
  * 初始化maps
  */
 private static void initMaps() {
  // 初始化地圖數(shù)組中沒(méi)有填入任何數(shù)字
  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;
   }
   // 遍歷大九宮格中的每個(gè)小九宮格
   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;
     // 如果當(dāng)前小九宮格中不能放入數(shù)字num，則回到前一個(gè)小九宮格
     if (i > 0) {
      // 將前一個(gè)九宮格中放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回退一個(gè)，因?yàn)榈葧?huì)for循環(huán)灰給i加一，所以這里減2
      i -= 2;
      continue;
     } else {
      isOk = false;
      return;
     }
    } else {
     // 將num放入當(dāng)前小九宮格中
     boolean flag = false;
     while (!flag) {
      int j = (int) (Math.random() * 9);
      // 當(dāng)前小方格橫坐標(biāo)
      int ii = (i / 3) * 3 + j / 3;
      // 當(dāng)前小方格縱坐標(biāo)
      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個(gè)小九宮格中的num
  */
 private static void clearNum(int i, int num) {
  for (int j = 0; j < 9; j++) {
   // 當(dāng)前小方格橫坐標(biāo)
   int ii = (i / 3) * 3 + j / 3;
   // 當(dāng)前小方格縱坐標(biāo)
   int jj = (i % 3) * 3 + j % 3;
   // 判斷當(dāng)前小方格是否可以放置
   if (maps[ii][jj] == num) {
    maps[ii][jj] = -1;
   }
  }

 }

 /*
  * 得到當(dāng)前小九宮格可以放入數(shù)字num的位置數(shù)目
  */
 private static int getCanPutSum(int i, int num) {
  int sum = 0;
  // 遍歷小九宮格
  for (int j = 0; j < 9; j++) {
   // 當(dāng)前小方格橫坐標(biāo)
   int ii = (i / 3) * 3 + j / 3;
   // 當(dāng)前小方格縱坐標(biāo)
   int jj = i % 3 * 3 + j % 3;
   // 判斷當(dāng)前小方格是否可以放置
   if (maps[ii][jj] == -1 && isCanPut(ii, jj, num)) {
    ++sum;
   }
  }

  return sum;

 }

 /*
  * 指定橫縱坐標(biāo)點(diǎn)是否可以放置num
  */
 private static boolean isCanPut(int ii, int jj, int num) {
  // 判斷指定坐標(biāo)點(diǎn)的同行或同列是否有相同數(shù)字，要是有則為false
  for (int i = 0; i < 9; i++) {
   if (maps[ii][i] == num) {
    return false;
   }
   if (maps[i][jj] == num) {
    return false;
   }
  }
  return true;
 }
}