芬蘭數(shù)學(xué)家因卡拉花費(fèi)3個(gè)月設(shè)計(jì)出了世界上迄今難度最大的數(shù)獨(dú)游戲，而且它只有一個(gè)答案。因卡拉說(shuō)只有思考能力最快、頭腦最聰明的人才能破解這個(gè)游戲。

今日，一則騰訊的新聞稱中國(guó)老頭三天破解世界最難九宮格，雖然最后老人是改了一個(gè)數(shù)字，但是引起本人一時(shí)興趣，想通過(guò)計(jì)算機(jī)程序求解該問(wèn)題，于是在宿舍呆了一下午，終于成功求解，程序源碼如下。

package numberGame; public class Point { private int col;// 行號(hào) private int row;// 列號(hào) private boolean flag;// 真為未設(shè)置。 private int value; // 構(gòu)造點(diǎn) public Point(int col, int row, boolean flag, int value) { super(); this.col = col; this.row = row; this.flag = flag; this.value = value; } public void changeFlag() { flag = !flag; } public boolean getFlag() { return flag; } public int getValue() { return value; } public void setValue(int value) { this.value = value; } public boolean canHere(Point[][] pArr) { boolean cb = canCol(pArr); boolean cr = canRow(pArr); boolean cminiArr = canMiniArr(pArr); return cb && cr && cminiArr; } //判斷在小3*3格子里是否有相同元素 private boolean canMiniArr(Point[][] pArr) { int coltemp = this.col % 3; int rowtemp = this.row % 3; for (int i = this.col - coltemp; i < col + (3 - coltemp); i++) { for (int j = this.row - rowtemp; j < row + (3 - rowtemp); j++) { if(i == this.col && j == this.row){ continue; }else{ if(this.value == pArr[i][j].getValue()){ return false; }} } } return true; } // 判斷列上是否有相同元素 private boolean canRow(Point[][] pArr) { for (int i = 0; i < 9; i++) { if (i == this.col) { continue; } else { if (this.value == pArr[i][this.row].value) {// 行變，列不變 return false; } } } return true; } // 判斷行上是否有相同元素 private boolean canCol(Point[][] pArr) { for (int i = 0; i < 9; i++) { if (i == this.row) { continue; } else { if (this.value == pArr[this.col][i].value) {// 列邊，行不變 return false; } } } return true; } }

—–主程序

package numberGame; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; public class Number99 { public static void main(String[] args) throws IOException{ Point[][] numMat = new Point[9][9]; ArrayList<Point> al = new ArrayList<Point>(); initNumMat(numMat,al); setNum(numMat,al); printMat(numMat); } private static void setNum(Point[][] numMat,ArrayList<Point> al) { int i = 0; int j = 0; do{ if (numMat[i][j].getFlag()) { for (int v = numMat[i][j].getValue()+1; v <= 9; v++) {//給回退到的位置的值加一。 numMat[i][j].setValue(v); if (numMat[i][j].canHere(numMat)) {//滿足條件，不沖突。 numMat[i][j].changeFlag();//改變標(biāo)記為假。表示已設(shè)置過(guò)。 break; }else{//滿足不條件，沖突。value值自加一次 }while(v == 9){//如果1-9都不能滿足要求，則先將本位重置為0，并回退一格,給回退到的位置的值加一（當(dāng)回退位置的值不為9時(shí),并且保證回退到的位置不是九宮格原本的點(diǎn)）。 numMat[i][j].setValue(0); j--; if(j==-1){ i--;j=8; } while(al.contains(numMat[i][j])){//如果回退到的位置為九宮格本來(lái)的點(diǎn)時(shí)，繼續(xù)回退，直到不是本身的點(diǎn)時(shí)跳出while。 j--; if(j==-1){ i--;j=8; } } numMat[i][j].changeFlag();//將標(biāo)記 v = numMat[i][j].getValue(); } }} j++; if(j==9){ j=0;i++;//此處i++ 可能使i自加為9，故下面需要i!=9判斷 } if(i!=9){ while(al.contains(numMat[i][j])){ j++; if(j==9){ j=0;i++; } } } }while(i!=9); } public static void initNumMat(Point[][] numMat,ArrayList<Point> al) throws IOException { for (int i = 0; i < numMat.length; i++) { for (int j = 0; j < numMat[i].length; j++) { numMat[i][j] = new Point(i, j, true, 0); } } initNumMat2(numMat, al); } public static void initNumMat2(Point[][] numMat, ArrayList<Point> al) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] p = new String[3]; String line=null; System.out.println('請(qǐng)按格式輸入點(diǎn)信息（i行號(hào), j列號(hào) v值）,輸入結(jié)束輸入over: i j v '); while((line = br.readLine())!=null){ if(line.equals('over')) break; p = line.trim().split(' +'); numMat[Integer.parseInt(p[0])][Integer.parseInt(p[1])].setValue(Integer.parseInt(p[2])); numMat[Integer.parseInt(p[0])][Integer.parseInt(p[1])].changeFlag(); al.add(numMat[Integer.parseInt(p[0])][Integer.parseInt(p[1])]); } } public static void printMat(Point[][] numMat) { System.out.println('--------┬---------┬---------┐'); for (int i = 0; i < numMat.length; i++) { for (int j = 0; j < numMat[i].length; j++) { if ((j + 1) % 3 == 0) System.out.print(numMat[i][j].getValue() + ' | '); else System.out.print(numMat[i][j].getValue() + ' '); } if ((i + 1) % 3 == 0) System.out.println('rn--------┼---------┼---------┤'); else System.out.println(); } } }

——-運(yùn)行程序

請(qǐng)按格式輸入點(diǎn)信息（i行號(hào),?j列號(hào)?v值）,輸入結(jié)束輸入over:?i?j?v0?0?81?2?31?3?62?1?72?4?92?6?23?1?53?5?74?4?44?5?54?6?75?3?15?7?36?2?16?7?66?8?87?2?87?3?57?7?18?1?98?6?4over——–┬———┬———┐8??1??2?|?7??5??3?|?6??4??9?|9??4??3?|?6??8??2?|?1??7??5?|6??7??5?|?4??9??1?|?2??8??3?|——–┼———┼———┤1??5??4?|?2??3??7?|?8??9??6?|3??6??9?|?8??4??5?|?7??2??1?|2??8??7?|?1??6??9?|?5??3??4?|——–┼———┼———┤5??2??1?|?9??7??4?|?3??6??8?|4??3??8?|?5??2??6?|?9??1??7?|7??9??6?|?3??1??8?|?4??5??2?|——–┼———┼———┤