数学与游戏：关于十五子的游戏

编者注：2018年1月5日，江苏卫视播出《最强大脑》第5季开播，头一个节目是数字华容道（又名十五子游戏），100位选手将淘汰掉1/5。在这个比赛中，赌王的儿子何猷君脱颖而出，以21秒的成绩夺冠，并因此第一个拿到直通30强的名额。何猷君有此成绩，跟他的数学天才不无关系，同时我猜，跟他在MIT念书（本科和硕士）也有密切关系，因为MIT有一门为计算机专业开设的数学课显然会讲到这个著名的游戏，你看有此为证：

而在国内，早就有人介绍15子游戏了，例如杨振宁先生就曾提到，他最初接触到排列组合并对对称发生兴趣，就源于初中时（当时大概是1935年左右）读到《中学生》杂志上一篇介绍15子游戏的通俗文章，再如，陈景润也在一本关于组合数学的小书里介绍了这个游戏。今天我们就将陈景润的这篇文章分享给大家。需要指出的是，这个游戏并非对所有的初始状态有解（请看下文），所以如果《最强大脑》节目组要想淘汰掉某些人，其实是很容易的，例如，只要给他设置一个根本无解的初始布局（就像在历史上有人就这么干过，参见维基百科 15-puzzle）。此外，除非每个人一开始的布局都是一样的，否则无法保证各位参赛者面对的可解布局所需的最少移动步骤是一样的。

本文介绍的方法是算法性质的，你读懂了它，就可以实际操作了。例如，你可以试一试MIT公开课程主页上的这个布局如何破解。下一期我们将介绍一种更高端、更近代的观点。总之，我们希望你能认识到，这个游戏里头有正儿八经的数学（而不是碰运气或靠小聪明），下一次我们再展开。

本文取自陈景润《组合数学简介》，一本很值得推荐给数学爱好者的好书。

——林开亮

 

 1 

在一张纸上，画上大小相同的十六个小方格，而把这些小方格构成一个正方形，再剪出十五个大小相同的正方形纸板，而这些正方形纸板面积稍小于方格的面枳。在这些小纸板上写上1到15这十五个标号。这样我们就可以来玩十五子游戏了。我们把这十五个纸板按任意的顺序放到这十六个小方格中去。由于每个小方格只能放一个，因而，有一个小方格是空着的。游戏规则是：当且仅当纸板与空格相邻时，该纸板才能和空格对换位置，而在这十五个方形纸板相互之间不能调换位置。例如, 图（2.1)是一种任意的排列情况，这时和空格相邻的纸板有1，8，4，11，而这时空格可以和这四个纸板中的任意一个相互对换位置，比如把空格右边的有标记4的纸板和空格相互对换位置后就成了图（2.2）。

现在的问题是：

能不能经过有限次的移动后把这十五子的顺序排为图（2.3)的样子。

我们知道，把这十五个纸板按任意的顺序放到这十六个小方格小去的方法一共有 16！=16×15×…×3×2 = 20922789888000种。如果每一种都要来试一下能不能排成图（2.3)的样子，那得花费多少时间呢？

当然我们可以一种一种的慢慢地试，但这不是一个好办法。于是，我们只能多动脑筋，寻找这个游戏的规律。

我们首先来看一下，如果把空格周围的某一纸板和空格置换对换，那么对换后，原来纸板所在的小方格就变成空格了，因此，我们总结出第一条规律，即空格经过几次和纸板相互对换后可以移动到这十六个小方格中的任一个位置上。利用这一个规律，我们还可以把任一个纸板移到这十六个小方格中的任一指定的方格上去。这是为什么呢？因为指定的方格与纸板原来所在的方格最多不过是上下差三格，左右差三格。要使纸板在这十六个小方格中向上移，我们只需把空格移到纸板上面一格，再将纸板和空格的位置相互对换后即可完成。若要使纸板向右移，我们可以把空格移到纸板的右边一格再将纸板和空格的位置相互对换后即可完成。同样，要使纸板向下或向左移动，都是办得到的。这样，我们又总结出一条非常重要的规律了，即任一纸板都能经过几次和空格相互对换后而移到这十六个小方格中的任一指定的方格中。为了叙述方便，我们将这十六个小方格标上号码，如图（2.4)，另外我们把十五个纸板分别称为1，2，3，…，15。根据我们总结的第二条规律，我们可以把1移到一号位置上。然后不动1， 能否把2移到二号位置上呢?这也是可以做到的。若2在第一列，我们可以把它移出第一列，我们同时也可以把空格移出第一列，从这时以后，第一列不动，而在第二、三、四列中，运用第二条规律，可以把2移到第二号位置上去。1，2的位置确定后，我们不动它，用相同的办法还可以把3移到三号位置上去。这时如果空格不在四号位罝上要想不动1，2，3，而把4移到四号位置上去，却不能够做到了。因为在四号位置右边和上边都没有方格， 而左边方格里的3又不能动，故只能有下边的第八号位置与它有联系了。然而我们总可以使第一行不动，而把4移到第八号位置，把空格移到第十二号位置，如图（2.5)。在图（2.5）中， 我们取出第三、四、七、八、十一、十二这六个方格出来而构成图(2.6)。

