慕侠2389804
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;}}}//递归算法。