POJ 1077 八数码 三种解法

题目

题目链接：http://poj.org/problem?id=1077

有人说做搜索不做这道题，人生遗憾。我做完了之后，嗯，同意。

思考

关于八数码问题，有以下几个问题需要想明白：

【状态表示和状态判断】 题目是按照连续9个字符的形式读入的，自然想到在node中用一个s[9]的数组存储当前状态。但是可以马上否认的是，我们不可能也用这个字符串来进行状态之间的比较，因为效率太低，操作麻烦，实现费劲。这个字符串一共有9!中排列方式，这里有一个定理：康托展开。很好地解决了存储和比较两个问题。通过康托展开，就可以把这9!个数字分别转换为一个int（注：9! = 362880 < 2^31-1)

【无解状态剪枝】 我们要的最后一个状态是{1， 2， 3， 4， 5， 6， 7， 8， x}， 这个排列的逆序数是0，是偶数。而对于任意一个排列，显然，因为x不表示数字，那么也就是说把x向左右两个方向移动并不会改变整个序列的逆序数，那么有结论： 如果初始序列的逆序数是一个奇数，则必然这个序列无解（必要，不充分）

有了以上两个想法，下一步就是选择搜索策略： bfs可以，A*可以，IDA*也可以

【参考代码】