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