下载掌阅APP，畅读海量书库
立即打开
数字华容道又名重排十五，是一个流传已久的单人智力游戏。这款游戏有两个基本问题：一是如何去解，二是是否一定有解。
这个游戏的主流玩法是降阶法（如图1-3所示），先还原1,2,3,4,5,9,13这7枚棋子，把它们分别安置在第一行和第一列上。
图1-3
第二步是把6,7,8,10,14这5枚棋子安置在第二行和第二列的自然顺序位置上（如图1-4所示）。
图1-4
现在，只剩下11,12,15这3枚棋子和右下角的1个空格了。这时会出现两种情况，一是11,12,15顺时针排列（不管空格在何处），二是11,12,15逆时针排列（也不管空格在何处）。如果是第一种情况，那么最多再走两步就可以到达终局了，如图1-5所示。如果是第二种情况，则对不起，你摊上大事了！即使你让临近的10、14两枚棋子一起参与进来，想尽法子，到何年何月也不可能达到终局。
图1-5
下面用数学方法回答：重排十五什么时候是可解的，什么时候是不可解的。先看下面几个定义。
定义1：由1,2,…,n组成的一个有序数组称为一个n级排列。
例如，2431是一个四级排列，45321是一个五级排列。
定义2：在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。
例如2431中，21,43,41,31是逆序，2431的逆序数就是4；类似地，45321的逆序数是9。
定义3：逆序数为奇数的排列称为奇排列，相应地，逆序数为偶数的排列称为偶排列。
显然，任一排列都只有这两种可能。
现在回到重排十五上来，15枚棋子放在16个空格中。按从左到右、从上到下的顺序（空格不计）排成一列，因此也构成了一个排列，如图1-6所示的初局。如果写成排列的话就是
横线以下是对应数字的逆序数。例如7，在此排列中有3,2,1,5,4,6这6个数比它小，所以7的逆序数是6；又如5，在它之后仅有4比它小，所以5的逆序数就是1，以此类推。在判断这个排列是哪一类排列时，不必把这15个逆序数加起来，只需数一数有多少个奇数就可以了。在本例中，共有7个奇逆序数，所以它是一个奇排列。
图1-6
以下我们要研究棋子的移动对于排列种类的影响。棋子左右移动，排列的奇偶性不受影响；而上下移动的话，奇偶性将要发生变化。如图1-7所示，棋子丁向上面的空格移动，则由原来的排列“×甲乙丙丁××”变成了排列“×丁甲乙丙××”，也就是说丁跳过甲乙丙而成了新的排列。由此所导致的排列种类的变化很容易看出来，因为丁一次性跳过甲乙丙可以看作先跳过丙、再跳过乙、最后跳过甲的三级跳。每跳一次，就有一个新的逆序产生，或一个旧的逆序消失。无论是哪种情况，每跳动一次的结果总是逆序数加1或减1。即跳动1次，排列的奇偶性变动一次；跳动3次，排列的奇偶性也连变3次。总结起来就是，一个棋子向上移动时，排列的奇偶性发生变化；反之，一个棋子向下移动时，奇偶性当然也要发生变化。
图1-7
现在假定游戏开始了，空格的位置在开始时照例放在棋盘的右下角。不管棋子移动多少次，空格的位置依旧在右下角才有可能达到终局。这样空格上移的次数必定与下移的次数相同，因此排列的奇偶性一定经过偶数次的变化，所以移动开始时初始排列的奇偶性必与其移动终了后的奇偶性是一样的。换言之，偶排列仍回到偶排列，而奇排列仍回到奇排列。但我们终局的要求是1,2,3,4,…,14,15的排列，逆序数为0，是个偶排列，这样我们就得到了一个重要结论：
初始开局是奇排列的重排十五一定无解，只有初始开局是偶排列的，才能有完美的终局。
在随机放置15枚棋子时，有多少情况是无解的呢？在一个n级排列中，排列总数是n！设全部的n级排列中有s个奇排列，t个偶排列。现将s个奇排列中的前两个数对换，得到s个不同的偶排列，因此s≤t。同样可证t≤s，于是s=t，即奇、偶排列的总数相等，各有n！/2个。所以，若15枚棋子随机放置的话，就可能有一半是无解的。
任何游戏之所以有趣，是因为无数次摸索尝试后，突然成功的那一刻的兴奋。现在，通过数学上的排列论，可以事先预测其结果，于是一个有趣的游戏变得兴味索然了。有人说这是数学的缺点，但换个角度看，这正是数学的伟大。数学大的功用在于解释宇宙的奥秘，发掘真理，最后使得人类能充分利用这千变万化的宇宙现象；小的妙处就像我们可以用排列组合解决重排十五的问题一样。
最后有一点要声明：游戏终局时，空格的位置必须与初始状态一样在右下角，否则以上讨论的问题就完全改变了。