那么这个题主要的思维难度在于如何设计状态，很多人都会想到用一个3*3的数组来模拟这个9宫格，但是实际上是不可行的，因为我们没有办法去表示这个状态下与初始状态的移动步数（也许可以用哈希表，但博主不会）那么如何来设计我们的状态呢？其实题目给了我们提示：用一个9位数来表示这个并状态，与数组上上的位置一一对应。举个例子：

123740865 1 2 3 7 4 0 8 6 5 

用9位数的话，可以很好的表示到了这个状态后与初始状态的移动步数是多少，因为9位数比较大，开数组浪费空间，我们可以选择用map,但是有人要问了：如果用9位数的话，我们如何去交换两个数的位置呢？其实如果是一个数组的话就比较容易转换的。相信读者也注意到了，这里的数组与我们9位数的状态之间是可以互相转化的，我们只需要稍微处理一下，编个函数也罢。

所以这个题的总体思路就是：用9位数作为状态传递，用数组去模拟交换！

A*

因为这个题用到了A*算法，所以这里就简单的讲讲A*是什么.

简单地说，我们平常的搜索算法多是没有目的的搜索，但是呢A*却是有目的的搜索，好比一个人在操场上，要去国旗旗杆，平常的搜索更像是一个瞎子，最坏的话要把操场每一个位置都找遍才能到达旗杆的位置，但是A*更像是一个正常人，一眼看见旗杆的位置，并朝那个方向走过去，很明显A*算法要比BFS或DFS便捷的多，事实也是如此：A*比平常的搜索算法快得多！，这个题也不例外。

那么如何使用A*呢

我们对每个点定义一个估价函数f(x)=g(x)+h(x)，g(x)表示从起始点到x的实际代价,h(x)表示估计的从x到结束点的代价，并要求h(x)小于等于从x到结束点的实际代价,那么每次我们从可行点集合中找到f(x)最小的x，然后搜索他,这个过程可以用优先队列（即堆）实现,这样的话可以更快地到达结束点，并保证到达结束点时走的是最优路径,一般来说，h函数的选择决定了A*算法的效率，h函数与实际值的差距越小越好