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

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

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

要证明充分性, 需要将矩阵用另一种方式展开成一排:$(a_{11}a_{12}a_{13}a_{23}a_{22}a_{21}a_{31}a_{32}a_{33})$.

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

$$ P_1 = \begin{bmatrix}a &\Box & b \\ c&d;&e; \\ f&g;&h; \\ \end{bmatrix} \rightarrow P_2 = \begin{bmatrix}a&d;&b; \\ c&\Box&e; \\ f&g;&h; \\ \end{bmatrix} $$

序列的变化是: $$ (a,b,e,d,c,f,g,h)\rightarrow (a,d,b,e,c,f,g,h) $$

其实就相当于置换 $ \sigma = (2,3,4)$

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

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

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

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

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