puzzle.java

八数码 * 大体思路：主要思想为插入排序。 * 特殊词语解释： * 墙：在最外层的中间位置

package exc7;

/**
 * <p>Title: </p>
 *
 * <p>Description: </p>
 *
 * <p>Copyright: Copyright (c) 2006</p>
 *
 * <p>Company: </p>
 *
 * @author not attributable
 * @version 1.0
 */
/******************************************************
 * 大体思路：主要思想为插入排序。
 * 特殊词语解释：
 * 墙：在最外层的中间位置，总共有四个，如[1][0]。
 *    注意：这四个位置有一个共同性质，即：以任何方式记录数字为，他们与其他五个位置的奇偶性互异
 * 角：数组的四个角
 * 空格：数字0
 */
public class Puzzle {
 void Clockwise(int array[][]){//逆时针,保证交换的数字不是排序数字
     if(Find(array,0)==4){//如果空格在中间
         int row=Find(array,0)/3;//获得空格的行
         int col=Find(array,0)%3;//获得空格的列
         //此时需要和空格周围的某一数字交换，选取最大的数字进行交换
         int temp=array[row-1][col];//记录空格上方的数字，便于判断和哪个数字交换
         if(temp<array[row+1][col]) temp=array[row+1][col];//下方数字较大
         if(temp<array[row][col-1]) temp=array[row][col-1];//左方数字较大
         if(temp<array[row][col+1]) temp=array[row][col+1];//右方数字较大
         row=Find(array,temp)/3;//取得要交换数字的行
         col=Find(array,temp)%3;//取得要交换数字的列
         //进行交换
         array[1][1]=array[row][col];
         array[row][col]=0;
     }
     else{//空格不在中间
         int row = Find(array, 0) / 3;//获得空格的行
         int col = Find(array, 0) % 3;//获得空格的列
         //空格将进行移动，方向为顺时针
         if (row == 0 && col < 2) {//向左移动
             //交换
             array[row][col] = array[row][col + 1];
             array[row][col + 1] = 0;
         }
         if (row > 0 && col == 0) {//向上移动
             //交换
             array[row][col] = array[row - 1][col];
             array[row - 1][col] = 0;
         }
         if (row == 2 && col > 0) {//向右移动
             //交换
             array[row][col] = array[row][col - 1];
             array[row][col - 1] = 0;
         }
         if (row < 2 && col == 2) {//向下移动
             //交换
             array[row][col] = array[row + 1][col];
             array[row + 1][col] = 0;
         }
     }//移动结束
     //输出移动后的数组
     System.out.println("===================");
    for(int i=0;i<array.length;i++){
        for(int j=0;j<array.length;j++)
            System.out.print(array[i][j]+" ");
        System.out.println();
    }
 }
 int Find(int array[][],int count){//寻找数字位置。
     int position=0;//记录count的位置
     //按行寻找count
     for(int row=0;row<array.length;row++)
         for(int col=0;col<array.length;col++)
             if(array[row][col]==count)
                 position=row*3+col;//保存count的位置
     return position;//返回count的位置
 }
 int[] NextPosition(int array[][],int count1){//排序得下一个位置，以及数据
     int content[]=new int[2];//记录count的下一个位置以及数字
     //逆时针的下一个
     if(Find(array,count1)/3==0&&Find(array,count1)%3>0) {//左边的数字
         //记录
         content[0]=Find(array,count1)-1;
         content[1]=array[content[0]/3][content[0]%3];
     }
     if(Find(array,count1)/3<2&&Find(array,count1)%3==0) {//下边的数字
         //记录
         content[0]=Find(array,count1)+3;
         content[1]=array[content[0]/3][content[0]%3];//error
     }
     if(Find(array,count1)/3==2&&Find(array,count1)%3<2) {//右边的数字
         //记录
         content[0]=Find(array,count1)+1;
         content[1]=array[content[0]/3][content[0]%3];
     }
     if(Find(array,count1)/3>0&&Find(array,count1)%3==2) {//上边的数字
         //记录
         content[0]=Find(array,count1)-3;
         content[1]=array[content[0]/3][content[0]%3];
     }
     return content;//返回
 }
 void ToCentre(int array[][],int count){//将适当的数移动到中间位置
     if(Find(array,count)==4);//count已经在中间位置
     else{//count不在中间位置
         while (((Find(array, count) % 2 != 1 || Find(array, 0) % 2 != 1) &&
                (NextPosition(array, 0)[1] < (count - 1))))//count和空格都不在墙上，
                                                                //并且空格的下一个位已经完成的数字
             Clockwise(array);//移动
         int row = Find(array, 0) / 3;//获得空格的行
         int col = Find(array, 0) % 3;//获得空格的列
         //空格与中间数字交换
         array[row][col] = array[1][1];
         array[1][1] = 0;
          //输出
         System.out.println("===================");
         for(int i=0;i<array.length;i++){
             for(int j=0;j<array.length;j++)
                System.out.print(array[i][j]+" ");
             System.out.println();
        }
         row = Find(array, count) / 3;//获得count的行
         col = Find(array, count) % 3;//获得count的列
         //count与空格交换
         array[1][1] = count;
         array[row][col] = 0;

         //完成将count移动到中间位置
         //输出
         System.out.println("===================");
     for(int i=0;i<array.length;i++){
       for(int j=0;j<array.length;j++)
           System.out.print(array[i][j]+" ");
       System.out.println();
   }
     }
 }
 void ToRight(int array[][],int count){//将数字移动到排序队列中
     if(count==1){//处理1的情况
         if(Find(array,1)==4){//1在中间位置
            if(Find(array,0)%2==0) Clockwise(array);//空格不在墙上，移动
            //此时空格一定在墙上，与1交换
            array[Find(array,0)/3][Find(array,0)%3]=1;
            array[1][1]=0;
            //输出
    System.out.println("===================");
    for(int i=0;i<array.length;i++){
        for(int j=0;j<array.length;j++)
              System.out.print(array[i][j]+" ");
        System.out.println();
    }
         }
         Clockwise(array);//因空格在中间位置，所以移动一下
     }else if(count!=8){//处理2~~7的情况
         while (Find(array, 0)%2 != 1 || NextPosition(array, count - 1)[1] != 0)//空格不在墙上
                                                         //或者排序序列中最大的一个数字下一个位置不是空格
             Clockwise(array);//移动
         //空格和count交换
         array[Find(array,0)/3][Find(array,0)%3] = count;
         array[1][1] = 0;
         Clockwise(array);//因空格在中间位置，所以移动一下
     }else {//处理8的情况
         while(Find(array,0)%2!=1||NextPosition(array,0)[1]!=1) Clockwise(array);//空格不在墙上，
                                                                //或者空格下一个位置不是1
         //此时空格一定再合适的位置，8与空格交换
         array[Find(array,0)/3][Find(array,0)%3]=8;
         array[1][1]=0;
     }
     //输出
     System.out.println("===================");
     for(int i=0;i<array.length;i++){
       for(int j=0;j<array.length;j++)
           System.out.print(array[i][j]+" ");
       System.out.println();
   }
 }
 int NextNumber(int array[][],int count){//检验处理完count后，count得下一个数字是否为(count+1)
     boolean over=false;//循环控制条件
     mobile:while(!over){//循环
         if(NextPosition(array,0)[1]<count){//空格在排序序列中
             Clockwise(array);//移动
             continue mobile;//继续检验空格的位置
         }
         if(NextPosition(array,count)[1]==(count+1)//count的下一个为(count+1)
            &&NextPosition(array,count-1)[1]==count)//并且(count-1)的下一个为count
             count++;//处理下一个数字
         else over=true;//count的下一个不是(count+1)
     }
    return count;//返回处理完的数字
 }
boolean  Over(int array[][]){//判断是否可以结束
    int count=1;//从1开始检测是否结束
    while(NextPosition(array,count)[1]==++count);//count的下一个数字是否为（count+1）
    return count==9;//结束时，count=9;否则,<9
 }
 void Method(int[][] array){//总方法
     int count=1;//从1开始处理
         while (!Over(array)) {//开始处理
             count = NextNumber(array, count);
             ToCentre(array, count);
             ToRight(array, count);
             count++;
         }
        }
 }