揭开“十五子棋”的奥秘

有一种图形还原游戏，叫“十五子棋”：在有 16 个方格的盒子里，装着

15 块标有从 1 到 15 的数字的小方块，并留有一个空档。开始时，小方块是按随意的顺序放进盒子里的。游戏的要求是：有效地利用空格，调动小方块， 使盒子小方块的数字还原到下图的正常位置。这样做可能吗？

这是一个相当简单的游戏，几乎人人一看就会明白。然而有时我们能够轻易取得成功，但有时无论我们如何努力，却无法取得成功！那么奥妙究竟在哪里呢？

可能读者都已注意到，空格是能够移动到盒子的任何位置的。我们也很容易利用空格把方块 1、2、3 依次调动到各自正常的位置上去。不过，当这三个棋子安顿好之后，想不动方块 3 而把方块 4 也移到正常位置上，却似乎有些为难。然而，用下图的办法我们却能实际上做到这一点。这里要动到的只是一块 2×3 方格的区域；而且很显然，只要有一块 2×3 的方格区域，就

一定能够做到这一点！方块 3 虽然动了一下，但后来又恢复到原先的位置。现在方块 1、2、3、4 已经在正常的位置上。接下去方块 5、6、7、8 也

可以同样恢复到正常位置。再接下去我们还可以把方块 9 和 13 移到各自正常

的位置上。此时我们仍有 2×3 方格的地盘，正如前面说过的那样，在这一区

域，我们依然可以把方块 10 和 14 各自安顿在正常的位置上。

至此，我们已经安顿好了 12 个方块，它们都已安在各自正常的位置上。剩下的位置是三个方块 11、12、15 和一个空格。我们还容易把 11 移到自己的位置，而把空格移至盒子的右下角。这时可能出现两种形式：

第一种是图（Ⅰ）的形式，此时所有的方块都已在正常的位置上，这表明我们已经取得了成功。第二种是图（Ⅱ）的形式。现在的问题是：图（Ⅲ） 的形式还能不能通过移动变为图（Ⅰ）的形式呢？

答案是否定的！

事实上我们可以把所有盒子里的方块看成一个数的顺列，而把空格当成数 16。这样，图（Ⅰ）的顺列为：

1，2，3，4，5，6，7，8，9，10，11，12，13，14，15，16。而 图 （Ⅱ） 的 顺 列 则 为 ： 1，2，3，4，5，6，7，8，9，10，11，15，13，14，12，16。

现在读者看到：图（Ⅱ）的顺列与图（Ⅰ）正常的顺列相比，其中有些数字的位置被打乱了，有些大的数跑到小的数的前面去，这种现象我们称为“逆序”。逆序可以采用点数的办法算出来。例如图（Ⅱ）的顺列，前 11

个数都没有出现逆序，而后面的 5 个数为： 15，13，14，12，16。

其中 15 跑到 13、14、12 这三个较小数的前面，因而出现了三个逆序； 而 13，14 跑到 12 的前面，这里又出现了两个逆序。此外再也没有其它逆序了。因此图（Ⅱ）的顺列共有 5 个逆序。

稍微认真分析一下，读者便会发现：在“十五子棋”中，方块和空格的移动，都不会引起原先顺列逆序的奇偶性的改变！由于图（Ⅰ）的顺列为偶逆序，而图（Ⅱ）的顺列为奇逆序，因而（Ⅱ）的形式是不可能通过方块棋子的移动变为图（Ⅰ）形式的。这就是为什么“十五子棋”有时能够成功， 而有时不能成功的道理！