Java制作智能拼图游戏原理及代码

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);  } }}