最近在PKU的ACM上做了八数码问题，将经验总结以下：
（1） 用A*算法， 估价函数选“Hamilton距离”比选用“在错误方各内的数字数目”强很多。
（2）A*算法的关键是要能够使“找到耗费最小的节点”和“判断是否子节点已经存在”的算法的效率尽可能高，为此，网上不少资料建议采用Binary Heap或Hash table等数据结构，然而单独使用任何一种数据结构，都有一定的缺陷，将Heap和Hash联合起来使用，应该可以提高不少效率。具体如下：
1。建一张Hash表，存放没一个节点的具体信息，如当前状态、父节点在表中的位置等。
2。open表中存放着一些节点，这些节点不同于Hash表中的节点，可以将它理解为是Hash表中节点的索引，它只包含节点的估价和节点在Hash表中的位置，这些节点按估价排列成堆（Heap）。
3。没必要再建一个closed表。
这样，程序的流程就可以写成：
初始化Hash表和open表；
 将根节点放入Hash表和open表；
 found = false;
 while(open表不空) {
     从open表中得到耗费最低的节点的索引cur;  // O(1)
     从open表中删除耗费最低的节点;  // O(logN)
     for 每个cur的子节点now do {
          if ( now 是目标节点 ) {
                  打印输出;
                  found = true;
                  结束搜索;
          }
          if( now 不在Hashtable中 ) {  // O(1)
               将now插入Hashtable中;  // O(1)
               将now的索引放入open表中;  // O(logN)
          } else if( now比Hashtable中的节点优 ) {  
               if( 原节点在open表中 ) {  // O(N)
                    用now替代原来节点;  // O(1)
                    在open中push_heap来更新open表的顺序;  // O(logN)
                }
          }
      }
  }
  if( !found ) 输出 "无解";
可以看到，虽然查找open表中已存在的节点仍然为O(N)， 但是当now已存在时，now比open表中节点优的概率是很小的，事先用O(1)的时间判断，就可以避免用O(N)的时间来查找，从而提高了效率（这很像是CPU的Cache的工作原理）。
具体程序如下：
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <cassert>
using namespace std;
struct OpenNode{
 int cost, point;
 OpenNode(){}
 OpenNode( int cost, int point ){
  this->cost = cost;
  this->point = point;
 }
};
bool operator<( const OpenNode& a, const OpenNode& b ){
 return a.cost > b.cost;
}
bool operator==(const OpenNode& a, int c){
 return a.point == c;
}

struct HashNode{
 char state[3][3];
 int g, h, par, dir,x,y;
 bool used;
 HashNode(){
  used=false;
 }
};

int dx[] = { -1,0,1,0 },
dy[] = { 0,1,0,-1 };  // u r d l

const int HASH_SIZE = 39999;
HashNode List[HASH_SIZE];
int factorial[] = {1,1,2,6,24,120,720,5040,40320};
/*int hash( char state[3][3] ){
int ret = 0;
char *p, *q;
for(p=&state[0][0];p<=&state[2][2];p++){
int cnt = 0;
for(q=&state[0][0]; q<p; q++) if( *q<*p ) cnt++;
ret += factorial[&state[2][2]-p]*(*p-cnt);
}
return ret;
}*/
bool eq( char a[3][3], char b[3][3] ){
 for(int i=0;i<3;i++)
  for(int j=0;j<3;j++) if( a[i][j]!=b[i][j] ) return false;
  return true;
}
int hash( char state[3][3] ){
 char* p = &state[0][0];
 int ret = p[0] * 7 + p[1] * 17 + p[2] * 47 + p[3] * 117 + p[4] * 217 + p[5]
  * 977 + p[6] * 1299 + p[7] * 5971 + p[8] * 7779;
 ret %= HASH_SIZE;
 while( List[ret].used && !eq(List[ret].state , state) )
  ret= (ret+1) % HASH_SIZE;
 return ret;
}
int h( char state[3][3] ){
 int ret = 0;
 for(int x=0;x<3;x++)
  for(int y=0;y<3;y++) if( state[x][y]!=0 )
   ret += abs((state[x][y]-1)/3-x) +abs((state[x][y]-1)%3-y);
  return ret;
}
void output( int i ){
 string res;
 while(List[i].dir>=0){
  res+= List[i].dir==0?'u':List[i].dir==1?'r':List[i].dir==2?'d':'l';
  i = List[i].par;
 }
 reverse( res.begin(), res.end() );
 cout<<res<<endl;
}
bool solvable( char state[3][3] ){
  int t = 0;
  for(char* i=&state[0][0];i<&state[2][2];i++)
    for(char* j=i+1;j<=&state[2][2];j++)
      if(*i!=0 && *j!=0 && *i>*j) t++;
  if(t%2) return false;
  return true;
}
vector<OpenNode> open;
int main(){
 string init;
 getline( cin, init );
 HashNode now;
 int cnt=0;
 for(int i=0;i<init.size();i++) {
  if(init[i] == 'x') {
   now.state[cnt/3][cnt%3] = 0;
   now.x = cnt /3;
   now.y = cnt %3;
   cnt++;
  } else if(init[i]!=' ') {
   now.state[cnt/3][cnt%3] = init[i] - '0';
   cnt++;
  }
 }
 if( !solvable(now.state) ) {
   cout<<"unsolvable"<<endl;
   return 0;
 }
 now.g = 0;
 now.h = h(now.state);
 now.par = -1;
 now.dir = -1;
 now.used = true;
 int i = hash(now.state);
 List[i] = now;
 open.push_back(OpenNode(now.g+now.h,i));
 while(!open.empty()){
  int cur = open.front().point;
  pop_heap( open.begin(), open.end() );
  open.erase( open.end()-1 );
  for(int i=0;i<4;i++){
   now = List[cur];
   int x = now.x+dx[i];
   int y = now.y+dy[i];
   if(x<0||x>2||y<0||y>2) continue;
   swap( now.state[x][y], now.state[now.x][now.y] );
   now.x = x;
   now.y = y;
   now.h = h( now.state );
   now.g++;
   now.par = cur;
   now.dir = i;
   
   int hashcode = hash( now.state );
   if( now.h == 0 ){
    List[hashcode] = now;
    output( hashcode );
    return 0;
   } else if( !List[hashcode].used ){
    List[hashcode] = now;
    open.push_back( OpenNode(now.h+now.g,hashcode) );
    push_heap( open.begin(), open.end() );
   } else if( List[hashcode].g+List[hashcode].h > now.g+now.h ){
    List[hashcode] = now;
    vector<OpenNode>::iterator it = find( open.begin(), open.end(), hashcode );
    if(it==open.end()) continue;
    push_heap( open.begin(), it+1 );
   }
  }
 }
 cout<<"unsolvable"<<endl;
 return 0;
}