Tip：sourceInput為數獨的初始狀態，可以自行更改
package mySuduku;import java.util.ArrayList;import java.util.List;public class All { public static void main(String args[]){ /* * 初始數據（map） */ int sourceInput[][]={ {0,0,7,0,5,0,0,0,0}, {6,0,0,2,0,1,7,0,0}, {0,1,2,0,0,0,4,0,8}, {3,2,4,0,0,0,1,0,0}, {0,0,0,0,0,0,0,0,0}, {0,0,0,0,6,0,8,0,0}, {0,0,0,5,0,0,3,0,0}, {7,0,0,8,0,0,0,4,0}, {8,4,0,0,0,3,5,7,0}}; /* 用來分析的map * 后期可以填補，以便簡化map */ int inputMap[][]=new int[9][9]; /* * 分析使用的map（使map不能再優化） * analyInputMap[x][y][z]中xy對應inputMap[x][y],[z]中1-9代表1-9的可能性， * 10代表這個數是否在原map中已經存在 */ int analyInputMap[][][]=new int[9][9][10]; //與分析的map做比較用的 int tempAnalyMap[][][]=new int[9][9][10]; //比較兩個map（這個看是否是優化為最終結果） boolean compareInputToTemp=true; //將sourceInput塞入inputMap中 setSameMap(sourceInput,inputMap,9,9); /* * 去除inputMap中有的值 * 即置analyInputMap[x][y][z]中的z位為該數(map[x][y])不可用 */ deleteFromMap(sourceInput,analyInputMap); /* * 兩步刪除不可能的結果 * 兩步分別指： 1對所有剩下的空白格，求出其可能的數值， * 2當其可能數值僅有一種時，更新inputMap填上這一種，然后將analyInputMap進行調整 * 當輸入和輸出的值一樣的時候認為無法再進一步簡化 */ while(compareInputToTemp){ //賦值inputMap到tempMap setSameMap(analyInputMap,tempAnalyMap,9,9,10); //檢查是否可以進一步簡化 arrange(inputMap,analyInputMap); //判斷上步簡化是否確實發生了變化 compareInputToTemp=compareAB(analyInputMap,tempAnalyMap,9,9,10); PRintMap(inputMap,9,9); printMap(analyInputMap,9,9,9); } /* * while后結果可視為初步最優解，此時考慮遍歷所有剩下的可能情況，用countRest記錄剩余空白格 * 對每個空白格需記錄這么幾個項：1坐標（即x,y）,2可能的數字 * 這里采用一個類（theRest）記錄 * 類中的X,Y記錄坐標，avaiable記錄可能的數值 * * 最后，用List<theRest> theRestNumber裝下所有theRest */ //剩下還有多少空沒有填 int countRest=0; //每個填的數字需要用個數據結構(類theRest) List<theRest> theRestNumber=new ArrayList<theRest>(); //一個暫時的temp指針，指向一個theRest類，這里先設置了，減小開銷 theRest temp; for(int i=0;i<9;i++) for(int j=0;j<9;j++) if(inputMap[i][j]==0){ countRest++; temp=new theRest(i,j); for(int k=0;k<9;k++){ if(analyInputMap[i][j][k]==0) temp.avaiable.add(k+1); } theRestNumber.add(temp); } //試試一個數字 tryANumber(inputMap,countRest,countRest,theRestNumber); } /* * 試試一個number * 整體思路如下，輸入參數為map（最終優化后結果），計數，整體theRestNumber的length，theRestNumber * 出口就是填滿所有數字(由于是先檢查，再填數字，所以最后不用檢查) */ public static void tryANumber(int[][] map,int nowRest,int allRestNum,List<theRest> theRestNumber){/* printMap(map,9,9);*/ if(nowRest==0){ printMap(map,9,9); } else if(allRestNum-nowRest>=0&&allRestNum!=0){ theRest temp=theRestNumber.get(allRestNum-nowRest); boolean flag=false; int i; for(i=0;i<temp.avaiable.size();i++){ flag=check(map,temp,temp.avaiable.get(i)); //如果值是可用的，則將值放入，并進行下一次的迭代 if(flag) { map[temp.x][temp.y]=temp.avaiable.get(i); tryANumber(map,nowRest-1,allRestNum,theRestNumber); //當try遍歷完成后，將嘗試的值置空 map[temp.x][temp.y]=0; } } } } //檢查放入一個number以后是否可行 public static boolean check(int[][] map,theRest temp,int tryNumber){ boolean flag=true; //檢查橫行和豎行是否有數字已經要嘗試的數字了 for(int i=0;i<9;i++) if(map[temp.x][i]==tryNumber||map[i][temp.y]==tryNumber) flag=false; //排除坐標對應3*3格中有沒有嘗試的數字 int tempx=temp.x/3; int tempy=temp.y/3; for (int i=0;i<3;i++) for(int j=0;j<3;j++) if(map[tempx*3+i][tempy*3+j]==tryNumber) flag=false; return flag; } //從分析的map中刪除map中有的元素(即置標簽位（z=9）為空) public static void deleteFromMap(int[][] source,int[][][] target){ for(int i=0;i<9;i++) for(int j=0;j<9;j++) if(source[i][j]!=0) target[i][j][9]=1; }; /* * 安置函數，入參是inputMap,和analyInputMap * 當a(即inputMap)每出現一個數字時，在對應的b（即analyInputMap）中進行相應動作(controlB) * 該動作排除a出現后限制b中的可能性（即a中空白處對應的可能數字要相應減少） * 在動作后，對b經行遍歷，發現若a的空白處可填項僅有一個時，對a進行填項，填項后對b的該坐標位置不可填 */ public static void arrange(int[][] a,int[][][]b){ for(int i=0;i<9;i++) for(int j=0;j<9;j++) if(a[i][j]!=0) controlB(i,j,a[i][j],b); //是否a的空白出只有一個可填項 int countIsOnly; //對b經行遍歷，發現若a的空白處可填項僅有一個時，對a進行填項，填項后對b的該坐標位置不可填 for(int i=0;i<9;i++) for(int j=0;j<9;j++) if(a[i][j]==0&&b[i][j][9]!=1){ countIsOnly=9; //循環，發現1則減去，當8個1時，說明只有一個可填，填項 for(int k=0;k<9;k++) countIsOnly-=b[i][j][k]; if(countIsOnly==1){ for(int k=0;k<9;k++) if(b[i][j][k]==0) a[i][j]=k+1; b[i][j][9]=1; } } } public static void controlB(int x,int y,int value,int[][][] b){ for(int i=0;i<9;i++){ //排除每行第x個字 b[x][i][value-1]=1; //排除每列第x個字 b[i][y][value-1]=1; } //排除坐標對應的3*3格 int tempx=x/3; int tempy=y/3; for (int i=0;i<3;i++) for(int j=0;j<3;j++){ b[tempx*3+i][tempy*3+j][value-1]=1; } } //復制二維數組函數，不多說 public static void setSameMap(int[][]source,int[][]target,int x,int y){ for(int i=0;i<x;i++) for(int j=0;j<y;j++) target[i][j]=source[i][j]; } //復制三位數組函數，不多說 public static void setSameMap(int[][][]source,int[][][]target,int x,int y,int z){ for(int i=0;i<x;i++) for(int j=0;j<y;j++) for(int k=0;k<z;k++) target[i][j][k]=source[i][j][k]; } //比較二維數組函數，不多說 public static boolean compareAB(int[][]a,int[][] b,int x,int y){ boolean flag=true; for(int i=0;i<x;i++) for(int j=0;j<y;j++) if(b[i][j]!=a[i][j]) flag=false; return flag; } //比較三維數組函數，不多說 public static boolean compareAB(int[][][]a,int[][][] b,int x,int y,int z){ boolean flag=false; for(int i=0;i<x;i++) for(int j=0;j<y;j++) for(int k=0;k<z;k++) if(b[i][j][k]!=a[i][j][k]) flag=true; return flag; } //打印二維map，不多說 public static void printMap(int[][] map,int x,int y){ for(int i=0;i<x;i++){ System.out.println(); for(int j=0;j<y;j++){ System.out.print(map[i][j]+" "); } } System.out.println(); } //打印三維map，不多說 public static void printMap(int[][][] map,int x,int y,int z){ for(int i=0;i<x;i++){ System.out.println(); for(int j=0;j<y;j++){ if(map[i][j][9]!=1){ System.out.print("map【"+i+"】:"+"【"+j+"】:"); for(int k=0;k<9;k++){ if(map[i][j][k]!=1) System.out.print(k+1); System.out.print(" "); } } } } System.out.println(); }} /* * 一個簡單類，用裝剩余空白格的信息 * x,y記錄空白處的坐標 * avaiable記錄可填充的數字 */class theRest{ public int x; public int y; public List<Integer> avaiable=new ArrayList<Integer>(); public int getX() { return x; } public void setX(int x) { this.x = x; } public int getY() { return y; } public void setY(int y) { this.y = y; } public theRest(int x, int y) { super(); this.x = x; this.y = y; }}新聞熱點
疑難解答
