java解世界最难九宫格问题-mile米乐体育

芬兰数学家因卡拉花费3个月设计出了世界上迄今难度最大的数独游戏，而且它只有一个答案。因卡拉说只有思考能力最快、头脑最聪明的人才能破解这个游戏。

今日，一则腾讯的新闻称中国老头三天破解世界最难九宫格，虽然最后老人是改了一个数字，但是引起本人一时兴趣，想通过计算机程序求解该问题，于是在宿舍呆了一下午，终于成功求解，程序源码如下。

package numbergame;   public class point {      private int col;// 行号      private int row;// 列号      private boolean flag;// 真为未设置。      private int value;      // 构造点      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 al = new arraylist();           initnummat(nummat,al);           setnum(nummat,al);          printmat(nummat);      }       private static void setnum(point[][] nummat,arraylist 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();//改变标记为假。表示已设置过。                          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);       }       public static void initnummat(point[][] nummat,arraylist 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 al) throws ioexception {          bufferedreader br = new bufferedreader(new inputstreamreader(system.in));          string[] p = new string[3];          string line=null;          system.out.println("请按格式输入点信息（i行号, j列号 v值）,输入结束输入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("\r\n--------┼---------┼---------┤");              else                  system.out.println();          }      }   }

——-运行程序

请按格式输入点信息（i行号, j列号 v值）,输入结束输入over: i j v

0 0 8

1 2 3

1 3 6

2 1 7

2 4 9

2 6 2

3 1 5

3 5 7

4 4 4

4 5 5

4 6 7

5 3 1

5 7 3

6 2 1

6 7 6

6 8 8

7 2 8

7 3 5

7 7 1

8 1 9

8 6 4

over

——–┬———┬———┐

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 |

——–┼———┼———┤