拼图游戏之可解性条件

可解的必要条件

游戏中只能由不断的空块和相邻的块做交换完成。而可解性也由交换数的奇偶性决定,交换数定义为通过交换任意块使得其恢复原状需要的次数。

考虑包含空块在内的交换数:空格子移动一步的时候,进行了一次交换,交换数的奇偶性发生改变。显然最后的奇偶性取决于空格移动步数的奇偶性。而移动步数奇偶性不依赖于具体路径,只依赖于初末位置。我们可以找一条最简单的路径的长度(曼哈顿距离)的奇偶性来判断可解性。

必要条件 移动步数奇偶性必须等于排列数/交换数的奇偶性

more ...

Integrable Constraint

In N dimension,

$$\begin{aligned} \bm f\times\bm g&\rightarrow f_a\times g_b=[f_ag_b]_{ab}\\ \bm f …
more ...