为了方便起见，这时我们将第四号、第七号、第十一号位置中纸板上的数字分別用甲、乙、丙来代替，即为图（2.6)。然后依次把4往下移，甲往下移，3往右移，乙往上移，就变成了图（2.7)。在图（2.7)中把甲往左移，把4往上移，把丙往右移，就变成了图（2.8)。在图（2.8)中把甲往下移，乙往下移，3往左移，4往上移，就成为图（2.9)。图（2.9)中3、4已分别在第三、第四号位置上，这正是我们想要得到的位置。

当第一行排好以后，我们不动第一行，按照同样方法，当然能够把5、6、7安排在第五、六、七号位置上，注意到我们安排4到第四号位置上时，仅用到第一、二、三行中的最后两个小方格，而第四行的格子没有用到，因此按照把4安排到第四号位置的办法，我们也能把8安排到八号位置上去。

当第二行排好后，我们来安排第三行与第四行时，就要使用不同的办法了。我们不是先排第三行，而是先排第一列后面的两 个位置，即第九和第十三号位置。这也不难做到，因为我们可以把第一列看为是第一行，按照排第一行后面的两个位置的办法来安排第一列后面的两个位置。例如我们可以先把9移到第九号位置上，这时若13恰好在十三号位置，则已达到目的，若十三号位置不是13，而是某个数字甲在第十三号位置上，则我们可以把13移到十四号位置上，把空格移到第十五号位置，又设在第十号位置上是某个数字乙，而在第十一号位置上是某个数字丙，如图 (2.10)所示。则可以按照安排4的方法（这里不过应该把那里的行列颠倒过来看），图（2.10)变成为图（2.11)，而图（2.11) 可变成为图（2.12)，再将图（2.12)变成图（2.13)，这时9和13都分别安排在第九和第十三号位置上去了。

接着又再按上述办法，我们还能把10，14也分别安排到第十和第十四位置上去。这时只剩下十一、十二、十五、十六这四个位置还没安排好，而在十五个纸板中就只剩下11、12、15这三块纸板还没有按照要求来安排。但无论情况如何，我们总可以把11移动到第十一号位置上去，而剩下的12、15这两块纸板可能出现下列两种情况。

如图（2.14)所示，其中12、15都恰好移动到第十二及第十五位置，这正是我们所要求达到的目的。但也可能出现第二种情况，如图（2.15）所示，这时12排在第十五号位置上，而15排在第十二号位置上，但图（2.16）可以变成为图（2.17)，图(2.17)可以变成为图（2.18)，而图（2.18)可以变成为图(2.19)，最后，我们还可以把图（2. 19)移动成为图（2.20) 的倩况，于是我们知道任给一个初始状态，而经过上面的一系列移动后，可以变为图（2.21)与图（2.22)两种顺序中的一种， 我们称图（2.21)的排列为“正常排列”,而称图（2.22)的排列为“奇异排列”。

应该说，作为一种游戏，我们讨论到此就算完了。但如果我们再问得深一点，例如我们问“奇异排列”能不能够重新移动而变成为“正常排列”？哪一种初始状态能变为“正常排列”而哪一种初始状况又能变为“奇异排列”？那就不能不借助于较多的数学方法了。为此，我们先来介绍组合数学中的几个定义。

 2 

