回忆经典,讲述滑块游戏背后的数学故事

  数学

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

/gkimage/ht/rw/tm/htrwtm.png

它号称“古老的中国游戏,与七巧板、九连环等中国传统益智玩具一起是中国难题的代表作”。实际上,据死理性派考据,华容道其实可不是什么传统中国游戏,它由英国人弗莱明发明,在上世纪30年代传入中国,是重排九宫的简化版。

重排九宫,又称八数字推盘(8-puzzle),是和华容道一样的滑块游戏(sliding puzzle)。今天死理性派就来讲述这个流行全球的游戏背后的数学故事。

/gkimage/3m/iq/fd/3miqfd.png

所有的重排九宫都可解吗?

在一个带框的木板上放入标有1到8的八个方块,在有限的空间内,怎样让这八个方块各归其位呢?最简单的做法当然是把方块都倒出来,然后放回去。当然这样有些无厘头,而且没有技术含量。不过如果真的把八块方块全倒出来再乱放回去,这样的8-puzzle还一定能重新复原吗?恐怕一些人早就听说过,对一个任意乱排的8-puzzle只有一半的可能性能够解开。有的人凭数学直觉可能就说了,这恐怕是奇偶性的问题吧。没错,当面对一个任意状态的8-puzzle时,我们可以根据其方块的排列方式算出一个整数,凭这个数的奇偶性就能断言8-puzzle可不可解。

而如何计算出这个数呢?这就要把方块排列方式“化归”到一个抽象的数学对象上,这样一来游戏规则(每步所允许的走法)就“化归”成了这个数学对象的某个属性,比如说奇偶不变性。所谓“化归”,是指在解决问题的过程中,数学家往往不是直接解决问题,而是对问题进行变形、转化,直到把它化归为某个(些)已解决,或容易解决的问题。

关于“化归法”有这样一个生动的解释,假设你能够用一个空水壶烧一壶热水。那如果所有条件不变,只是水壶中已有足够的水,该怎么办呢?通常人们会去进行下一个步骤。而数学家不这样,他们会倒去壶中的水,并且声称他们已经把这个问题化归成先前面已解决的的问题了。这虽是一个略带揶揄味道的笑话,不过至少说出了化归的基本特征。

/gkimage/6x/om/2x/6xom2x.png

注定无人能拿下的1000刀

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

/gkimage/tj/29/u0/tj29u0.png

滑块游戏可解性分析

其实早在1879年,Johnson 和 Story 两位数学家就证明了“重排十五”是不可解的。而他们使用的方法正是计算前文提到的那个整数——方块初始排列状态的逆序数。如果用数字9标识空白位置 ,那么下面这种情况方块的排序状态就可以记作 [2 3 1 4 5 6 7 8 9]。

/gkimage/z0/st/57/z0st57.png

容易看出[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 a i+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)构成一个矩形时,三个方格的位置就可通过简单的操作任意互换,如图所示。

/gkimage/qp/ox/gl/qpoxgl.png

而8-puzzle里任何三个字块只要能组成一个三角形,它们的位置都可以互换,因为空白方格总是可以先移动到指定位置与这个三角形构成矩形,在执行完互换后再原路返回,而其他格子的位置不会有变。比如我们现在要轮换abe三个方块之间的位置:

/gkimage/f1/ak/dp/f1akdp.png

这样一来,问题就化归为如何用这种三角形轮换来把8-puzzle解开了,这恐怕就不是什么难题了。

LEAVE A COMMENT

This site uses Akismet to reduce spam. Learn how your comment data is processed.