On the Solvability of 8-Puzzle
人智课一次作业是写一个 A* 程序算八数码问题的最优解. 一个自然的问题是, 什么样的初始状态有解?
一个熟知的结论是, 将矩阵元素排成一排, 忽略空格, 当且仅当逆序对个数为偶数时此问题有解.
必要性很好证明, 因为观察可知所有的移动操作不会改变逆序对个数的奇偶性. 那充分性呢?
要证明充分性, 需要将矩阵用另一种方式展开成一排:
考虑每次移动对这种排法的影响, 例如:
序列的变化是:
其实就相当于置换
我们把所有这样的置换求出来 (其实本质不同的总共只有 4 种), 可以证明这些置换恰好能够生成 8 元偶置换群.
那么就证明了, 所有的 8 元偶排列互相都是可到达的.
但是这里的 "偶" 是定义在新的矩阵展开方式下的了,
所以还没完.
由于一个 8 元偶排列对应 9 个状态,
因此有
说的有点简略了, 我把详细的证明放在 github 上.
当然, 写个程序验证它的可解性要快得多..