关于重排九宫问题，该怎么用java实现？求解释？

Question

就是把像2 8 31 47 6 5这样的通过一步步的变换最终变为1 2 38 47 6 5要有中间的变换过程输出必须用java语言实现（最好能有A*，广度优先等好几种算法）

Answer 1

import java.util.Arrays;
public class NineGridTest{
public static void main(String[] args){
//三行数据依次排列9个元素构造实例，空位填0，调用go方法获取答案。
NineGrid example=new NineGrid(new int[]{1,6,5,3,0,2,7,8,4});
int[] answer=example.go();
if(answer==null){
System.out.println("没有找到步骤");
}
else{
for(int i=0;i<answer.length;i++){
System.out.print(answer[i]);
}
System.out.println();
}
}
}
class NineGrid{
private static final int MAX_STEP=50;
private static final int[] right=new int[]{1,2,3,8,0,4,7,6,5};
private int vacant,length;
private int[] grids,answer;
public NineGrid(int[] grids){
if(grids.length!=9){
throw new IllegalArgumentException(String.format("缺少数据：%1$d(%2$d)",grids.length,9));
}
int i,j;
for(i=8;i>=0;i--){
for(j=0;j<9;j++){
if(grids[j]==i){
break;
}
}
if(j==9){
throw new IllegalArgumentException("无效的数字序列。缺少："+i);
}
}
this.grids=grids;
answer=new int[50];
length=0;
}
public int[] go(){
for(vacant=0;vacant<9&&grids[vacant]!=0;vacant++);
return nextStep(0)?Arrays.copyOf(answer,length):null;
}
private boolean OK(){
return Arrays.equals(grids,right);
}
private boolean nextStep(int step){
if(step==MAX_STEP){
return false;
}
int[] siblings=getSiblings(vacant);
for(int i=0;i<siblings.length;i++){
if(step>0&&grids[siblings[i]]==answer[step-1]){
continue;
}
grids[vacant]=grids[siblings[i]];
answer[step]=grids[vacant];
grids[siblings[i]]=0;
vacant^=siblings[i];
siblings[i]^=vacant;
vacant^=siblings[i];
if(OK()){
length=step+1;
return true;
}
else{
boolean result=nextStep(step+1);
if(result){
return true;
}
else{
grids[vacant]=grids[siblings[i]];
vacant=siblings[i];
grids[vacant]=0;
}
}
}
return false;
}
private int[] getSiblings(int position){
switch(position){
case 0:return new int[]{1,3};
case 1:return new int[]{0,2,4};
case 2:return new int[]{1,5};
case 3:return new int[]{0,4,6};
case 4:return new int[]{1,3,5,7};
case 5:return new int[]{2,4,8};
case 6:return new int[]{3,7};
case 7:return new int[]{4,6,8};
case 8:return new int[]{5,7};
default:return null;
}
}
}
//递归算法。