今年的极客大挑战有道题是这样的，给你一个3*3的拼图，不过顺序是乱的，可以移动拼图，问把原图拼出来，最少要多少步。

很显然这题可以转化成一道八数码问题，因为极客大挑战对时间空间没有特别要求，所以用普通搜索就能很快解决。正好现在空闲的时间比较多，来总结一下八数码问题的学习笔记。

<!-- more -->

以前看过一篇博文叫《八数码的八境界》，详细地介绍了八数码的各种解法，给了我很大的启发。然而这里我想总结一下我熟悉的几种解法。

直接讨论经典问题感觉挺空洞的，还是直接拿ACM题来说吧。

POJ 1077 应该是最基本的八数码问题，数据不是很强，题意就简述一下了，就是给了一个3*3的宫格，问移动最少多少步能移动成最初形态,如

 1  2  3      =>         1 2 3
 x  4  6      =>         4 5 6
 7  5  8      =>         7 8 x

###NOTE 1.单向BFS+Hash

BFS很好想到，移动的方向只有4种，上下左右。直接上BFS的话肯定不行，会TLE。加上hash能让程序快不少。

如果记录每一位的信息，那么Hash数组的大小将达到$$10^9$$，用大质数减少碰撞，加上手写静态链表前向星什么的应该是能够接受的。

这里介绍一种巧妙的Hash方法减少空间开销。

观察一下可以发现，把x替换为9，那么3*3的宫格内的数依次写下来其实就是1～9的全排列，种类数有9!=362880种。

康托展开是构建哈希表时压缩空间常用的一种方法。康托展开实质上是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的。计算方法如下：

数列a[n]是1～n的全排列，b[i]是表示第i位之后大于a[i]的数的个数。 X=b[n](n-1)!+b[n-1](n-2)!+…+b[i]*(i-1)!+…+b1*0!

如：排列3 5 7 4 1 2 9 6 8 展开为 98884。因为X=28!+37!+46!+25!+04!+03!+22!+01!+0*0!=98884.

排列的第一位是3，比3小的数有两个，以这样的数开始的排列有8!个，因此第一项为2*8!

排列的第二位是5，比5小的数有1、2、3、4，由于3已经出现，因此共有3个比5小的数，这样的排列有7!个，因此第二项为37! 以此类推，直至00!

所以对于BFS时，搜到的每一种状态，用康托展开进行Hash，就可以放到一个大小为9!的哈希表中进行判重。

网上很多人都是这样做的，为了宝贵的空间，所以这里就不发代码了。 ###NOTE 2.双向BFS+Hash

因为这道题的终态是固定的

1 2 3 
4 5 6
7 8 x

所以我们可以从这个状态和输入的初始状态开始双向BFS。

用两个队列，一个队列保存从终态开始BFS，所保存的状态节点；另一个保存从始态开始BFS，所保存的状态节点。哪个队列的节点数少，就展开哪个节点。再加上Hash，所以应该会很快搜到一个可行解。

这里推荐一道双向BFS的题目和解题报告 LA 3618 Cubic Eight-Puzzle-立体八数码 以及 解题报告

###NOTE 3.A*搜索+Hash

此题状态很明确，而且分支不算多，估价函数也很好找。

曼哈顿距离，对于坐标(x1,y1)和坐标(x2,y2)，曼哈顿距离就是$|x1-x2|+|y1-y2|$。

拿每个方格到它的目标方格的曼哈顿距离作为估价函数h，加上当前的搜索深度作为启发函数f，进行A搜索。搜索的时候需要加上Hash判重，遇到状态相同，保留启发函数值较小的那个即可，加上堆/优先队列，每次展开f值最小的节点，这样便能用A搜索AC此题。

###NOTE 4. IDA*搜索

IDA搜索，其实是迭代加深版的A搜索。

迭代加深(Iterative Deepening)，也是一种搜索的策略。适用于解在搜索树中的深度不是很深，然而搜索树的分支特别多的情况下使用。具体的做法是：限定一个最大深度dmax，再进行DFS，一旦搜索的深度达到了dmax就退出。如果没有搜到，就把dmax+1，再进行DFS，直到搜索到解为止。由此避免了DFS搜索深度过深，而找不到正确解。

推荐一道迭代加深搜索的题目POJ 2870 Light Up 以及 解题报告

迭代加深版的A*搜索，其实就是在迭代加深时，计算当前状态h值，加上当前深度，算出f值，一旦f值大于dmax就推出。

IDA搜索的代码编写较A来说要简单得多。A代码多，主要在于用来判重的Hash表和对f值排序的堆。然而IDA是DFS，所以根本不用判重，也不需要对f值进行排序，也减少了空间消费。

代码在这里：LA 5506 Eight

NOTE 5.求逆序数判断是否有解

现在来考虑一道新的问题，HDU 4021

此题实际上并没有要求我们找到一组正确的解，而是询问是否有解。

对于八数码问题来说，如果方格和空格上下左右移动，对于数列逆序数的奇偶性是不会变的。

上下移动相当于此数在数列中向前或向后移动了2个位置，要么两个数都比它大，逆序数+2，要么都比它小，逆序数-2，要么一大一小，逆序数的奇偶性不变。

左右移动，此数在数列中的位置不变，奇偶性不变。

总的来说逆序数的奇偶性是不变的。

有了这个判定，可以让我们在搜索一开始便对数列的有解性进行一个判断。

对于n维的n*n-1问题来说，有这样的结论：

N为奇数时，初始状态与指定状态逆序数奇偶性相同即有解；
N为偶数时，先计算出从初始状态到指定状态，空位要移动的行数m，如果初始状态的逆序数加上m与指定状态的逆序数奇偶性相同，则有解。