八数码问题，对于一般的数据，BFS+逆序对HASH就可以解决了，或者双广搜索。进一步的话就是A*优化，A*的启发函数有以下两种：1,不在相应位置的格子数目; 2,不在相应位置的曼哈顿距离之和;显然第二种的效率比较高。一中兼顾效率，写起来有方便的算法就是IDA*，因为不要判重，而且是DFS，代码量小。还有猥琐点的方式就是从目标状态向所有状态扩展打表。。。
对于八数码问题，还有一个重要剪枝，那就是逆数对的剪枝，如果开始状态的逆数对数目是奇数则必无解，否则一定有解。因为对于目标状态的逆序对是0，即偶数，而操作只能与0交换，而0是不会影响结果的，只有于0交换的数会影响结果，但是那个数移动也会没有影响，因此初始状态逆序对数为奇数不可能会转到偶数的状态，因此无解。
其中对于POJ-1077和HDU-1043这两道题，因为只要求出可行解，没有必要求出步数最少的解，因此我们完全可以自己构造解，相信玩过拼图游戏并且思考了的就是小case了，简而言之就是一个一个的按照1,2,,,8,0的顺序把格子放回原位并且固定，再去放其它的，直到目标状态为止。
下面是我的HDU1043 A*代码：
1 //STATUS:C++_AC_328MS_4744KB 2 #include<stdio.h> 3 #include<stdlib.h> 4 #include<string.h> 5 #include<math.h> 6 #include<iostream> 7 #include<string> 8 #include<algorithm> 9 #include<vector> 10 #include<queue> 11 #include<stack> 12 #include<map> 13 #include<set> 14 using namespace std; 15 //define 16 #define pii pair<int,int> 17 #define mem(a,b) memset(a,b,sizeof(a)) 18 #define lson l,mid,rt<<1 19 #define rson mid+1,r,rt<<1|1 20 #define PI acos(-1.0) 21 //typedef 22 typedef long long LL; 23 typedef unsigned long long ULL; 24 //const 25 const int N=210; 26 const int INF=0x3f3f3f3f; 27 const int MOD=1000007,STA=400010; 28 const LL LNF=1LL<<60; 29 const double EPS=1e-8; 30 const double OO=1e15; 31 const int dx[4]={-1,0,1,0}; 32 const int dy[4]={0,1,0,-1}; 33 //Daily Use ... 34 template<class T> inline T Min(T a,T b){return a<b?a:b;} 35 template<class T> inline T Max(T a,T b){return a>b?a:b;} 36 template<class T> inline T Min(T a,T b,T c){return min(min(a, b),c);} 37 template<class T> inline T Max(T a,T b,T c){return max(max(a, b),c);} 38 //End 39 40 char out[]="urdl"; 41 int fac[10]; 42 int T,end; 43 44 struct Path{ 45 int op,fa; 46 }path[STA]; 47 48 struct Node{ 49 int ma[9]; 50 int sta,g,h,x,y; 51 bool operator < (const Node& b)const{ 52 return h!=b.h?h>b.h:g>b.g; 53 } 54 }; 55 56 struct HASH{ 57 int sta[STA]; 58 void init(){mem(sta,0);} 59 int ctadd(int s[]){ 60 int i,j,ret=0,k; 61 for(i=0;i<9;i++){ 62 for(j=k=0;j<i;j++) 63 if(s[j]>s[i])k++; 64 ret+=k*fac[i]; 65 } 66 if(sta[ret])return -1; 67 sta[ret]=1; 68 return ret; 69 } 70 }hs; 71 72 int geth(int s[]) 73 { 74 int i,j,h=0,x,y; 75 for(i=0;i<3;i++){ 76 for(j=0;j<3;j++){ 77 x=s[i*3+j]/3; 78 y=s[i*3+j]%3; 79 h+=abs(x-i)+abs(y-j); 80 } 81 } 82 return h; 83 } 84 85 int isok(int s[]) 86 { 87 int i,j,cnt; 88 for(i=cnt=0;i<9;i++){ 89 for(j=i+1;j<9;j++) 90 if(s[i]!=8 && s[j]!=8 && s[i]>s[j])cnt++; 91 } 92 return !(cnt&1); 93 } 94 95 int astar(int s[]) 96 { 97 int i,j; 98 Node u,v; 99 priority_queue<Node> q; 100 for(i=0;i<9;i++)u.ma[i]=s[i]; 101 u.sta=hs.ctadd(s); 102 u.g=0;u.h=geth(s); 103 for(i=0;i<9;i++)if(s[i]==8){u.x=i/3,u.y=i%3;break;} 104 q.push(u); 105 path[u.sta].fa=-1; 106 while(!q.empty()){ 107 u=q.top();q.pop(); 108 for(i=0;i<4;i++){ 109 v.x=u.x+dx[i]; 110 v.y=u.y+dy[i]; 111 if(v.x>=0&&v.x<3 && v.y>=0&&v.y<3){ 112 for(j=0;j<9;j++)v.ma[j]=u.ma[j]; 113 v.ma[v.x*3+v.y]=u.ma[u.x*3+u.y]; 114 v.ma[u.x*3+u.y]=u.ma[v.x*3+v.y]; 115 v.sta=hs.ctadd(v.ma); 116 if(v.sta>=0){ 117 path[v.sta].op=i; 118 path[v.sta].fa=u.sta; 119 v.g=u.g+1; 120 v.h=geth(v.ma); 121 q.push(v); 122 } 123 if(v.sta==end){ 124 return v.sta; 125 } 126 } 127 } 128 } 129 return -1; 130 } 131 132 void print(int u) 133 { 134 if(path[u].fa==-1)return; 135 print(path[u].fa); 136 printf("%c",out[path[u].op]); 137 } 138 139 int main() 140 { 141 // freopen("in.txt","r",stdin); 142 int i,j,s[10],ans; 143 char c[N]; 144 fac[0]=1; 145 for(i=1;i<9;i++)fac[i]=i*fac[i-1]; 146 end=0; 147 148 while(gets(c)){ 149 for(i=j=0;c[i];i++){ 150 if(c[i]!=' '){ 151 if(c[i]=='x')s[j]=8; 152 else s[j]=c[i]-'1'; 153 j++; 154 } 155 } 156 157 for(i=0,j=1;i<9;i++)if(s[i]!=i){j=0;break;} 158 if(j){ 159 putchar('\n'); 160 continue; 161 } 162 if(isok(s)){ 163 hs.init(); 164 ans=astar(s); 165 print(ans); 166 } 167 else printf("unsolvable"); 168 putchar('\n'); 169 } 170 return 0; 171 }