import java.util.Hashtable;
import java.util.LinkedList;
public class Puzzle {
private String source;
private String destination;
public Puzzle(String s,String d){source=s; destination=d;}
public Puzzle() {}
static final int N=3;
boolean inside(int i,int j) {return i>=0 && i<N && j>=0 && j<N;}
final int[][] move={{0,1},{0,-1},{1,0},{-1,0}};
final char[] op={'R','L','D','U'};
int I(int k) {return k/N;}
int J(int k) {return k%N;}
int K(int i,int j) {return i*N+j;}
private boolean solvAbility(){
int first=invariant(source);
int last=invariant(destination);
int plf=source.indexOf("9");
int pll=destination.indexOf("9");
return (first+I(plf)+J(plf))%2==(last+I(pll)+J(pll))%2;
}
private int invariant(String st){
int k=0;
for (int i = 0; i < st.length(); i++) {
for (int j = i+1; j < st.length(); j++) {
if(st.charAt(i)>st.charAt(j)) k++;
}
}
return k;
}
public String solveBfs(){
if(!solvAbility()) return null;
LinkedList<String> quee=new LinkedList<String>();
Hashtable<String, String> ht=new Hashtable<String, String>();
ht.put(source, "");
quee.add(source);
while(true){
String q=quee.removeFirst();
String st=ht.get(q);
int place=q.indexOf("9");
int i=I(place);
int j=J(place);
for (int d = 0; d < 4; d++) {
int ii=i+move[d][0];
int jj=j+move[d][1];
if(inside(ii, jj)){
int k=K(ii,jj);
StringBuffer cur=new StringBuffer(q);
cur.setCharAt(place, cur.charAt(k));
cur.setCharAt(k, '9');
String p=cur.toString();
if(p.equals(destination)){
return st+op[d];
}
if(!ht.containsKey(p)){
quee.add(p);
ht.put(p, st+op[d]);
}
}
}
}
}
public static void main(String[] args) {
System.out.println(new Puzzle("123456789","479658123").solveBfs());
//System.out.println();
}
}
ولی حل معمای 24 هست که هنوز دچار مشکله. 
