15puzzle(15谜)可解性背后的数学原理

15puzzle玩法简介

15puzzle,也叫做15谜,15游戏。它的初始状态是由1到15共15个数字以及一个“空白”(以下简称“#”)排列在4*4的方格上,其中数字任意排列在前15个方格上,而“#”在最后一个方格上。玩家可以选择“空”上下左右四个方向的数字,并让这个数字与“空”交换位置。

所谓复原,指的是当这个4*4的方格从左到右,从上到下依次为1~15这15个数字加上一个最后面的”#“,这时候玩家胜利。

这儿有个可以正常访问的在线15puzzle游戏

15puzzle历史

15puzzle最早由美国纽约的一名邮差在1874年提出。1914年,一个叫Sam loyd的人出版了一本叫《Cyclopedia of Puzzles》的书,提出了14-15问题,即把已经完成的15puzzle中的14和15数字调换位置,其它的保持不变,就如下面这样。Sam loyd愿意把高达1000美刀的奖金送给能成功复原14-15问题的人。

你有办法把这个复原吗?更加一般化来说,给你任意一个15puzzle谜题,能保证有办法把它复原吗?如果不能保证,判断依据有时什么?

可解性分析

移动次数居然是偶数

首先我们发现,“#”在初始打乱状态处在第16个方格,在完全复原后仍然处在第16个空格。这说明,如果我们把“#”左移了u次,那一定也把“#”右移了u次,如果我们把“#”上移了r次,那一定也把“#”下移了r次。上移的次数和下移次数相等,左移次数和右移次数相等,才能让“#”回到原来的位置,也就是说,“#”被移动了偶数次,答案的移动步数应该是偶数。

置换什么的

仅知道移动次数是偶数还是不够的。接下来我们将要讨论交换格子,推数字这类的游戏中一般的规律。

假设我们有1~4共4个数字,这4个数字组成了一个有序集合X_1 = {1,2,3,4}。然后定义交换的方法,把这个集合中的数字换成同一个集合中另一个数字,既不重复也不遗漏。

其中方法y的意思是,把原集合中的1换成2,把2换成3,依次类推,得到的新集合为X_2 = {2,1,4,3}

这儿的方法叫做“置换”,不过名字并不是我们纠结的重点。 我们发现,诶,置换y实际上是把1和2对调了位置,把3和4也对调了位置,而1,2和3,4之间居然互不影响,真是奇了怪了,不如把独立的交换叫做循环吧。(1,2)是一个循环,(3,4)是另外一个。于是置换y记作

    \[  y = (1\ 2)(3\ 4)  \]

方法z同理,记作:

    \[ z = (1\ 2\ 3\ 4) \]

假设集合X_1中元素的个数为n,某置换的循环的个数是t,若n-t为偶数,那么这个置换就是偶置换,否则是奇置换。嗯,y是偶置换,z是奇置换。

1000刀的奖金花落谁家?

再次回到移动次数分析。其实每次移动,就是交换了两个元素而其它元素不变,就是一次置换啊,例如把第16个位置上的#与第十五个位置上的“6”交换,我们可以记作(6\ #)。

之前已经说过,为了游戏胜利,我们要移动偶数次,移动过程互不影响,那么也就是偶数次循环。诶,偶数次循环,我们的集合中元素个数为16,也是偶数个,偶数减偶数还是偶数,这不就是证明我们要找的答案,也是偶置换吗?

这下,我们可以说,如果一个15puzzle的游戏(初始“#”在第16个格子)有解,那么它的解法一定是偶置换,如果分析出要把某个15puzzle的解法是奇置换的话,那么它一定是不可解的。

回到sam loyd的那个14-15问题。如果我们要把它复原,必须只进行一次置换,也就是只交换(14,15),这是奇置换。但是为了让“#”号在复原后仍然在第16个格子,我们必须移动偶数步,来个偶置换。奇偶不可兼得,那1000块奖金自然是谁也别想拿到了。

头图那个例子

我们再用不容置疑的置换的眼光,看看15puzzle的解法究竟是怎样的。以头图为例,按从左到右,从上到下的顺序,解法其实就是下面一个置换y:

我们要做的,就是把上面一行的初始混乱状态,置换为下面一行的有序胜利状态。虽然这个置换y不符合游戏规则,但我们可以把它改得符合游戏规则啊!不过现在先不急。

看看置换y,我们可以记作

    \[ y = (1\ 5\ 6\ 15\ 4\ 7\ 11\ 3)(2)(12\ 8\ 14\ 10)(\#) \]

先解释一下,(2)的意思就是2和2交换,当然就是保持原样了。
(12 8 14 10)的意思是,12到8的位置,8到14的位置,14到10的位置,10到12的位置。解释完毕。

我们惊讶的发现,要使头图的例子复原,也得弄4个循环,16-4 = 12,也就是偶置换。答案要求的也是偶置换,诶是不是说明了什么?头图的例子很有被解开的前途啊。

不过等等,答案要求的解法,每次只能交换2个元素。而置换y一下交换好几个,违反规则了啊。正如之前所说,我们可以把它改成每次只交换两个元素的啊。

再悄悄定义一下

我们很快就要解决15puzzle啦!我们把刚才说得奇偶置换重新解释一下。

在集合S_n中,有一置换a内有t个循环,则sgn定义为

    \[ sgn(a) = (-1)^{n-t} \]

嗯,那么当sgn(a) = 1的时候,a就是偶置换,当sgn(a) = -1的时候,a就是奇置换。 然后是一个定理对集合S_n上的两个置换a和b,我们有分解的方式:

    \[ sgn(ab) = sgn(a)sgn(b) \]

再假设τ是一个“对换”,即只交换两个元素的置换,例如之前说到的(6\ #),就是对换。 那么

    \[ sgn(τa) = -sgn(a) \]

这个也很容易理解,这时我们就可以说,偶置换就是可以分解成偶数个对换的乘积,奇置换就是可以分解成奇数个对换的乘积。偶置换多加一个循环就是奇置换,奇置换多加一个循环就是偶置换。当然,每个对换也是奇置换。

祭出最后一个推理:

游戏规则规定答案必须是对换,也就是一次交换两个元素。之前我们证明了答案的的步数是偶数,当然就是偶数个对换,那么,我们只要证明,在头图的例子中,作为偶置换的置换y,分解成对换后也是偶数个对换不就行了嘛?

设置换a可以分解成q个对换τ_1...τ_q,那么

    \[ sgn(a) = sgn(τ_1)...sgn(τ_q) = (-1)^q \]

a是偶置换,那么sgn(a) = 1,即q是偶数。因为每个对换都是奇置换,所以偶数的奇置换就当然偶置换啦,也就说,偶置换分解成对换后,就是是偶数个对换的积。

你知道我要说什么了吧?

那么,对于标题的问题来说,答案就撂这儿了:

设初始位置上,第1到15格分别是变量a_1,a_2..a_15,第16格为“空白”,记作“#”。

为了让数字复原,必须进行的下面这个置换

如果为偶置换,那么这个15puzzle是可解的。如果是奇置换,不好意思,一边凉快去吧。

结语

如果你能看到这儿,恭喜你,抽象代数的内容你已经了解一点了。除了15puzzle,相似的8puzzle问题可解性证明也是一样的。

嗯,现在你可以给小伙伴出个解不出来的15puzzle,然后一边吃瓜一边看你的小伙伴满头大汗了。所以在你的小伙伴也看到这篇文章之前,尽情为所欲为吧!。

参考

欢迎来我的博客看此文章!

Leave a Reply