有一堆东西，需要按照某种规定把它们排列出来。我们可以给每一个东西编一个号，例如按某种规定依次编为1，2，…，n，因而按某种规定把这一堆东西排好后，就得到一个从小到大的序列（1， 2，…，n)，我们称这个序列为顺序列，但若出现一个大的数排在小的数前面，例如（1，3，2，4，…，n），则这个序列就不是顺序列了，而是一个在顺序上发生杂乱的序列，我们不妨称之为非顺序列，在非顺序列中，由于发生杂乱的情况不同，而存在各种不同的非顺序列，为了说明这种杂乱的程度， 于是人为地规定了一些标准。在这里，为了满足我们的需要，于是我们规定这样一种标准：若在一个序列中，有一个数排在比它还要小的另一个数之前，我们称之为一个倒置。例如非顺序列 (1，3，2，4，5)有一个倒置，因为3排在2之前，而除这个倒置以外，再没有別的倒置了。又例如序列（3，1，2，4， 5)有两个倒置，因为3不仅在2之前，而且还排在1之前，除此之外再没有別的倒置了，但（3， 2，1，4， 5)却有三个倒置，因为3排在1和2的前面，这有两个倒置，2排在1的前面，这又有一个倒置，因而共有3个倒置。我们称顺序列的倒置数为0，这是因为顺序列没有发生倒置。根据倒置数的不同，我们便可以把所有的序列分成两类，一类是倒置数为偶数的序列，我们称它为偶置序列，当然由于0也可算为偶数，因而我们把顺序列归为偶置序列。另一类是倒置数为奇数的序列，我们称它们为奇置序列。

有了这些组合数学的概念之后，我们就可以来回答前面提出的问题了。设图(2.22*)是一个十五子游戏的初始位置。我们先把第一行的四个数从左到右排好，然后再把第二行的四个数从左到右排好后再接在第一行的四个数之后，再依次把第三行、第四行的数按照同样的方法接在第二行的四个数之后，但其中空格不给以排出。 这样我们便把这15个数排成为一个序列，（如图2.23所示），

下面我们将开始计算这个序列的倒置数。5排在最前面，因而有1，2， 3，4这四个比它小的数排在它后面了，所以仅仅对于5来讲，就有四个倒置。我们按照图（2.24)中的写法把4写在5的下面去；1排在第2个位置，虽然5排在它前面，但这一个倒置在计算5的倒置数时已经算过了，所以不再计算，而1的后面再也没有比1小的数了，因而1的倒置数是0。

我们在图（2.24) 中把0记在1的下面；同理，排在4的后面而又比4小的数有3和2两个，因而4的下面记上2；按这样的方法，3的下面记上1；10的下面记上5；8的下面记上3；2的下面记上0；13的下面记上5 ；6的下面记上0 ； 9的下面记上1；14的下面记上3；12的下面记上2； 7的下面记上0；15的下面记上1；11的下面记上0。于是图（2.24)的下面一行数的和就是图（2.23)中的序列的倒置数了，由于4+0+2+1+5+3+0+5+0+1+3+2+0+1+0=27是一个奇数，因而这是一个奇置序列（请注意！这时我们是把原问题中的空格抛开来计算的）。事实上，要判断其是奇置序列还是偶置序列，用不着把这些倒置数加起来，因为偶数加偶数还是偶数，而奇数加偶数还是奇数，这就是说，一个整数加上一个偶数并不会改变原来的这个整数的奇偶性。因此我们只需去数一下倒置数中有多少个奇数，若是偶数个奇数，则这个序列是一个偶置序列，因为偶数个奇数之和是一个偶数，再加上没有计算的那些偶数，仍然是一个偶数；若有奇数个奇数，则这个序列一定是一个奇置序列，因为奇数个奇数之和必然是一个奇数，再加上没有计算的那些偶数，也还是一个奇数。因此我们数一下图（2.24)的下面一行数中共有1，5，3， 5，1，3，1这7个奇数，故马上可断定图（2.23)的序列是一个奇置序列了。按照这种方法，我们对于十五子游戏中的任何一个初始位置，都能够较快地判定其是奇置序列还是偶置序列了。例如图（2.20）的“正常排列”的倒置数为0，因而是一个偶置序列，而图（2.21)的 “奇异排列”只有一个倒置，因而是奇置序列。

 3 

下面我们来研究一下，一个序列中相邻的两个数调换一下位置，倒置数会发生什么变化呢？例如一个序列中某一对相邻的两数为xy，当两数调换位置后，变为yx。若x大于y，则xy的顺序是不正常的，即有一个倒置，现在变为yx，即小的y在前，大的x在后，因而原来的一个倒置经过这一调换后消失了。若x小于y，则原来的位置是小的在前，大的在后，这两个数之间没有倒置，经过调换后，变为yx，大的在前，而小的在后，因而产生了一个倒置。因此，我们可以断言，两个相邻的数若调换位置后，就一定会产生一个新的倒置，或者一个原有的倒置消失了， 即倒置数的变化为土1。因而原序列倒置数的奇偶性发生了变化。 若有三个相邻的数为xyz，把x调到z的后面，变为yzx，这时候，我们可以把这样的调换划分为两步，先看为是x与y变换位置，再把x与z调换位置，变为yzx，即经过了两次相邻的调换， 因而原序列倒置数的奇偶性要发生两次变化，即奇→偶→奇，或者是偶→奇→偶。这样，一个数在序列里向前跳过两个数或者向后跳过两个数后，序列的奇偶性不变。若是四个相邻的数排成为xyzw，当x调到w之后，变为yzwx时，显然还可以把这个变换分成三个相邻的调换，即x先与y交换，再与z交换，最后与w交换，因而原序列倒置数的奇偶性也经过三次变换，即奇→偶→奇→偶，或者是偶→奇→偶→奇，故序列的奇偶性要改变。

