问题分析 将每一个状态作为一个结点容易想到可以用广搜的方法解决，这种方法简单，但是就算是加入哈希判重也会搜索很多的无用结点。 我们打算用A*算法解决这个问题，既然确定了用A*算法，那么我们首先应该确定估价函数h(x)，估价函数的选取直接决定A*算法的效率，一般对于八数码问题有三种估价函数的选法：

可以证明前两种都是乐观估计，最后一种不是，因此前两种都可以作为八数码问题的估价函数，但是你的估计值与真实值越近所需要搜索的状态越少，很明显第一种方法太乐观了（估价函数的选取直接决定算法的效率），因此我们采用第二种方法作为八数码问题的估价函数

解决了估价函数的问题以后，第二个需要解决的问题就是判重，我们首先想到的是用集合set，这种方法最简单，但是很不幸这种方法耗时也是最多的，如果时间要求比较高的话，这种情况很容易超时。这里我们不用这种方法，判重问题自然而然想到的是哈希表，好了现在问题又来了，如何创建哈希表，也就是哈希函数怎么写，这个东西比较有技巧，还好对于这种问题有一种现成的方法解决，那就是康托展开 ，还有一个问题就是有些问题是无解的，这种情况我们不希望进行很大力气的搜索之后发现无解，最好是能提前预知，值得庆幸的是八数码无论怎么移动逆序的奇偶性不变，因此我们可以直接通过O（1）的时间判断开始和目标结点的逆序奇偶性是否相同就可以了。有了上面的分析之后，程序就可以写出来了 自己写代码的话，可以用一个一维数组存储状态，二维数组实在有些麻烦

代码如下