8.风靡世界的棋子

装有15个方形棋子的小匣子看上去似乎很普通，但几乎所有的玩家都能对你历数它曾经的辉煌，作为一种令人着迷的数学游戏，它曾在很多国家风靡一时。

德国游戏研究者、数学家弗·阿伦斯曾对这段历史做过描述：“15个方形棋子游戏出现于19世纪70年代的美国，无数的游戏玩家为它痴迷，它的流行速度之快，令整个社会震惊，甚至成为社会的灾难。”

这场“灾难”同样席卷了位于大洋另一边的欧洲。即使是乘坐铁轨马车的乘客，手里都拿着装有15个棋子的小木匣。商店里、事务所中，老板们面对沉迷于游戏中的职员几乎无计可施，最后不得不在制度中增加禁止游戏的条款。这场流行游戏的赢家是娱乐业的老板们，他们举办了各种大规模的15个棋子游戏比赛，获得了巨大的收益。

在德国，即使是庄重的国会大厅，也成了15个棋子的游戏场。回忆起这段历史，曾亲身经历过那一时期的前国会议员——著名的地理学家、数学家西格蒙德·京特说：“国会大厅中那些捧着小木匣全神贯注游戏着的白发老人就像是坐在了我的眼前。”

巴黎的露天场、林荫道上，处处都是15棋子游戏的“天堂”，它甚至以迅雷不及掩耳之势从巴黎流行到整个法国。有一位法国的作家曾经这样描述那时的场景：“即使是乡间随便的一座孤零零的小屋，都有这种蜘蛛正在筑巢，它们正致力于密切关注那些随时会陷入蛛网的牺牲品们。”

人们对15个棋子的狂热程度在1880年达到顶峰。不久之后，数学的武器成功将其征服，它的游戏价值被很快推翻了。研究人员利用数学理论对人们提供的大量题目一一进行攻克，最后发现，有一半的题目是根本无解的。这使所有每天致力于求解的游戏迷们恍然大悟，他们终于知道为什么再怎样坚持不懈都无法解出某些难题，为什么那些娱乐业的老板们举办大赛的时候敢设立巨额奖金。在这一点上，游戏的发明者比任何人都底气十足。他甚至向纽约报提出给星期天副刊提供一道尚未有解的难题，并自掏腰包拿出1 000美元征求答案。这位发明者的名字是萨穆埃利（塞姆）·洛伊德，他编撰过很多谜语和有趣的题目，颇受大众追捧。但他所发明的15个棋子游戏却根本没有在美国成功申请到专利证书，因为他在提交题目的同时，还必须按照规定提交一套破解该题目的“工作模型”。他当然不可能提交，因为他的题目根本无法用数学方法解答出来，于是他被拒绝了。专利局的工作人员对他说：“没有解，就不可能有工作模型，没有工作模型，我们无法为你签发专利证书。”洛伊德接受了这个决定，没有做更多争取。不过如果他当时能够预见15个棋子游戏的火爆程度，也许会为专利证书再努力一下的。

萨穆埃利（塞姆）·洛伊德对这一游戏的历史这样写道：“智慧王国的老住户们应该不会忘记，我是如何在70年代初让全世界的人都为一个装有15个棋子的小木匣子绞尽脑汁的。”几乎没有人不知道15个棋子游戏（图10）的小木匣，就像书中插图（图11）所显示的那样，标有数字的15个棋子正常排列在正方形的小木匣子里，只有14和15这两颗棋子的顺序是颠倒的。要求就是依次移动棋子，让它们完全正常排列，确切地说，14和15的位置要互换回来。

所有人，包括可敬的官员们，都在没日没夜地解这道题，但始终没有一个正确破解它的人出现，那笔为胜利者提供的1 000美元奖金也就成了摆设。

很多商人因为全神贯注地解题甚至忘记关闭店门，可敬的官员们为了找到答案，整夜地站在路灯下求解（图12）。但没有谁放弃这种努力，因为他们都对即将到来的“胜利”满怀憧憬与信心。因此一些令人遗憾的事就发生了，比如领航员将船开上了浅滩，火车司机在经过站台时忘记停车，种田人把手中的犁抛在了田边……

**********

了解了15个棋子游戏的历史，我们再来了解一下这个游戏本身。这是一个包含着复杂数学理论知识的游戏，它与高等代数中的“行列式理论”密不可分。我们前面提到过的德国游戏研究者、数学家弗·阿伦斯表达了下面的一些观点：

