基于Java解荷兰数学家设计世界最难九宫格.doc

今日，一则腾讯的新闻称中国老头三天破解世界最难九宫格，虽然最后老人是改了一个数字，但是引起本人一时兴趣，想通过计算机程序求解该问题，于是在宿舍呆了一下午，终于成功求解，程序源码如下。1. packagenumberGame;2. 3. 4. publicclassPoint5. privateintcol;/行号6. privateintrow;/列号7. privatebooleanflag;/真为未设置。8. privateintvalue;9. /构造点10. publicPoint(intcol,introw,booleanflag,intvalue)11. super();12. this.col=col;13. this.row=row;14. this.flag=flag;15. this.value=value;16. 17. 18. publicvoidchangeFlag()19. flag=!flag;20. 21. 22. 23. publicbooleangetFlag()24. returnflag;25. 26. 27. publicintgetValue()28. returnvalue;29. 30. 31. publicvoidsetValue(intvalue)32. this.value=value;33. 34. 35. publicbooleancanHere(PointpArr)36. booleancb=canCol(pArr);37. booleancr=canRow(pArr);38. booleancminiArr=canMiniArr(pArr);39. returncb&cr&cminiArr;40. 41. /判断在小3*3格子里是否有相同元素42. privatebooleancanMiniArr(PointpArr)43. intcoltemp=this.col%3;44. introwtemp=this.row%3;45. 46. for(inti=this.col-coltemp;icol+(3-coltemp);i+)47. for(intj=this.row-rowtemp;jrow+(3-rowtemp);j+)48. if(i=this.col&j=this.row)49. continue;50. else51. if(this.value=pArrij.getValue()52. returnfalse;53. 54. 55. 56. 57. returntrue;58. 59. 60. /判断列上是否有相同元素61. privatebooleancanRow(PointpArr)62. for(inti=0;i9;i+)63. if(i=this.col)64. continue;65. else66. if(this.value=pArrithis.row.value)/行变，列不变67. returnfalse;68. 69. 70. 71. returntrue;72. 73. 74. /判断行上是否有相同元素75. privatebooleancanCol(PointpArr)76. for(inti=0;i9;i+)77. if(i=this.row)78. continue;79. else80. if(this.value=pArrthis.coli.value)/列边，行不变81. returnfalse;82. 83. 84. 85. returntrue;86. 87. -主程序1. packagenumberGame;2. 3. importjava.io.BufferedReader;4. importjava.io.IOException;5. importjava.io.InputStreamReader;6. importjava.util.ArrayList;7. 8. 9. publicclassNumber9910. 11. publicstaticvoidmain(Stringargs)throwsIOException12. PointnumMat=newPoint99;13. ArrayListal=newArrayList();14. 15. initNumMat(numMat,al);16. 17. 18. setNum(numMat,al);19. printMat(numMat);20. 21. 22. privatestaticvoidsetNum(PointnumMat,ArrayListal)23. inti=0;24. intj=0;25. do26. if(numMatij.getFlag()27. for(intv=numMatij.getValue()+1;v=9;v+)/给回退到的位置的值加一。28. numMatij.setValue(v);29. if(numMatij.canHere(numMat)/满足条件，不冲突。30. numMatij.changeFlag();/改变标记为假。表示已设置过。31. break;32. else/满足不条件，冲突。value值自加一次33. 34. 35. while(v=9)/如果1-9都不能满足要求，则先将本位重置为0，并回退一格,给回退到的位置的值加一（当回退位置的值不为9时,并且保证回退到的位置不是九宫格原本的点）。36. numMatij.setValue(0);37. j-;38. if(j=-1)39. i-;j=8;40. 41. while(al.contains(numMatij)/如果回退到的位置为九宫格本来的点时，继续回退，直到不是本身的点时跳出while。42. j-;43. if(j=-1)44. i-;j=8;45. 46. 47. numMatij.changeFlag();/将标记48. v=numMatij.getValue();49. 50. 51. 52. j+;53. if(j=9)54. j=0;i+;/此处i+可能使i自加为9，故下面需要i!=9判断55. 56. if(i!=9)57. while(al.contains(numMatij)58. j+;59. if(j=9)60. j=0;i+;61. 62. 63. 64. while(i!=9);65. 66. 67. 68. publicstaticvoidinitNumMat(PointnumMat,ArrayListal)throwsIOException69. for(inti=0;inumMat.length;i+)70. for(intj=0;jnumMati.length;j+)71. numMatij=newPoint(i,j,true,0);72. 73. 74. initNumMat2(numMat,al);75. 76. 77. 78. publicstaticvoidinitNumMat2(PointnumMat,ArrayListal)throwsIOException79. BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in);80. Stringp=newString3;81. Stringline=null;82. System.out.println(请按格式输入点信息（i行号,j列号v值）,输入结束输入over:ijv);83. 84. while(line=br.readLine()!=null)85. if(line.equals(over)86. break;87. p=line.trim().split(+);88. numMatInteger.parseInt(p0)Integer.parseInt(p1).setValue(Integer.parseInt(p2);89. numMatInteger.parseInt(p0)Integer.parseInt(p1).changeFlag();90. al.add(numMatInteger.parseInt(p0)Integer.parseInt(p1);91. 92. 93. 94. publicstaticvoidprintMat(PointnumMat)95. System.out.println(-);96. 97. for(inti=0;inumMat.length;i+)98. for(intj=0;jnumMati.length;j+)99. if(j+1)%3=0)100. System.out.print(numMatij.getValue()+|);101. else102. System.out.print(numMatij.getValue()+);103. 104. if(i+1)%3=0)105. System.out.println(rn-);106. else107. System.out.println();108. 109. 110. 111. -运行程序请按格式输入点信息（i行号,j列号v值）,输入结束输入over:ijv008123136217249262315357444455467531