“14～15”游戏

历史上曾发生过一段有趣的故事。美国科学魔术师萨姆·洛伊德在1878年推出了一款著名的“14～15”智力玩具，这个游戏迅速风靡欧美大陆。在德国的马路上、工厂里、皇宫中、国会大厦，到处都有人在如痴如醉地玩这个游戏，以致许多工厂老板不得不出示公告，禁止人们在上班时玩游戏，否则开除！在法国，从比利牛斯山脉到诺曼底半岛的小山村和巴黎的林荫大道，也是处处可见玩这个游戏的人群。这个玩具在出售时的初始布局如图1-8所示，玩具的制作者洛伊德承诺，谁能够通过滑动其中的数块使错位的14和15换成正常次序，谁就能获得1000美元的奖金。1000美元可不是一个小数目，自然会引起轰动。事实上，这是永远无法达到的，只是洛伊德的一个“诡计”，因为这正是一个奇排列。

图1-8

但从图1-8所示的初始布局，还是可以得到一些有趣的终局。如图1-9所示，即把数字1～15的次序理顺，但空格不在右下角，而在左上角。目前已知这个玩法的最少步数是44步，如下所示：

14,11,12,8,7；6,10,12,8,7；4,3,6,4,7；14,11,15,13,9；12,8,4,10,8；4,14,11,15,13；9,12,4,8,5；4,8,9,13,14；10,6,2,1。

图1-9