拼图游戏

- 日理万妓 2022-08-07 08:52 264阅读 0赞

## [拼图游戏][Link 1] ##

本文讨论如何判断拼图游戏中图形是否可以还原。

例1：下图是一个3X3的数字拼图。

图1

它要还原成图2

图2

将问题一般化，在M\*N的方格里有M\*N-1个不同元素和一个空元素，只有空元素可以与上下左右相邻的元素交换位置。M\*N方格中M\*N-1个元素和一个空元素的位置确定一个图形。拼图游戏的问题是：一个图形经过一连串的交换能否得到另一个图形，如何得到。从交换方式的可逆性看出这种关系满足等价三性质，如果图形A通过交换变成图形B我们则称它们是等价的。把M\*N-1个元素用1至M\*N-1编号，空元素编号0。然后展成一个排列。每个图形对应一个排列。确定了展开方式，图形和排列是一一对应的。这里用到的展开方式是行优先的顺序（其他方式展开也能到相应的结果）。将例1的两个图形展开有：图1对应1 3 2 6 0 5 4 7 8，图2对应1 2 3 4 5 6 7 8 0。

**定理****1****：**图形A与图形B等价的充要条件图形A的排列的逆序数加上0元素行号和列号的奇偶性等于图形B的排列的逆序数加上0元素行号和列号的奇偶性。为方便表述，把图形排列的逆序数加上0元素行号和列号的奇偶性称为图形的奇偶性。

先看定理1如何起作用，图1：展开的排列 1 3 2 6 0 5 4 7 8，它的逆序数为8，0元素行号为2，列号为2。逆序数加行号，列号的奇偶性为偶。图2：展开的排列 1 2 3 4 5 6 7 8 0，它的逆序数为8，0元素行号为3，列号为3。逆序数加行号，列号的奇偶性为偶。两个图形的奇偶性相同，根据定理1判断它们等价。

首先证明必要性，即如果图形A与图形B等价，则图形A的奇偶性等于图形B奇偶性。

0元素和某个元素交换位置，则排列的逆序数的奇偶性就改变一次。交换后0元素的行号或者列号会加1或减1，即行号，列号之和的奇偶性也改变一次。这说明拼图的交换方式不改变图形的奇偶性，也说明拼图中至少有两组等价类，奇偶性不同的图形不等价。

下面证明充分性，如果图形A的奇偶性等于图形B的奇偶性，则图形A，B等价。

如果证明了拼图只有两组等价类，从必要性的证明过程可知，奇性图形是一组等价类，偶性是一组。从而证明了充分性。

先考虑一般的排列1 2 3 ... N。某个元素连续与后面M相邻的元素交换位置，称为向后M步移动。如排列：1 2 3 4 5 6。元素2的向后3步移动，排列变成1 3 4 5 2 6。同样的方式定义向前M步移动。如果排列A能够通过有限向前M步移动和向后M步移动变成排列B，称排列A与排列B M步等价。容易看出这也是等价关系。

**引理****1****：**任何一个1至N的排列M步等价于1 2 ... N-M（...）。括号里是N-M+1至N的某个排列。

证明：如果N=M，这显然成立。

假设N=k时成立，下面证明k+1的情况。

1元素的位置记为i

情况1：假设i=1，显然，余下的元素减1，就变成N=k的境况，得证。

情况2：如果1<i<=M，则元素1前面的元素向后M步移动，变为情况1。

情况3：如果i>M，则元素1有限次向前M步移动，使i有1<=i<=M，可变成情况1或2。

从而得证。  
当M=2时，只有两组等价类。由于移动不改变排列的奇偶性，从而奇排列是一组等价类，偶排列是一组等价类。

考虑N\*M的拼图。  
当N=M=2，穷举法可证明只有两组等价类。

当N，M不同时为2时，设N不等于2（如果N等于2，M不等于2可颠倒行列讨论）。

只考虑第二行最后一个元素是空元素的情形，因为空元素在其他位置总可以等价某个空元素在第二行最后一个元素的图形。不考虑空元素以之字形方式展开图形，即第一行最后一个数字和第二行倒数第二个数字相连。如：

图3