public class BaShuMa {
?
?static int[][] chu = {{2,8,3},{1,6,4},{7,0,5}};
?static int[][] biao = {{1,2,3},{8,0,4},{7,6,5}};
?static int[][] now = chu;
?static int i0 =2;
?static int j0 =1;
??? static int bushu = 0;
???? boolean left = false;
??boolean right = false;
??boolean up = false;
??boolean down = false;
?
?
?
?static String lujing = "";
??????
?/*返回當前數組的在位數*/
?public static int buzaiwei(int a[][]) {
??int sum = 0;
??for(int i=0;i<=2;i++) {
???for(int j=0;j<=2;j++) {
????if(a[i][j] == biao[i][j]&&a[i][j]!=0) {
?????sum++;
????}
????
????}
???}
???return sum;
??}
?/*判斷0所在的位置*/?
??public void i0j0weizhi(int[][] a) {
???int[] b = new int[2];
???for(int i=0;i<=2;i++) {
????for(int j=0;j<=2;j++) {
?????if(a[i][j]==0) {
??????i0 = i;
??????j0 = j;
??????b[0] = i0;
??????b[1] = j0;
??????
??????????????? }
????}
???}
???
??}
??
?/*以當前數組的i0.j0為參數,求出當前的可用規則集,并用4個boolean值來防止逆操作*/
?public? String keyonggueizeji(int c,int d) {
??
??String keyonggueize = "";
??if(d>=1&&right==false) {
???keyonggueize = keyonggueize + "z";
???
??}
??if(c>=1&&down==false) {
???keyonggueize = keyonggueize + "s";
???
??}
??if(d<=1&&left==false) {
???keyonggueize = keyonggueize + "y";
???
??}
??if(c<=1&&up==false) {
???keyonggueize = keyonggueize + "x";
???
??}
??return keyonggueize;
}?? /*走步函數*/
??? public void zoubu(int c,int d) {
????
?? int k1 = 0;
?? int k2 = 0;
?? int k3 = 0;
?? int k4 = 0;
?? int[][] b1={{2,8,3},{1,6,4},{7,0,5}};
?? int[][] b2={{2,8,3},{1,6,4},{7,0,5}};
?? int[][] b3={{2,8,3},{1,6,4},{7,0,5}};?
? int[][] b4={{2,8,3},{1,6,4},{7,0,5}};
? for(int i=0;i<=2;i++) {
? ?for(int j=0;j<=2;j++) {
? ??b1[i][j]=now[i][j];
? ?}
? }
? for(int i=0;i<=2;i++) {
? ?for(int j=0;j<=2;j++) {
? ??b2[i][j]=now[i][j];
? ?}
? }
? for(int i=0;i<=2;i++) {
? ?for(int j=0;j<=2;j++) {
? ??b3[i][j]=now[i][j];
? ?}
? }
? for(int i=0;i<=2;i++) {
? ?for(int j=0;j<=2;j++) {
? ??b4[i][j]=now[i][j];
? ?}
? }
?
? /*int[][] b1 = {{2,8,3},{1,6,4},{7,0,5}};
?? int[][] b2 = {{2,8,3},{1,6,4},{7,0,5}};
?? int[][] b3 = {{2,8,3},{1,6,4},{7,0,5}};?
? int[][] b4 = {{2,8,3},{1,6,4},{7,0,5}};*/
? i0j0weizhi(now);
? /*System.out.println(i0);
? System.out.println(j0);
? for(int a=0;a<=2;a++) {
??????????? ?for(int b=0;b<=2;b++) {
??????????? ??System.out.println(now[a][b]);
??????????? ?}
??????????? }*/
?
?
??/*判斷是否在字符串里有z*/
?
?if(keyonggueizeji(i0,j0).indexOf("z")!=-1) {
??
????
???
??
??b1[i0][j0] = b1[i0][j0-1];
??b1[i0][j0-1] = 0;
???? k1 = buzaiwei(b1);?
?
}
?if(keyonggueizeji(i0,j0).indexOf("s")!=-1) {
??b2[i0][j0] = b2[i0-1][j0];
??b2[i0-1][j0] = 0;
??k2 =buzaiwei(b2);
}
?
?if(keyonggueizeji(i0,j0).indexOf("y")!=-1) {
??b3[i0][j0] = b3[i0][j0+1];
??b3[i0][j0+1] = 0;
??k3 = buzaiwei(b3);
}
?
?if(keyonggueizeji(i0,j0).indexOf("x")!=-1) {
??b4[i0][j0] = b4[i0+1][j0];
??b4[i0+1][j0] = 0;
???? k4 =buzaiwei(b4);
}
??? if(k1>k2&&k1>k3&&k1>k4) {
??bushu++;
??lujing = lujing + "左";
??j0 = j0 -1;
??now = b1;
??left = true;
??up = false;
??down = false;
??right = false;
??/*for(int a=0;a<=2;a++) {
??????????? ?for(int b=0;b<=2;b++) {
??????????? ??System.out.println(now[a][b]);
??????????? ?}*/
??
?}
?if(k2>k1&&k2>k3&&k2>k4) {
??bushu++;
??lujing = lujing + "上";
??i0 = i0 - 1;
??now = b2;
??left = false;
??up = true;
??down = false;
??right = false;
?
?}
?if(k3>k1&&k3>k2&&k3>k4) {
??bushu++;
??lujing = lujing + "右";
??j0 = j0 +1;
??now = b3;
??left = false;
??up = false;
??down = false;
??right = true;
?
?}
?if(k4>k1&&k4>k2&&k4>k3) {
??bushu++;
??lujing = lujing + "下";
??i0 = i0 + 1;
??now = b4;
??left = false;
??up = false;
??down = true;
??right = false;
??
?}
?if(k1==k2&&k1>k3&&k1>k4) {
??bushu ++;
??lujing = lujing + "上";
???? i0 = i0 - 1;
??now = b2;
??left = false;
??up = true;
??down = false;
??right = false;
?
??
???
?}
}
?
?
??? public static void main(String[] args) {
??????? BaShuMa bashuma = new BaShuMa();
??????? System.out.println("給定的初始狀態數組為:");
??? ?for(int i=0;i<=2;i++) {
??? ??
??? ???System.out.print(chu[0][i]);
??? ??
??? ?}
??? ?System.out.println();
??? ?for(int i=0;i<=2;i++) {
??? ????? System.out.print(chu[1][i]);
??? ??? }
??? ??? System.out.println();
??? ?for(int i=0;i<=2;i++) {
??? ??System.out.print(chu[2][i]);
??? ??}
??? ??System.out.println();
??????? System.out.println("***********************");
??? ???? ?System.out.println("給定的目標狀態數組為:");
??? ?for(int i=0;i<=2;i++) {
??? ??
??? ???System.out.print(biao[0][i]);
??? ??
??? ?}
??? ?System.out.println();
??? ?for(int i=0;i<=2;i++) {
??? ????? System.out.print(biao[1][i]);
??? ??? }
??? ??? System.out.println();
??? ?for(int i=0;i<=2;i++) {
??? ??System.out.print(biao[2][i]);
??? ??}
??????? System.out.println();
??????? System.out.println("***********************");
??????? System.out.println("行走步驟為:");
??????? while(true)
??????? if(bashuma.buzaiwei(now)!=8) {
??????? ?bashuma.zoubu(i0,j0);
??????????? for(int i=0;i<=2;i++) {
??? ??
??? ???System.out.print(now[0][i]);
??? ??
??? ?}
??? ?System.out.println();
??? ?for(int i=0;i<=2;i++) {
??? ????? System.out.print(now[1][i]);
??? ??? }
??? ??? System.out.println();
??? ?for(int i=0;i<=2;i++) {
??? ??System.out.print(now[2][i]);
??? ??}
??? ?
??????? System.out.println();
??????? System.out.println("***********************");
??? }
??????? else {
??????? ?break;
??????? }
??? System.out.println("走步的路線為:"+lujing);
??? System.out.println("需要的步數為:"+bushu);?
??????? //bashuma.zoubu(i0,j0);
??????? //System.out.println(bashuma.alldepth(chu));
???????
??? }
}