撰写了文章 更新于 2019-09-07 21:22:18
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个数字组成了一个有序集合X1 = {1,2,3,4}。然后定义交换的方法，把这个集合中的数字换成同一个集合中另一个数字，既不重复也不遗漏。
其中方法y的意思是，把原集合中的1换成2，把2换成3，依次类推，那么得到的新集合就是为X2 = {2,1,4,3}。
这儿的方法叫做“置换”，不过名字并不是我们纠结的重点。 我们发现，诶，置换y实际上是把1和2对调了位置，把3和4也对调了位置，而1，2和3，4之间居然互不影响，真是奇了怪了，不如把独立的交换叫做循环吧。(1,2)是一个循环，(3,4)是另外一个。于是置换y记作
y = (1 2)(3 4)
同理，记作：
z = (1 2 3 4)
假设集合X1中元素的个数为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啦！我们把刚才说得奇偶置换重新解释一下。
在集合Sn中，有一置换a内有t个循环，则sgn定义为
sgn(a) = (-1)n-t
嗯，那么当sgn(a) = -1的时候，a就是偶置换，当sgn(a) = -1的时候，a就是奇置换。 然后是一个定理对集合Sn上的两个置换a和b，我们有分解的方式：
sgn(ab) = sgn(a)sgn(b)
再假设τ是一个“对换”，即只交换两个元素的置换，例如之前说到的(6 #),就是对换。 那么
sgn(τa) = sgn(a)
这个也很容易理解，偶置换多加一个循环就是奇置换，奇置换多加一个循环就是偶置换。当然，每个对换也是奇置换。
祭出最后一个推理：
游戏规则规定答案必须是对换，也就是一次交换两个元素。之前我们证明了答案的的步数是偶数，当然就是偶数个对换，那么，我们只要证明，在头图的例子中，作为偶置换的置换y，分解成对换后也是偶数个对换不就行了嘛？
设置换a可以分解成q个对换τ1.....τq，那么
sgn(a) = sgn(τ1)....sgn( τn) = (-1)q
若a是偶置换，那么sgn(a) = 1,即q是偶数。因为每个对换都是奇置换，所以偶数的奇置换就当然偶置换啦，也就说，偶置换分解成对换后，就是是偶数个对换的积。
你知道我要说什么了吧？
那么，对于标题的问题来说，答案就撂这儿了：
设初始位置上，第1到15格分别是变量a1,a2....an，第16格为“空白”，记作“#”。
为了让数字复原，必须进行的下面这个置换
如果为偶置换，那么这个15puzzle是可解的。如果是奇置换，不好意思，一边凉快去吧。
结语
如果你能看到这儿，恭喜你，抽象代数的内容你已经了解一点了。除了15puzzle，相似的8puzzle问题可解性证明也是一样的。
嗯，现在你可以给小伙伴出个解不出来的15puzzle，然后一边吃瓜一边看你的小伙伴满头大汗了。所以在你的小伙伴也看到这篇文章之前，尽情为所欲为吧！。
