C++ :

/*
	Name: 八数码 
	Date: 14/10/14 20:21
	Description: IDA*
*/
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>

using namespace std;

int now[10];
char c;
int to[10]={0,1,2,3,8,0,4,7,6,5};
int pos0=0,deep=0,h;
int f(){
	int fnow[10];
	int fto[10];
	int tot=0;
	for(int i=1;i<=9;++i){
		fnow[now[i]]=i-1;
		fto[to[i]]=i-1;
    }
	for(int i=1;i<9;++i){
		tot+=abs(fnow[i]/3-fto[i]/3)+abs(fnow[i]%3-fto[i]%3);
	}
	return tot;
}

void dfs(int ans,int pos){
	
	h=f();
	if(h+ans>deep) return;
	if(ans==deep) {
		cout<<ans<<endl;
		exit(0);
	}
	if(pos!=1&&pos!=4&&pos!=7){
		swap(now[pos],now[pos-1]);
		dfs(ans+1,pos-1);
		swap(now[pos],now[pos-1]);	
	}
	if(pos!=3&&pos!=6&&pos!=9){
		swap(now[pos],now[pos+1]);
		dfs(ans+1,pos+1);
		swap(now[pos],now[pos+1]);
	}
	if(pos>3){
		swap(now[pos],now[pos-3]);
		dfs(ans+1,pos-3);
		swap(now[pos],now[pos-3]);
	}
	if(pos<7){
		swap(now[pos],now[pos+3]);
		dfs(ans+1,pos+3);
		swap(now[pos],now[pos+3]);
	}
} 
int main(){
	/*freopen("1.in","r",stdin);
	for(int i=1;i<=9;++i){
		cin>>now[i];
		if(now[i]==0) pos0=i;
	}*/
	for(int i=1;i<=9;++i){
		cin>>c;
		now[i]=(int)c-48;
		if(now[i]==0) pos0=i;
	}
	while(1){
		dfs(0,pos0);
		++deep;
	}
	
}

Pascal :

program life;
 const goal='123804765';
       vx:array[1..4] of integer=(1,-1,3,-3);
       maxn=1200007;
 type rec=record
      s:string[9];
      step:longint;
      end;
      re=record
      f:boolean;
      s:string[9];
      end;
 var
 opt:array[0..maxn] of rec;
 flag:array[0..maxn] of re;
 i,j,n,m,x,w,k:longint;
 v:boolean;
 st,y:string[9];
 function lhash(s:string):int64;
 var
   hash:int64;
   begin
   val (s,hash);
   lhash:=hash mod maxn;
   end;
 procedure judge;
   begin
   if opt[m].s=goal then
     begin
     writeln (opt[m].step);
     halt;
     end;
   end;
 begin
 readln(st);
 opt[1].s:=st;
 opt[1].step:=0;
 x:=lhash(st);
 flag[x].f:=true;
 flag[x].s:=st;
 i:=1; j:=1;
 while i<=j do
   begin
   w:=pos ('0',opt[i].s);
   for k:=1 to 4 do
     if ((w mod 3=1) and (k<>2) or ((w mod 3=0)) and (k<>1))or
         (w mod 3=2) then
     if (w+vx[k]>0) and (w+vx[k]<=9) then
       begin
       y:=opt[i].s;
       y[w]:=y[w+vx[k]];
       y[w+vx[k]]:='0';
       x:=lhash(y);
       v:=false;
       while (x<maxn) and (flag[x].f) do
         begin
         if flag[x].s=y then
           begin
           v:=true;
           break;
           end;
         inc (x);
         end;
       if not v then
         begin
         inc(j);
         m:=j mod maxn;
         opt[m].s:=y;
         opt[m].step:=opt[i].step+1;
         flag[x].f:=true;
         flag[x].s:=y;
         judge;
         end;
       end;
   inc(i);
   end;
 end.

Java :

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;

public class Main {
    int[] dx = {-3,3,-1,1};

    public Main(){
        Scanner sc=new Scanner(System.in);
        String start = sc.nextLine(),end = "123804765";
        // 起始和结束状态
        HashSet<String> judge = new HashSet<>();
        judge.add(start);
        ArrayList<State> AL=new ArrayList<State>();
        AL.add(new State(start.toCharArray(),0));
        while(!AL.isEmpty()){    //System.out.println(index);
            State current=AL.remove(0);
            if(String.valueOf(current.type).equals(end)){
                System.out.println(current.step);
                return;
            }
            int blank;// 空格的位置
            for(blank = 0;blank<9;blank++)if (current.type[blank] == '0') break;
            for (int dt:dx) {
                if ((blank<3 && dt==-3) || (blank>5 && dt==3) || (blank%3==0 && dt==-1) || (blank%3==2 && dt==1)) continue;//不合法的情形，直接跳过
                else {
                    char[] type_new = new char[9];
                    for (int i = 0; i < 9 ; i++)  type_new[i] = current.type[i];
                    type_new[blank] = type_new[blank+dt];
                    type_new[blank+dt] = '0';
                    String newS = String.valueOf(type_new);
                    if(!judge.contains(newS)) {
                        State newState = new State(type_new,current.step+1);
                        AL.add(newState);
                        judge.add(newS);
                    }
                }
            }


        }
    }

    public static void main(String[] args) {
        Main tk=new Main();
    }

    class State{    //状态
        char[] type;  //格局
        int step;   //步数

        public State(char[] type, int step) {
            this.type = type;
            this.step = step;
        }
    }
}