15个棋子游戏要求人们，无论15个棋子最初以什么顺序排列，利用木匣中仅有的一个空格，依次移动棋子，把它们的顺序调整到正常的状态，即左上角为1，它的右边是2和3，右上角是4；第二排从左至右分别是5、6、7、8，然后是第三排、第四排。（见图10）

假设小木匣中的15个棋子以杂乱无章的顺序排列其中，我们通过一系列的移动，总是可以将1号棋子移动到左上角的位置。接下来在不移动1的前提下，也可以将2移动至它的右侧。保持1和2不动，3与4也能很快排列其后，就算它们都不在最后两条垂直的线上，也很容易调整至正确的位置。第一行已经完成，用同样的方法，我们可以将第二行的5、6、7、8移动到位，这是一定可以做到的。最后的两行，我们先将9和13调整到行首的位置上。目前所有已经到位的棋子——1、2、3、4、5、6、7、8、9、13，必须待在原地，不能再被移动了。那么剩下的6个格子中，包括棋子10、11、12、14、15和一个空格，在这个有限的范围中，要先将10、11、12移动到正确的位置，这时第三行就完成了。那么位于第四行的14和15，或者按顺序依次排在13的右侧，或者二者顺序颠倒（图11）。

上述的方法非常简单，读者很容易进行实践检验，根据这一过程，我们得出以下的结论：

游戏中15个棋子的任何一种排列都能被调整到图10或者图11所示的状态。

假设某一种排列——我们暂用字母S来表示——能转换成另外一种不同的排列，那么它一定可以再转换回原来的状态，因为棋子所走的任何一步都是可以还原的。比如将棋子12移动一步，立刻又可以将它反向移动还原回去。

这使我们得到了两种系列的排列：第一系列中的排列全部可以调整至正常顺序的排列，第二系列中的排列全部可以调整为不同的排列。反过来讲，由正常顺序的排列可以得到第一系列中的任何一种排列，由各种不同的排列能够得到第二系列中的任何一种排列。也就是说，同一系列中的任何两种排列都是能够相互转化的。

那么，如果继续下去，我们能否将这两个系列中的排列合并呢？答案非常明确：不能。这里我们必须省略掉详细的证明过程，但结论是严肃的，无论经历多么复杂的移动，这两种排列也是不可能相互转化的。

因此我们有必要明确地将游戏中15个棋子的排列方式划分为两个互不关联的系列：第一系列是能被调整至正常排序状态的排列，即可破解的排列；第二系列是能被调整为其他的排列，但在任何情况下都不可能被调整至正常排序状态的排列，这就是那些无解的排列，也就是被用来重金求解的排列。

怎样确定某一排列属于哪一系列？我们来举一个例子说明：

第一行的棋子排列正常，第二行的前几个棋子也一样，但最后位置上的棋子除外。排在第二行最后位置的原本应该是8，但现在却是9，而8却被排在了下面的区域中，我们把这种排列上的位置前移称为“无序”。换句话说，棋子9这里出现了1个无序的位置。再看下面的两行，11、12、13、14这四个棋子的排列是14、12、13、11。也就是说，棋子14排在了12、13、11前面，棋子12排在了11前面，棋子13排在了11前面。由此可知，棋子14出现了3个无序。棋子12和棋子13分别出现了1个无序。现在我们总计有1+3+1+1=6个无序。

小木匣一共有16个位置，提前将第四行最后一格空出来，方便我们用这种方法确定所有的无序之和。如果这个和是偶数，就像我们前面例子中求得的总无序数是偶数6，那么这个排列属于第一系列，是有解排列，可以被调整为正常顺序的排列。如果这个和是奇数，这个排列就属于第二系列，是无解排列，不能被调整为正常顺序的数列。特别需要说明的是，当总无序数为0时，按偶数计。

数学理论的成功介入揭开了这个游戏的神秘面纱，也使我们对它曾经引起的轰动感到不可思议。数学创立的游戏理论是严谨、详尽的，不存在任何疑点。15个棋子游戏的成功破解并非依靠偶尔的运气或一时的机智，像其他所有游戏一样，破解它的唯一依据是纯粹的数学事实，其结论的权威性是毋庸置疑的。

我很愿意为读者朋友们提供几道同一领域的难题。下面的题目都是有解的，编写它们的人正是萨穆埃利（塞姆）·洛伊德。