八数码问题搜索有非常多高效方法：如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]方法二：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 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#include #include #include 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]