经典的八数码问题，这几天尝试了一些不同的做法，现在总结下。
1.广搜+哈希
这是最容易想到的一种做法，哈希的方法是康托展开，组合数学上有介绍。
广搜+哈希
2.双向广搜+哈希
双向广搜的复杂度大约是单向的一半，所以效率上会有不错的提高。
双向广搜+哈希
3.A*+哈希+曼哈顿距离
用到广搜，就可以想到能用经典的A*解决，用深度作为g(n)，剩下的自然是启发函数了。对于八数码，启发函数可以用两种状态不同数字的数目。接下来就是A*的套路，A*的具体思想不再赘述，因为人工智能课本肯定比我讲的清楚。但是必须得注意到，A*需要满足两个条件：
1.h(n)>h'(n),h'(n)为从当前节点到目标点的实际的最优代价值。
2.每次扩展的节点的f值大于等于父节点的f值小。
自然，我们得验证下我们的启发函数，h验证比较简单不用说，由于g是深度，每次都会较父节点增1。再看h，认识上， 我们只需要将h看成真正的“八数码”，将空格看空。这里，就会发现，每移动一次，最多使得一个数字回归，或者说不在位减一个。 h最多减小1，而g认为是深度，每次会增加1。所以，f=g+h， 自然非递减，这样，满足了A*的两个条件，可以用A*了！
A*+哈希+曼哈顿距离
4.IDA*+曼哈顿距离
因为要用到IDA*搜索，所以我们搜索之前先判断一下是否有解。
判断的方法是学习一个大神的： 判断八数码问题是否有解
IDA*比起BFS的好处是空间复杂度极低，同时因为有剪枝，比起BFS降低了盲目性；比起A*的好处是不用去维护一个堆。
IDA*+曼哈顿距离