在十五子游戏中，我们的变化不过是把空格向左右或向上下移动。当空格向左右移动时，原位置的序列没有发生变化。例如在某一行中，原来的位置是x□yz ，当空格向右移动时变为xy□z，当空格向左移动时变为□xyz，这两种情况的排列都是xyz，因而我们断言，当空格向左右移动时，原序列的倒置数不变，所以倒置数的奇偶性也不会发生变化。当空格向上移动时，例如由图（2 .25)变为图（2.26)。

因为图（2.25)展开的序列为* * xyzw *，而图（2.26)展幵的序列为* * yzwx * ，即x向后跳了三个位置，因而按前面的分析，序列的奇偶性要改变了。同理，当空格往下移动一格时，即由图（2.26)变为图（2.25)时，序列的奇偶性也要改变。而当空格向上移动一格后，又向右或者向左移动时，最后又向下移动到空格原来所在的行时，则序列倒置数的奇偶性变化了两次，因而知道序列的倒置数的奇偶性不变。若空格向上或者向下移动两格，则序列倒置数的奇偶性也变化了两次，结果倒置数的奇偶性仍然不改变。但若空格向上或者向下移动三格，则奇偶性就要改变了。在十五子游戏中，最后结果空格是在第四行，因而若空格原位置在第四行或第二行，则到最后位置（即图（2.20)或图（2.21))时，序列的奇偶性不会改变，若空格原来的位置是在第一行或第三行时，则最后位置的序列倒置数的奇偶性要发生变化。我们在前面已经讲过，不论十五子游戏的最初位置如何，最终总可以变为图 (2.20)的“正常排列”（偶置序列）或图（2.21)的“奇异排列”（奇置序列）。

因此，当原位置的序列是偶置序列，而空格在第一行或第三行时，它只能变为“奇异排列”；若此时空格在第二行或第四行，则它一定可以变为“正常排列”。当原位置的序列是奇置序列，而空格在第一行或第三行时，则最终总可以变成为“正常排列”；当空格在第二行或第四行时，它就只能变为“奇异排列”了。而“正常排列”与“奇异排列”的空格都在第四行，因此“正常排列”（偶置序列）再经过任何移动也不可能变为“奇异排列”（奇置序列）了。讨论到此，我们就完全掌握了十五子游戏的奥秘了，因为我们不但能把它排成最终状况，而且能预先就知道它能不能排成“正常排列”，这只须简单计算一下序列倒置数的奇偶性，并看一下空格在第几行就行了。 就这样，我们仅仅使用了一点点数学概念，就把神秘的十五子游戏变成为十分简单明了的事实，当然与此同时，有趣的游戏也就枯燥无味了，数学之有用再一次得到了证明，它使我们领略了探索奥秘的兴奋。

 4 

事实上，十五子游戏并不仅仅限于十六个小方格和十五块小纸板，任何n²个小方格组成一个纵横数相同的方形棋盘和n²-1个小纸板都可以玩“n²-1子游戏”。例如纵横各五的二十五个小方格和二十四个小纸板我们一样能玩“二十四子游戏”，与十五子游戏一样，可以总结出其规律，并且规律更简单一些，即偶置序列可以排成“正常排列”，奇置序列只能排成“奇异排列”， 而不必去看空格在哪一行。这又是为什么呢？我们再来研究一下，当空格左右移动时，与十五子游戏一样，序列的奇偶性不变。

而当空格上下移动时，例如从图（2.27)变成图（2.28) 时。序列由* * xyzwu * *变为* * yzwux * * ，即x向后跳动了四次，因而序列的奇偶性也要变动四次，即奇→偶→奇→偶→奇，或由偶→奇→偶→奇→偶，因而奇置序列仍变为奇置序列， 偶置序列也仍然变为偶置序列，即空格上下移动都不改变序列的奇偶性，所以偶置序列变为“正常排列”（偶置序列），而奇置序列只能变为“奇异排列”（奇置序列）了。