On the Solvability of 8-Puzzle

人智课一次作业是写一个 A* 程序算八数码问题的最优解. 一个自然的问题是, 什么样的初始状态有解?

一个熟知的结论是, 将矩阵元素排成一排, 忽略空格, 当且仅当逆序对个数为偶数时此问题有解.

必要性很好证明, 因为观察可知所有的移动操作不会改变逆序对个数的奇偶性. 那充分性呢?


要证明充分性, 需要将矩阵用另一种方式展开成一排:.

考虑每次移动对这种排法的影响, 例如:

序列的变化是:

其实就相当于置换

我们把所有这样的置换求出来 (其实本质不同的总共只有 4 种), 可以证明这些置换恰好能够生成 8 元偶置换群.

那么就证明了, 所有的 8 元偶排列互相都是可到达的.

但是这里的 "偶" 是定义在新的矩阵展开方式下的了, 所以还没完. 由于一个 8 元偶排列对应 9 个状态, 因此有 个状态互相可到达. 这样才证完了.

说的有点简略了, 我把详细的证明放在 github 上.

当然, 写个程序验证它的可解性要快得多..

Comments