回忆经典，讲述滑块游戏背后的数学故事 _小知识

华容道作为80后和部分90一代的启蒙玩具，其经典度和怀旧感不逊李雷和韩梅梅。

文章插图
它号称“古老的中国游戏，与七巧板、九连环等中国传统益智玩具一起是中国难题的代表作” 。实际上，据死理性派考据，华容道其实可不是什么传统中国游戏，它由英国人弗莱明发明，在上世纪30年代传入中国，是重排九宫的简化版。
重排九宫，又称八数字推盘（8-puzzle），是和华容道一样的滑块游戏（sliding puzzle）。今天死理性派就来讲述这个流行全球的游戏背后的数学故事。

文章插图
所有的重排九宫都可解吗？
在一个带框的木板上放入标有1到8的八个方块，在有限的空间内，怎样让这八个方块各归其位呢？最简单的做法当然是把方块都倒出来，然后放回去。当然这样有些无厘头，而且没有技术含量。不过如果真的把八块方块全倒出来再乱放回去，这样的8-puzzle还一定能重新复原吗？恐怕一些人早就听说过，对一个任意乱排的8-puzzle只有一半的可能性能够解开。有的人凭数学直觉可能就说了，这恐怕是奇偶性的问题吧。没错，当面对一个任意状态的8-puzzle时,我们可以根据其方块的排列方式算出一个整数，凭这个数的奇偶性就能断言8-puzzle可不可解。
而如何计算出这个数呢？这就要把方块排列方式“化归”到一个抽象的数学对象上，这样一来游戏规则（每步所允许的走法）就“化归”成了这个数学对象的某个属性，比如说奇偶不变性。所谓“化归” ，是指在解决问题的过程中，数学家往往不是直接解决问题，而是对问题进行变形、转化，直到把它化归为某个（些）已解决，或容易解决的问题。
【回忆经典，讲述滑块游戏背后的数学故事】关于“化归法”有这样一个生动的解释，假设你能够用一个空水壶烧一壶热水。那如果所有条件不变，只是水壶中已有足够的水，该怎么办呢？通常人们会去进行下一个步骤。而数学家不这样，他们会倒去壶中的水，并且声称他们已经把这个问题化归成先前面已解决的的问题了。这虽是一个略带揶揄味道的笑话，不过至少说出了化归的基本特征。

文章插图
注定无人能拿下的1000刀
前面已经说过， 8-puzzle的各种可能的初始排法里面，只有一半的排列方式能被解开。19世纪90年代，自称是15-puzzle（即8-puzzle的4×4扩展版）的发明人的Sam Loyd 曾悬赏1000美金，征求能仅仅把14和15交换的方法，这也就是著名的重排十五问题。一千美金在当时非常吸引人，导致很多人不务正业成了“赏金猎人” 。但是很遗憾，谁也没有拿走这它，或者可以这样说，其实谁也拿不走这一千美金。

文章插图