数字（字母）华容道的可解性

前言：最近在学习mathematics for computer science, 听课中思考了这样一道有趣的问题：数字/字母华容道的可解性。若要Google搜索，可以搜索"solubility of the pile puzzle"或者是"solubility of the sixteen puzzle"。其实这个问题早已被研究透彻，但我看了很多文章，解释地十分繁琐甚至有错误的地方，所以在此做一个清晰简明的总结（所用知识都是大家能看明白的）。

一、所用知识（如果有大佬能从抽象代数的角度解释就更好了）：

1.不变式（invariant）的思想：在研究一些问题时，我们可以从一个事物一直不变的性质/状态入手。例如我们要证明以下的数字华容道不可解：

看起来似乎无从下手，那么我们能不能从中找到什么不变的性质呢？首先我们可以想这个游戏是每次将数字进行上下左右移动，那么每次移动改变了什么呢？又有什么没变呢？

也许你还是一头雾水，但确实有不变的东西：我们发现完成好的数字/字母华容道，它的逆序是0（逆序会在下面讲到），而现在这个华容道的逆序数是1，而我们每次左右移动并不改变逆序数，上下移动改变逆序数的数目是0或2，所以无论我们移动多少次，都无法将逆序数为1的华容道变成逆序数为偶数/0的华容道（奇数+偶数=奇数）。若你对此还是有点难以理解，更加详细的讲解可以观看AV46506390的p3。

2.逆序数（线性代数里的概念）

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。 一个排列中逆序的总数就称为这个排列的逆序数。举个例子：

在（1，2，4，6，3，5，7，8）中，（4，3），（6，3）（6，5）都为逆序，该排列的逆序数为3。

而华容道可以以行的顺序写成一个排列，（空着的那一格是不算的），所以上面的华容道逆序数为1（（8，7）这一个逆序），而最终排好的华容道逆序数为0。

PS：我们将华容道复原专指所有数字/字母按顺序排列，将空格放在从上往下，从左往右数的最后一格。

二、数字/字母华容道一般情况的可解性

上面以3x3为例子，说明了3x3数字/字母华容道的可解性，我们可以合理推论得到（下面会作证明）：

对于n x n（n为奇数）的数字/字母华容道：其初始情况的逆序数须为偶数，该华容道可解。

那么对于n为偶数的呢？哈哈哈，是不是有点复杂了？其实并不（虽然我考虑偶数的情况时也想了很久，头发抓掉了不少），另外很多文章也是根据n=奇偶的情况去考虑，并且跳跃地给出了𝚽（𝚽指空的那一格）与逆序数的关系来判断可解性（简直坑爹，mmp）。

下面我们直接来看一般情况：其中𝚽指的是空的那一格。

n x n的数字/字母华容道中，有（n^2-1）个数字，记该华容道初始状态的逆序数为Q，𝚽所在行数为R。除了𝚽所在的这一行，其他的一行有n个数字。

如图，若将该华容道想像成i 一个排列，若将b移动到𝚽所在的位置，则把b向后移动了n-1位。因为原先排列是（·····a,b,c,······，d,e,······，f,g,h,·······）

现在排列变为（·······a,c,·····，d,b,e,·······，f,g,h,······），c，d之间有n-3个元素，b移动的位数应表示为1+n-3+1（两个1分别表示c，d），故b向后移动了n-1位。换言之，𝚽在华容道中上/下移动了n-1位（这个非常重要，一定要理解！！！

引理一：

对于一个排列，某元素向前/向后移动1位，该排列的逆序数就会增加/减少1，即该排列的逆序数的奇偶性会发生一次改变。

引理二：

在华容道中，左右移动并不改变排列的逆序数。

结论：

当n为奇数时（如3x3，5x5这类），n-1为偶数，也就是说，𝚽的上下移动不会改变排列逆序数的奇偶性，因此想要将一个华容道复原，其初始状态的逆序数必须为偶数。

当n为偶数时，n-1为奇数，每次上下移动都会改变排列逆序数的奇偶性，而如果我们要能复原偶数型nxn的华容道，那么最终𝚽位于最后一格，而𝚽位于第R行，移动到最后一行需要上下移动T=（n-R+2k）次，因为不可能一直下移，所以不是n-R次，但如果有上移操作，那么要回到原来的位置，对应地需要一次下移，所以上移下移的操作一定是偶数次，故用2k来表示。

可以看出T的奇偶性由R决定，故要能复原n为偶数的华容道，其初始状态逆序数的奇偶性要和R相同（因为奇数+奇数=偶数，偶数+偶数=偶数）

那么这时有人会问，当n为奇数时，𝚽也要到最后一格，那不是也满足T的表达式吗？如果这样，好像和n为偶数一样了诶。确实如此（指前面那句话），但n为奇为偶最重要的是上下移动到底会不会改变逆序数的奇偶性，n为奇数时，上下左右移动并不会改变排列逆序数的奇偶性，所以我们并没有讨论𝚽的位置对可解性的影响。

如果还想了解更多，可以去阅读《N数码问题直接解及优化研究》，《抽象代数基础教程》这些材料，如果只是单单想了解可解性，我的这篇专栏应该写得足够清楚明白了🧐