今日，一则腾讯的新闻称中国老头三天破解世界最难九宫格，虽然最后老人是改了一个数字，但是引起本人一时兴趣，想通过计算机程序求解该问题，于是在宿舍呆了一下午，终于成功求解，程序源码如下。
packagenumberGame; publicclassPoint{ privateintcol;//行号 privateintrow;//列号 privatebooleanflag;//真为未设置。 privateintvalue; //构造点 publicPoint(intcol,introw,booleanflag,intvalue){ super(); this.col=col; this.row=row; this.flag=flag; this.value=value; } publicvoidchangeFlag(){ flag=!flag; } publicbooleangetFlag(){ returnflag; } publicintgetValue(){ returnvalue; } publicvoidsetValue(intvalue){ this.value=value; } publicbooleancanHere(Point[][]pArr){ booleancb=canCol(pArr); booleancr=canRow(pArr); booleancminiArr=canMiniArr(pArr); returncb&&cr&&cminiArr; } //判断在小3*3格子里是否有相同元素 privatebooleancanMiniArr(Point[][]pArr){ intcoltemp=this.col%3; introwtemp=this.row%3; for(inti=this.col-coltemp;i<col+(3-coltemp);i++){ for(intj=this.row-rowtemp;j<row+(3-rowtemp);j++){ if(i==this.col&&j==this.row){ continue; }else{ if(this.value==pArr[i][j].getValue()){ returnfalse; } } } } returntrue; } //判断列上是否有相同元素 privatebooleancanRow(Point[][]pArr){ for(inti=0;i<9;i++){ if(i==this.col){ continue; }else{ if(this.value==pArr[i][this.row].value){//行变，列不变 returnfalse; } } } returntrue; } //判断行上是否有相同元素 privatebooleancanCol(Point[][]pArr){ for(inti=0;i<9;i++){ if(i==this.row){ continue; }else{ if(this.value==pArr[this.col][i].value){//列边，行不变 returnfalse; } } } returntrue; } }
—–主程序
packagenumberGame; importjava.io.BufferedReader; importjava.io.IOException; importjava.io.InputStreamReader; importjava.util.ArrayList; publicclassNumber99{ publicstaticvoidmain(String[]args)throwsIOException{ Point[][]numMat=newPoint[9][9]; ArrayList<Point>al=newArrayList<Point>(); initNumMat(numMat,al); setNum(numMat,al); printMat(numMat); } privatestaticvoidsetNum(Point[][]numMat,ArrayList<Point>al){ inti=0; intj=0; do{ if(numMat[i][j].getFlag()){ for(intv=numMat[i][j].getValue()+1;v<=9;v++){//给回退到的位置的值加一。 numMat[i][j].setValue(v); if(numMat[i][j].canHere(numMat)){//满足条件，不冲突。 numMat[i][j].changeFlag();//改变标记为假。表示已设置过。 break; }else{//满足不条件，冲突。value值自加一次 } while(v==9){//如果1-9都不能满足要求，则先将本位重置为0，并回退一格,给回退到的位置的值加一（当回退位置的值不为9时,并且保证回退到的位置不是九宫格原本的点）。 numMat[i][j].setValue(0); j–; if(j==-1){ i–;j=8; } while(al.contains(numMat[i][j])){//如果回退到的位置为九宫格本来的点时，继续回退，直到不是本身的点时跳出while。 j–; if(j==-1){ i–;j=8; } } numMat[i][j].changeFlag();//将标记 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); } publicstaticvoidinitNumMat(Point[][]numMat,ArrayList<Point>al)throwsIOException{ for(inti=0;i<numMat.length;i++){ for(intj=0;j<numMat[i].length;j++){ numMat[i][j]=newPoint(i,j,true,0); } } initNumMat2(numMat,al); } publicstaticvoidinitNumMat2(Point[][]numMat,ArrayList<Point>al)throwsIOException{ BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in)); String[]p=newString[3]; Stringline=null; System.out.println("请按格式输入点信息（i行号,j列号v值）,输入结束输入over:ijv"); 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])]); } } publicstaticvoidprintMat(Point[][]numMat){ System.out.println("——–┬———┬———┐"); for(inti=0;i<numMat.length;i++){ for(intj=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("\r\n——–┼———┼———┤"); else System.out.println(); } } }
——-运行程序
请按格式输入点信息（i行号,j列号v值）,输入结束输入over:ijv 008 123 136 217 249 262 315 357 444 455 467 531 573 621 676 688 728 735 771 819 864 over ——–┬———┬———┐ 812|753|649| 943|682|175| 675|491|283| ——–┼———┼———┤ 154|237|896| 369|845|721| 287|169|534| ——–┼———┼———┤ 521|974|368| 438|526|917| 796|318|452| ——–┼———┼———┤
有事者，事竟成;破釜沉舟，百二秦关终归楚;苦心人，
