import java.io.FileNotFoundException;import java.io.PrintStream;import java.io.UnsupportedEncodingException;import java.util.Random; public class Puzzle { private long step = 0; private int n = 6;// 宮格基數 private int[][] puzzle; private int resetBlock = 0;// //空白塊位置 private int whiteBlockX; private int whiteBlockY;   //當前要準備移動的塊的坐標即復位塊 private int resetBlockX; private int resetBlockY;   private boolean isPrint=false;   public Puzzle() {  init(); }  public Puzzle(int n) {  this.n = n;  init(); }  private void init() {  puzzle = new int[n][n];  for (int y = 0; y < n; y++) {   for (int x = 0; x < n; x++) {    puzzle[y][x] = x + y * n;   }  }  whiteBlockX = n-1;  whiteBlockY = n-1;  int times = 100;// 打亂次數，必須是偶數  Random random = new Random();  while (times > 0) {   int x0 = random.nextInt(n);   int y0 = random.nextInt(n);   int x1 = random.nextInt(n);   int y1 = random.nextInt(n);   if (x0 != x1 && y0!=y1) {// 保證是偶排序    if((x0==n-1&&y0==n-1)||(x1==n-1&&y1==n-1)){//最后一個不調換     continue;    }    times--;    int t = puzzle[x0][y0];    puzzle[x0][y0] = puzzle[x1][y1];    puzzle[x1][y1] = t;   }  }//  int[][] p = {{22,9 ,1 ,5 ,0 ,25 },{//    33,23,20,26,18,21},{//    6 ,16,17,10,34,31},{//    19,28,32,7 ,3 ,2},{//    11,4 ,12,14,27,24},{//    15,29,30,8 ,13,35}};//  puzzle = p; }   public void sort(){  for (int y = 0; y < n; y++) {   for (int x = 0; x < n; x++) {    if (x == n - 1 && y == n - 1) {// 最后一個為空白,    } else {     reset(x, y);    }   }  } } //把塊復位移動目標位置 private void reset(int targetX, int targetY) {  // 找到復位塊當前的位置  initResetBlock(targetX, targetY);  /*   * 復位順序是從左到右，從上到下   * 移動方式 先上移動，再左移動   * 當前復位塊，它要復位的位置可分為 四種情況   * 1、不在最右邊一行也不是最下面兩行   * 2、最右邊一行 x=n-1，但不是下面兩行;   * 3、最下面兩行 y=n-2，但不是最右邊一行;   * 4、即使最右邊的一行也是最下面兩行   */  if(targetX < n-1 && targetY < n-2){   if(resetBlockX==targetX&&resetBlockY==targetY){//位置正確不用移動    return;//退出遞歸   }   resetBlockToTarget(targetX, targetY);  }else if(targetX==n-1 && targetY < n-2){//第二種情況   if(resetBlockX==targetX&&resetBlockY==targetY){//位置正確不用移動    return;//退出遞歸   }   reset2(targetX, targetY);  }else if(targetX < n-2 && targetY == n-2){//   isPrint=true;   reset3(targetX);   return;  }else{   initResetBlock(n-2, n-2);   resetBlockToTarget(n-2, n-2);   if(whiteBlockX<n-1){    whiteBlockRight();   }   if(whiteBlockY<n-1){    whiteBlockDown();   }   if(whiteBlockX==n-1&&whiteBlockY==n-1){    return;   }  }  reset(targetX, targetY);//遞歸 } private void initResetBlock(int targetX,int targetY){  resetBlock = targetX + targetY * n;  for (int y = 0; y < n; y++) {   for (int x = 0; x < n; x++) {    if (puzzle[y][x] == resetBlock) {// x,y就是復位塊的位置     resetBlockX = x;     resetBlockY = y;     break;    }   }  } } private void reset3(int targetX){//  if(targetX>=2){//  }  initResetBlock(targetX, n-1);  resetBlockToTarget(targetX, n-2);     initResetBlock(targetX, n-2);  resetBlockToTarget(targetX+1, n-2);  l:  while (!(whiteBlockX==targetX && whiteBlockY==n-1)) {   if(whiteBlockY<n-1){    whiteBlockDown();    continue l;   }   if(whiteBlockX>targetX){    whiteBlockLeft();    continue l;   }   break;  }  whiteBlockUp();  swapWhiteBlockAndCurrentBlock();     if(puzzle[n-2][targetX]!=resetBlock||puzzle[n-1][targetX]!=(resetBlock+n)){//沒有復位成功//   isPrint=true;   swapWhiteBlockAndCurrentBlock();   reset3_0();   reset3(targetX);  } } private void reset3_0(){  if(resetBlockX<n-1){   whiteBlockDown();   whiteBlockRight();   whiteBlockRight();   whiteBlockUp();   swapWhiteBlockAndCurrentBlock();   reset3_0();   return;  }  return; }     private void reset2_3(){  if(whiteBlockX==resetBlockX && whiteBlockY==resetBlockY+1){   return;//滿足條件，退出遞歸  }  //白塊可能在復位塊的：左方、左下、下方  if(whiteBlockY==resetBlockY){//左方   whiteBlockDown();  }else if(whiteBlockX < resetBlockX){//左下   whiteBlockRight();  }else {   whiteBlockUp();  }  reset2_3();//遞歸 }   private void reset2_2(int targetX, int targetY){  if(resetBlockX==targetX&&resetBlockY==targetY){//2、把復位塊移到目標位置正下方   return;//退出遞歸  }     //復位塊可能位置，目標位置左方、正下方、左下方  if(resetBlockX==targetX){//正下方 上移   resetBlockUp(targetX, targetY);  }else{//左方或左下方；先右移再上移   resetBlockRight(targetX, targetY);  }  reset2_2(targetX, targetY);//遞歸 }  private void reset2(int targetX, int targetY){  if(resetBlockX==targetX&&resetBlockY==targetY){//位置正確不用移動   return;//退出遞歸  }  /* 1、如果白塊正好占了目標位置：如果復位塊正好在下方，交換及完成復位，如果下方不是復位塊，把白塊移開目標位置   * 2、把復位塊移到目標位置正下方   * 3、把白塊移動復位塊下方   * 4、按照規定的步驟復位   */  //第一步  if(whiteBlockX==targetX&& whiteBlockY==targetY){   if(whiteBlockX==resetBlockX&&whiteBlockY==resetBlockY+1){//復位塊在下方    swapWhiteBlockAndCurrentBlock();    return;   }else{    whiteBlockDown();   }  }  //第二步 把復位塊移到目標位置正下方  reset2_2(targetX, targetY+1);  //第三步 把白塊移動復位塊下方  reset2_3();  //第四步 按照規定的步驟復位  swapWhiteBlockAndCurrentBlock();  whiteBlockLeft();  whiteBlockUp();  whiteBlockRight();  whiteBlockDown();  whiteBlockLeft();  whiteBlockUp();  whiteBlockRight();  whiteBlockDown();  swapWhiteBlockAndCurrentBlock();  whiteBlockLeft();  whiteBlockUp();  whiteBlockUp();  whiteBlockRight();  swapWhiteBlockAndCurrentBlock(); }   private void resetBlockToTarget(int targetX, int targetY){  if(resetBlockX==targetX&&resetBlockY==targetY){//位置正確不用移動   return;//退出遞歸  }    if(resetBlockY==targetY){//正左   resetBlockLeft(targetX, targetY);  }else{//左下，下，右下   if(resetBlockX>=targetX){//右下||下；上移    if(resetBlockX==n-1){//復位塊在最右邊，先左移；方便上移時統一的采用白塊逆時針方式     resetBlockLeft(targetX, targetY);    }else{     resetBlockUp(targetX, targetY);    }   }else{//左下；右移    resetBlockRight(targetX, targetY);   }  }  resetBlockToTarget(targetX, targetY);//遞歸 }   private void resetBlockRight(int targetX, int targetY){  if(resetBlockX==targetX&&resetBlockY==targetY){//位置正確不用移動   return;//退出遞歸  }  if(resetBlockX==n-1){//復位塊在最右邊了，無法右移，直接退出   return;  }//  System.out.println("resetBlockRight");  if(whiteBlockY<resetBlockY){//上方   if(whiteBlockY<resetBlockY-1){//上方多行    whiteBlockDown();   }else{//上方一行    if(whiteBlockX<resetBlockX+1){//左上和正上     whiteBlockRight();    }else{//右上     whiteBlockDown();    }   }  }else if(whiteBlockY==resetBlockY){//同一行   if(whiteBlockX<resetBlockX){//左方    if(whiteBlockY==n-1){//到底了，只能往上     whiteBlockUp();    }else{     whiteBlockDown();    }   }else{//右方    if(whiteBlockX==resetBlockX+1){     swapWhiteBlockAndCurrentBlock();     return;//退出遞歸    }else{     whiteBlockLeft();    }   }  }else{//下方   if(whiteBlockX <= resetBlockX){//左下、下    whiteBlockRight();   }else{//右下    whiteBlockUp();   }  }  resetBlockRight(targetX, targetY);//遞歸 }   private void resetBlockLeft(int targetX, int targetY){  if(resetBlockX==targetX&&resetBlockY==targetY){//位置正確不用移動   return;//退出遞歸  }  if(resetBlockX==0){//在左邊邊界 復位塊無法左移，直接退出遞歸   return;  }//  System.out.println("resetBlockLeft");  if(whiteBlockY<resetBlockY){//上方   if(whiteBlockY<resetBlockY-1){//上方多行    whiteBlockDown();   }else{//上方一行    if(whiteBlockX==resetBlockX){//上方     if(whiteBlockX==n-1){//最右邊，白塊無法右移，只能左移      whiteBlockLeft();     }else{      if(resetBlockY==n-1){//復位塊在最低端，白塊不能順時針移動       whiteBlockLeft();      }else{       whiteBlockRight();      }     }    }else if(whiteBlockX>resetBlockX){//右上方     if(resetBlockY==n-1){//復位塊在最低端，白塊不能順時針移動      whiteBlockLeft();     }else{      whiteBlockDown();     }    }else{//左上方     whiteBlockDown();    }   }  }else if(whiteBlockY==resetBlockY){//左方、右方   if(whiteBlockX<resetBlockX){//左方    if(whiteBlockX==resetBlockX-1){//左邊一格     swapWhiteBlockAndCurrentBlock();//退出遞歸     return;    }else{     whiteBlockRight();    }   }else{//右方    if(whiteBlockY==n-1){//到底了，不能下移。只能上移     whiteBlockUp();    }else{     whiteBlockDown();    }   }  }else{//左下、下方、右下   if(whiteBlockX<resetBlockX){//左下    if(whiteBlockX==resetBlockX-1){     whiteBlockUp();    }else{     whiteBlockRight();    }   }else{//下方、右下    whiteBlockLeft();   }  }  resetBlockLeft(targetX, targetY);//遞歸 }   private void resetBlockUp(int targetX, int targetY){  if(resetBlockX==targetX&&resetBlockY==targetY){//位置正確不用移動   return;//退出遞歸  }  if(resetBlockY==0){//復位塊到頂了，無法上移   return;  }//  System.out.println("resetBlockUp");  if (whiteBlockY < resetBlockY) {//上方   if(whiteBlockY < resetBlockY - 1){//上方多行    whiteBlockDown();   }else{//上方一行    if(whiteBlockX == resetBlockX){//白塊和復位塊在同一列（豎列） 白塊和復位塊直接交換位置     swapWhiteBlockAndCurrentBlock();//退出遞歸     return;    }else{     if(whiteBlockX<resetBlockX){//白塊在復位塊的左邊；白塊右移      whiteBlockRight();      }else{//白塊在復位塊的右邊；白塊左移      whiteBlockLeft();     }    }   }  } else if (whiteBlockY == resetBlockY) {//白塊和復位塊同一行；白塊上移   if(whiteBlockX<resetBlockX){//正左    if(whiteBlockX<resetBlockX-1){//正左多格     whiteBlockRight();    }else{//正左一格     if(whiteBlockY==n-1){//到底了      whiteBlockUp();     }else {      if(resetBlockX==n-1){//復位塊在最右邊，無法逆時針,只有順指針移動白塊       whiteBlockUp();      }else{       whiteBlockDown();      }     }    }   }else{//正右    whiteBlockUp();   }  }else{//白塊在復位塊下方，白塊需要饒過復位塊上移,白塊逆時針繞到白塊上面   //三種情況：左下，下，右下   if(whiteBlockX<=resetBlockX){//左下，下；白塊右移    if(resetBlockX==n-1){//復位塊在最右邊，無法逆時針,只有順指針移動白塊     if(whiteBlockX==resetBlockX){//正下方      whiteBlockLeft();     }else{//左下方      whiteBlockUp();     }    }else{     whiteBlockRight();    }   }else{//右下；白塊上移    whiteBlockUp();   }  }  resetBlockUp(targetX, targetY);//遞歸 }   //白塊和復位塊交換位置 private void swapWhiteBlockAndCurrentBlock(){  step++;  int tempX = whiteBlockX,tempY = whiteBlockY;  int temp = puzzle[whiteBlockY][whiteBlockX];  puzzle[whiteBlockY][whiteBlockX] = puzzle[resetBlockY][resetBlockX];  puzzle[resetBlockY][resetBlockX] = temp;  whiteBlockX = resetBlockX;  whiteBlockY = resetBlockY;  resetBlockX = tempX;  resetBlockY = tempY;  println("swap"); }   private void whiteBlockDown(){  step++;  int temp = puzzle[whiteBlockY][whiteBlockX];  puzzle[whiteBlockY][whiteBlockX] = puzzle[whiteBlockY+1][whiteBlockX];  puzzle[whiteBlockY+1][whiteBlockX] = temp;  whiteBlockY++;  println("↓"); } private void whiteBlockUp(){  step++;  int temp = puzzle[whiteBlockY][whiteBlockX];  puzzle[whiteBlockY][whiteBlockX] = puzzle[whiteBlockY-1][whiteBlockX];  puzzle[whiteBlockY-1][whiteBlockX] = temp;  whiteBlockY--;  println("↑"); }   private void whiteBlockLeft(){  step++;  int temp = puzzle[whiteBlockY][whiteBlockX];  puzzle[whiteBlockY][whiteBlockX] = puzzle[whiteBlockY][whiteBlockX-1];  puzzle[whiteBlockY][whiteBlockX-1] = temp;  whiteBlockX--;  println("←"); } private void whiteBlockRight(){  step++;  int temp = puzzle[whiteBlockY][whiteBlockX];  puzzle[whiteBlockY][whiteBlockX] = puzzle[whiteBlockY][whiteBlockX+1];  puzzle[whiteBlockY][whiteBlockX+1] = temp;  whiteBlockX++;  println("→"); }     @Override public String toString() {  StringBuilder sb = new StringBuilder();  sb.append("resetBlock=("+resetBlock+","+resetBlockX+","+resetBlockY+")/n");  if(puzzle!=null){   int len = String.valueOf(n*2-1).length();   for (int y = 0; y < n; y++) {    for (int x = 0; x < n; x++) {     if(x>0){      sb.append(",");     }     sb.append(_str(String.valueOf(puzzle[y][x]), len));    }    sb.append("/n");   }   sb.append("---------------------------------------");  }else{   sb.append("puzzle is null");  }  return sb.toString(); } private String _str(String str,int len){  str=str==null?"":str;  if(str.length()<len){   return _str(str+" ", len);  }  return str; }   private void println(String str){  if(isPrint){   System.out.println(str);   System.out.println(this);  } }  public static void main(String[] args) throws FileNotFoundException, UnsupportedEncodingException {//  System.setOut(new PrintStream("e:/puzzle.txt","UTF-8"));  Puzzle p = new Puzzle();  System.out.println(p);  try {   p.sort();  } catch (Exception e) {   e.printStackTrace();   System.out.println("Exception:");  }finally{   System.out.println(p);  } }}