讲述滑块游戏背后的数学故事（必学）

华容道作为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交换的方法，这也就是著名的重排十五问题。一千美金在当时非常吸引人，导致很多人不务正业成了“赏金猎人”。但是很遗憾，谁也没有拿走这它，或者可以这样说，其实谁也拿不走这一千美金。 滑块游戏可解性分析 其实早在1879年，Johnson 和 Story 两位数学家就证明了“重排十五”是不可解的。而他们使用的方法正是计算前文提到的那个整数——方块初始排列状态的逆 序数。如果用数字9标识空白位置 ，那么下面这种情况方块的排序状态就可以记作 [2 3 1 4 5 6 7 8 9]。 容易看出[2,1]，[3,1]是逆序的，即这里α=2（注意始终9表示空白方块，实际是不存在的，所以不在考察范围内）。逆序数在这里的实际意义是，如果上述这个状态的puzzle要回到自然状态[1 2 3 4 5 6 7 8 9],则需交换第二格和第三格，再交换第一格和第二格，共计步数为2。根据逆序数的奇偶性，Johnson 和 Story把方块的排列状态分为偶状态和奇状态。自然你也可以多余的随便交换别的两格再交换回来（在实际游戏过程中你确实可能出现这样的反复操作），不过我们只关心α的奇偶性。而奇妙之处正在于，遵循游戏规则的移动方式不可能改变方块排列状态的奇偶性！因为数字左右移动时状态对应的数列没有变化，故逆序数不变；而当数字从上往下（或者从下往上）移动时，例如方块 a i 下移时，相当于往后挪动了三个位置，即[ a 1 … a i ai+1 a i+2 … a 8 ]→[a 1 … a i+1 a i+2 a i … a 8 ]，实际上就是 a i 与 a i+1 ， a i 与 a i+2 依次进行邻换（数列中相邻两个数码相互交换），根据代数中的定理可知，一个数列经过偶数次的邻换，产生的新数列与原数列的逆序数奇偶性相同。因此重排九宫中，方块的移动不会改变其逆序数的奇偶性。说到这里问题就变得明了了，通过判断初始状态与目标状态的α值就能判定这个puzzle是否可解。而这个结论则可以推广到任意m×n型的滑块游戏中去。 回到重排十五问题，这个puzzle的初始状态[1 2 3 4 5 6 7 8 9 10 11 12 13 15 14 16]的逆序数是1（[15 14]）,与目标状态[1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16]的逆序数α=0奇偶性不同，所以必然不可解。 8-puzzle的操作攻略 前面已经细述如何判断任意状态的滑块游戏的可解性。那当面对一个的确可解的重排九宫时，又怎样移动方块，排列出目标状态呢？ 这里提供一个三角轮换法则。仍用9代表空白方格，当它和三个方格（比如abc）构成一个矩形时，三个方格的位置就可通过简单的操作任意互换，如图所示。 而8-puzzle里任何三个字块只要能组成一个三角形，它们的位置都可以互换，因为空白方格总是可以先移动到指定位置与这个三角形构成矩形，在执行完互换后再原路返回，而其他格子的位置不会有变。比如我们现在要轮换abe三个方块之间的位置： 这样一来，问题就化归为如何用这种三角形轮换来把8-puzzle解开了，这恐怕就不是什么难题了。