给定Task：
3x3的区域，标记有1-8八个数字的方形棋子，剩下一个区域为空
游戏过程中，只能移动棋子到相邻的空区域上，当移动到如下位置时，游戏结束。
问：从给定棋盘状态到游戏结束时，需要的步数。
首先，最简单暴力的算法是什么呢？
BFS。将3*3的棋盘看作一种状态，每个区域只出现一个数字，每个数字只出现一次。第一个位置有9种可能，第二个位置8种可能，所以一共9!=362880种可能。
通过什么方法能表示不同排列的状态呢？
Answer：康托展开
康托展开
e.g 三个数的排列，按顺序就是：123, 132, 213, 231, 312, 321
对于一个长度为n的排列num[1..n]，其序号X为：
X = a[1](n-1)!+a[2](n-2)!+…+a[i](n-i)!+…+a[n-1]1!+a[n]*0!
其中a[i]表示在num[i+1..n]中比num[i]小的数的数量
num[] = {2, 1, 3}
a[] = {1, 0, 0}
X = 1 * 2! + 0 * 1! + 0 * 1! = 2
我们如果将3的全排列从0开始编号，2号对应的正是213。所以可以以顺序（唯一性）表示一个状态，范围最多为362880。
BFS过程中，我们利用队列Q保存当前步数最少的状态，从该状态开始继续搜索到终态。
启发式搜索
启发式搜索算法大概就是利用一些“启发性”信息（先验知识），来引导搜索过程，达到减少搜索范围，降低时间复杂度的作用。
在启发式搜索的过程中，不一定按照步数最优的顺序来搜索。我们通过加入额外的先验知识H，按照“最有希望是最优步数”的状态进行搜索。
具体来说，我们用G表示BFS搜索过程中，从起始状态到当前状态的最少步数。用H表示一个估计值，表示从当前状态到终态的步数。
F=G+H用来评判当前状态是否最有希望成为最优解。因为加入了人为设计的评估函数H，所以往往启发式搜索要比普通BFS快很多。
值得注意的是，在设计评估函数的时，评估函数的值一定要小于等于当前状态到目标状态的代价（步数）。
WHY？
我们搜索的准则是先选择F值少的状态进行扩展，所以如果评估函数大于实际代价，导致状态F偏大，当前搜索转之选择其余状态，有可能搜索过程中漏掉了最优解。相对的，只要评估函数的值小于等于实际当前状态到目标状态的代价，就一定能找到最优解。
这里，评估函数H可以设计为：1-8八数字当前位置到目标位置的曼哈顿距离之和。
WHY？
曼哈顿距离如图中红蓝黄线所示。两个位置直接通过一格一格地交替进行交换，可见曼哈顿距离是当前位置和目标位置之间最短的距离。
游戏规则是只能移动棋子到相邻的空区域上，所以借助于空区域交换所有八数字到目标位置与八个数字分别和目标位置一格一格“直接走路”过去交换相比，前者步数一定大一些。（我暂时是这么理解的）
小插曲：逆康托展开
已知X，如何方向求解出全排列？
根据X的求值公式，可以推断出对于a[i]来说，其值一定小于等于n-i。那么有：
a[i]≤n-i, a[i](n-i)!≤(n-i)(n-i)!<(n-i+1)!
也就是说，对于a[i]来说，无论a[i+1..n]的值为多少，其后面的和都不会超过(n-i)!
那么也就是说，如果我用X除以(n-1)!，得到商c和余数r。其中c就等于a[1]，r则等于后面的部分。
这样依次求解，就可以得到a[]数组了！
比如求解3的全排列中，编号为3的排列：
3 / 2! = 1 … 1 => a[1] = 1
1 / 1! = 1 … 0 => a[2] = 1
0 / 0! = 0 … 0 => a[3] = 0
从num[1]开始，依次从尚未使用的数字中选取第a[i]+1小的数字填入就可以了！
a[] = {1, 1, 0}
unused = {1, 2, 3}, a[1] = 1, num[1] = 2
unused = {1, 3}, a[2] = 1, num[2] = 3
unused = {1}, a[3] = 0, num[3] = 1
=> 2, 3, 1