八数码问题搜索有非常多高效方法：如A*算法、双向广搜等
但在搜索过程中都会遇到同一个问题。那就是判重操作（假设反复就剪枝），怎样高效的判重是8数码问题中效率的关键
以下关于几种判重方法进行比較：编码、hash、set
看到问题刚開始学习的人最先想到的应该就是用一个vis数组标志一下就可以。
可是该申请多大的数组呢？一个9维数组（9^9=387420489太大了吧）？假设内存同意这是最高效的办法：O(1)
所以我们如今面临的问题是怎样在O(1)的时间复杂度不变的情况下把空间压缩下来：
方法一：编码、解码，我们能够发现8数码问题最多有9！=362880个状态，假设我们对这些状态进行编码，用一个362880大小的数组就能够了，内存消耗大大减少，效率也基本不变，效率非常高。但对于问题中状态过多时这样的方法存在局限性。
代码：
int vis[362880],fact[9];
void init_lookup_table(){
fact[0]=1;
for(int i=1;i<9;++i) fact[i]=fact[i-1]*i;
}
int try_to_insert(int s){
int code=0;
for(int i=0;i<9;i++){
int cnt=0;
for(int j=i+1;j<9;++j) if(st[s][j]<st[s][i]) cnt++;
code+=fact[8-i]*cnt;
}
if(vis[code]) return 0;
return vis[code]=1;
}方法二：hash函数：效率非常高。这样的方法是用范围比較广。hash函数的选取非常重要（好的hash函数冲突小）。前面的编码相当于一种完美的hash函数，没有冲突。
代码：
const int hashsize=1000003;
int head[hashsize],next[maxstate];
void init_lookup_table(){memset(head,0,sizeof(head));}
int hash(State& s){
int v=0;
for(int i=0;i<9;i++) v=v*10+s[i];
return v%hashsize;
}
int try_to_insert(int s){
int h=hash(st[s]);
int u=head[h];
while(u){
if(memcmp(st[u],st[s],sizeof(st[s]))==0) return 0;
u=next[u];
}
next[s]=head[h];
head[h]=s;
return 1;
}方法三：stl set集合：编码相对简单了很多。可是这样的方法效率也最低，对与时间要求比較高的题目，我们能够先用set。然后用hash取代
代码：
set<int> vis;
void init_lookup_table(){vis.clear();}
int try_to_insert(int s){
int v=0;
for(int i=0;i<9;i++) v=v*10+st[s][i];
if(vis.count(v)) return 0;
vis.insert(v);
return 1;
}题目链接：点击打开链接
通过题目看效率：vijos八数码问题
编码：122msAC
hash：197msAC
set：932msAC
代码：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <set>
typedef int State[9];
using namespace std;
const int maxstate=1000000;
State st[maxstate],goal={1,2,3,8,0,4,7,6,5};
int dist[maxstate];
int fa[maxstate];
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
/********************编码、解码***********************/
int vis[362880],fact[9];
void init_lookup_table(){
fact[0]=1;
for(int i=1;i<9;++i) fact[i]=fact[i-1]*i;
}
int try_to_insert(int s){
int code=0;
for(int i=0;i<9;i++){
int cnt=0;
for(int j=i+1;j<9;++j) if(st[s][j]<st[s][i]) cnt++;
code+=fact[8-i]*cnt;
}
if(vis[code]) return 0;
return vis[code]=1;
}
/*********************hash表************************
const int hashsize=1000003;
int head[hashsize],next[maxstate];
void init_lookup_table(){memset(head,0,sizeof(head));}
int hash(State& s){
int v=0;
for(int i=0;i<9;i++) v=v*10+s[i];
return v%hashsize;
}
int try_to_insert(int s){
int h=hash(st[s]);
int u=head[h];
while(u){
if(memcmp(st[u],st[s],sizeof(st[s]))==0) return 0;
u=next[u];
}
next[s]=head[h];
head[h]=s;
return 1;
}
**********************stl set集合************************
set<int> vis;
void init_lookup_table(){vis.clear();}
int try_to_insert(int s){
int v=0;
for(int i=0;i<9;i++) v=v*10+st[s][i];
if(vis.count(v)) return 0;
vis.insert(v);
return 1;
}
***********************************************/
int bfs(){
init_lookup_table();
int front=1,rear=2;
while(front<rear){
State &s=st[front];
if(memcmp(goal,s,sizeof(s))==0) return front;
int z;
for(z=0;z<9;++z) if(!s[z]) break;
int x=z/3,y=z%3;
for(int d=0;d<4;++d){
int newx=x+dx[d];
int newy=y+dy[d];
int newz=newx*3+newy;
if(newx>=0&&newx<3&&newy>=0&&newy<3){
State& t=st[rear];
memcpy(&t,&s,sizeof(s));
t[newz]=s[z];
t[z]=s[newz];
dist[rear]=dist[front]+1;
fa[rear]=front;
if(try_to_insert(rear)) rear++;
}
}
front++;
}
return 0;
}
int main(){
char ch;
for(int i=0;i<9;i++) {
//scanf("%d",&st[1][i]);
cin>>ch;
st[1][i]=ch-'0';
}
//for(int i=0;i<9;i++) scanf("%d",&goal[i]);
fa[1]=-1;
int ans=bfs();
if(ans>0) printf("%d
",dist[ans]);
else
printf("-1
");
return 0;
}