# 八数码难题（8 puzzle）有无解的严格证明、求解算法设计及其他 **八数码难题（8 puzzle）有无解的严格证明、求解算法设计及其他** ## 引言 [上一篇文章](Quik24Points_Implement_Solve_RatCalcExp_and_Other "速算24点的实现与求解、有理数运算、表达式解析及其他") 提到关于步步高的最令我怀念的游戏**原子对接**，可惜这篇文章不是讲这个游戏的，是的，我鸽了。但是我也没有完全鸽，其实关于原子对接这个游戏的实现，我早在两个月前，[上一篇文章](Quik24Points_Implement_Solve_RatCalcExp_and_Other "速算24点的实现与求解、有理数运算、表达式解析及其他") 发布的时候就已经实现了，之所以一直没有发出来，只是我觉的还不够写一篇完整的博客去解释，我想再攒攒。 但是由于一些不得不面对的环境变动，今后可能不能像现在这样慢慢的攒一篇长博客再发了，也是基于这个原因，我迫不及待的将该篇还未完全完成的博文发布出来，待以后有时间了慢慢完善。对原子对接游戏迫不及待的读者可以先行试玩：[原子对接-游戏](http://1157.huaying1988.com/atomix.html "步步高-原子对接游戏-网页版")，为了更好的完成这个游戏，我还开发了关于它的地图编辑器：[原子对接-地图编辑器](http://1157.huaying1988.com/atomixEdit.html "步步高-原子对接游戏-地图编辑器")。 之所以，一直没有发布原子对接的实现，是因为我觉得只发个游戏，不搞个求解器是不完整的，但是直接搞原子对接的求解器我又觉的有点难度，于是，我决定先用八数码难题（8 puzzle）来练练手，也就是本篇博文的主题。 ## 目录 [TOC] ## 什么是八数码难题（8 puzzle）？ 八数码难题（8 puzzle）又称九宫格拼图游戏。 游戏场地是一个3×3的九宫格，内有1~8八个数字及一个空格，跟空格在上、下、左、右四个方向邻接数字可以通过与空格交换位置进行移动。玩家通过一系列的移动使得数字以及空格排列由初始状态最终变化为游戏的目标状态，在这个过程中如果移动最少的步数达到目标的话，该移动过程称为从某初始状态到最终状态最优解。 之所以又称为九宫格拼图游戏，是因为把1~8八个数字改为8张拼图的话，这就是一个很传统很老套的拼图游戏了。 上面说了一通，对于没接触过的人来说还是太抽象了，不必担心，还是要祭出一个具体的游戏实现的: [8数码拼图游戏(8 Puzzle)](http://1157.huaying1988.com/ptyx.html "8数码拼图游戏(8 Puzzle)") 。这个游戏最早是我在上大学的时候写来自娱自乐的，现在回过头来看，已经十多年过去了，还是很感慨的…… 游戏的实现简单而原始，我就不再花费时间和精力去讲解了，因为这些都不是本篇博文的重点。  ## 关于八数码难题是否有解的严格证明 关于这个问题，我早在大学的时候就在思考了，为此当时我还专门给仰慕已久的[Matrix67大牛](http://www.matrix67.com/blog/ "Matrix67的博客")发gmail邮件求教该问题，跟这个问题一起求教的还有关于全排列列表算法的问题。关于全排列列表算法，Matrix67给了一个递归算法，我看完之后恍然大悟，这个算法在[上一篇文章](Quik24Points_Implement_Solve_RatCalcExp_and_Other "速算24点的实现与求解、有理数运算、表达式解析及其他") 中也有涉及和实现。但是关于8数码是否有解的难题，Matrix67给出的指导并不成熟，这也导致这么多年成为我一直想要解决的一个问题。 当前在网上也能找到一些证明，比如在水木清华BBS上的关于八数码有解性的讨论 [《关于八码数问题有解与无解的证明》](https://blog.csdn.net/ju136/article/details/6876647 "《关于八码数问题有解与无解的证明》") （由于原链接已失效，此处给出的是引用链接）。 这些证明都给出了八数码问题是否有解的判定结论: ** 将八数码问题中的八个数字（忽略掉空格）按照其在九宫格中的位置从左到右从上到下依次排列（顺序见下图），若初始状态排列与目标状态排列的奇偶性相同，则该八数码问题有解/可达。 **  但是仔细观察网上这些文章的证明过程都并不严谨，**大部分只能证明其必要性，不能证明其充分性。即只能证明八数码问题有解则奇偶性一定相同，并不能证明奇偶性相同则八数码问题一定可达。**本文将给出一个完全严格的证明，证明**排列奇偶性是否相同和八数码问题是否可达是等价的**。 但是在给出证明之前，先要复习《线性代数》…… ### 排列奇偶性相关知识复习 我们先来复习一下，我们在《线性代数》这门课中学到的关于排列奇偶性的相关知识。有了这些基础知识，再证明相关结论就不难了。  当年我上大学的时候学的是哈工大出版社出版的《线性代数与解析几何(偏理)》这本书，我看过同济大学应用数学系编著的《工程数学-线性代数》，真是太简略了……  所以我们一起来复习一下，同时也补上那些被编著者省略掉的一些小细节。 #### 排列、逆序数、对换的基本定义 把n个不同的元素按一定的顺序排列成一行，成为这n个元素的一个**排列**。n个不同元素的排列共有n!种。 由 $$ 1,2,\cdots,n $$ 组成的一个有序数组称为一个**n阶排列**。通常用$$ j_1j_2 \cdots j_n $$表示，且当$$ m\neq l $$时，$$ j_m \neq j_l (m,l=1,2,\cdots,n)$$。 对于n个自然数的一个排列，如果一个大数排在一个小数之前，就称这两个数构成一个**逆序**。一个排列的逆序总和称为该排列的**逆序数**，记为$$ \tau( j_1 j_2 \cdots j_n ) $$ 。 如5阶排列31542的逆序是(3,1),(3,2),(5,4),(5,2),(4,2),故 $$ \tau(31542) = 5 $$ 。 逆序数为奇数的排列称为**奇排列**。逆序数为偶数的排列称为**偶排列**。**自然排列** $$ 123 \cdots n $$ 的逆序数为0，故它是偶排列。 在一个排列中，把某两个数的位置互换（其他数不动）变成另一个排列的变动称为一个**对换**，将相邻的两个数对换称为**相邻对换**。 #### 排列的性质 **（1）一个排列中的任意两个数对换后，排列改变奇偶性。** 即经过一次对换，奇排列变成偶排列，偶排列变成奇排列。 【证明】 先证明相邻对换的情形 设排列 $$ a_1 a_2 \cdots a_s a b b_1 b_2 \cdots b_t $$ ,对换a与b后排列变为 $$ a_1 a_2 \cdots a_s b a b_1 b_2 \cdots b_t $$ 。 易见，a与b的对换不影响 $$ a_1 a_2 \cdots a_s $$ , $$ b_1 b_2 \cdots b_t $$ 与其他数的序关系。但a、b两数间的序关系却变为：当 $$ a \lt b $$ 时在新排列中a、b构成逆序；当 $$ a \gt b $$ 时在新排列中a、b不构成逆序。因而，排列 $$ a_1 a_2 \cdots a_s a b b_1 b_2 \cdots b_t $$ 的逆序比排列 $$ a_1 a_2 \cdots a_s b a b_1 b_2 \cdots b_t $$ 的逆序多1或者少1，因而奇偶性不同。 再证一般对换情形。 对排列 $$ a_1 a_2 \cdots a_s \quad a \quad b_1 b_2 \cdots b_m \quad b \quad c_1 c_2 \cdots c_t $$ 作 $$ m $$ 次相邻对换，调成 $$ a_1 a_2 \cdots a_s \quad a b \quad b_1 b_2 \cdots b_m c_1 c_2 \cdots c_t $$ , 再作 $$ m+1 $$ 次相邻对换，调成 $$ a_1 a_2 \cdots a_s \quad b \quad b_1 b_2 \cdots b_m \quad a \quad c_1 c_2 \cdots c_t $$ 。总之，经过 $$ 2m+1 $$ 次相邻对换，可以把排列$$ a_1 a_2 \cdots a_s \quad a \quad b_1 b_2 \cdots b_m \quad b \quad c_1 c_2 \cdots c_t $$ 调成排列 $$ a_1 a_2 \cdots a_s \quad b \quad b_1 b_2 \cdots b_m \quad a \quad c_1 c_2 \cdots c_t $$ ，所以这两个排列的奇偶性相反。**证毕** **（2）在全部的 $$ n \quad ( n \ge 2 ) $$ 阶排列中，奇偶排列各占一半，各有 $$ \frac{n!}{2} $$ 个。。** 【证明】 假设在全部n级排列中共有s个奇排列，t个偶排列。将s个奇排列中的前两个数字对换，得到s个互不相同的偶排列。因此 $$ s \le t $$ 。同理可证 $$ t \le s $$ ，于是 $$ s = t $$ ，即奇、偶排列的总数相等，各有 $$ \frac{n!}{2} $$ 个。 **（3）任意一个n阶排列都可以经过一系列对换变成自然排列，并且所作对换的次数与这个排列有相同的奇偶性。** 【证明】 我们对排列的阶数n作数学归纳法，来证任意一个n阶排列都可以经过一系列对换变成自然序列： ①1阶排列只有一个，结论显然成立。 ②假设结论对n-1阶排列已经成立，证对n阶排列的情形结论也成立。 设 $$ j\_1 j\_2 \cdots j\_n $$ 是一个n阶排列，如果 $$ j\_n = n $$ ，那么根据归纳法假设，n-1级排列 $$ j\_1 j\_2 \cdots j\_{n-1} $$ 可以经过一系列变换变成自然序列，即 $$ 1 2 \cdots n-1 $$，于是这一系列对换也就把 $$ j\_1 j\_2 \cdots j\_n $$ 变成 $$ 1 2 \cdots n $$ 这种自然序列的形式。 如果 $$ j\_n \ne n $$ ，那么对 $$ j\_1 j\_2 \cdots j\_n $$ 作 $$ j\_n $$ 和 $$ n $$ 的对换，它就变成 $$ j\_1^{\prime} j\_2^{\prime} \cdots j^{\prime}\_{n-1} n $$ ，这就归结成上面的情形，因此结论普遍成立。 相仿地，自然序列 $$ 1 2 \cdots n $$ 也可用一系列对换变成 $$ j\_1 j\_2 \cdots j\_n $$ ，因为自然序列逆序数为0，是偶排列，所以根据性质（1），所做对换的次数与排列 $$ j\_1 j\_2 \cdots j\_n $$ 有相同的奇偶性。 ### 奇偶性与可达性的关系及证明 #### 必要性证明过程 **八数码问题所有可达状态的排列奇偶性都相同** 根据定义，显而易见：八数码问题中的左移和右移操作并不会改变排列，而上移和下移操作会导致排列中某个元素前移2格或后移2格。 根据上面排列的性质，前移2格和后移2格都相当于做了两次相邻变换，奇偶性不变。 可得，八数码的操作不会改变排列的奇偶性，即八数码问题所有可达状态的排列都奇偶性都相同 #### 充分性证明过程 **排列的奇偶性相同则对应在八数码问题中也可达。** 根据以上排列性质的观察和思考，可得推论： 性质（1）推论：** 任意一次 对换 都可以通过 奇数次 相邻对换 来达到相同的效果。那么，偶数次 对换 可以通过 偶数次 相邻对换 来达到相同的效果。 ** 性质（3）推论：** 经过 偶数次 对换 可以从一个排列到达其他任意一个与它奇偶性相同的排列。 ** 根据上面两个推论可以得到新的推论：** 经过 偶数次 相邻对换 操作可以从一个排列到达其他任意一个与它奇偶性相同的排列。 ** 即 **排列奇偶性相同 等价于 通过偶数次相邻对换可达 ** ** 在不改变排列顺序的前提下，对于空格在任意位置的状态都是可达的。** 【证明】 空格可以在不改变排列顺序的前提下，在行内任意移动。 空格可以在不改变排列顺序的前提下，在行间任意移动： 经过验证，空格可以经过11步操作，由第1行移动到第2行而不改变排列顺序，如下图：  由于这11步操作中，第3行未受到任何影响，那么可以通过相似的步骤将空格再由第2行移动到第3行。 由此得证:在不改变排列顺序的前提下，对于空格在任意位置的状态都是可达的。 ** 针对排列中任意位置元素的“前移2格”和“后移2格”操作都可以在八数码中通过操作来完成。** 【证明】 根据上面的证明，在不改变排列顺序的前提下，空格可达任意位置。 对于一个8阶排列共由6种情况的“前移2格”的操作，参考下图，分别可以由纵向向下的箭头操作①→④、④→⑦、②→⑤、⑤→⑧、③→⑥、⑥→⑨这6个操作来完成。 同理，8阶排列的6种“后移2格”操作，分别可以由纵向向上的箭头操作④→①、⑦→④、⑤→②、⑧→⑤、⑥→③、⑨→⑥这6个操作来完成。  **任意两次相邻对换都可以通过“前移2格”和“后移2格”来达到相同的效果。** 【证明】 设两次相邻对换分别为序列中ab两个相邻元素、cd两个相邻元素进行相邻对换，不妨设ab在排列中的位置比cd靠前或相等，那么序列的形式类似于 **…… ab …… cd ……** 两次相邻对换后的结果为 **…… ba …… dc ……** 我们把a到c中间间隔的元素个数称为两次相邻对换的间隔距离，下面我们按照两次相邻对换的间隔距离来分情况讨论： ①相隔0个元素，即两次相邻对换的是同样的两个元素，那么整个序列未发生变化 ②相隔1个元素，即b和c重合，经过两次相邻对换后，相当于d前移两格或者a后移两格 ③其他相隔奇数个元素的情况 原序列 **…… ab …奇数个元素… cd ……** c每次前移2格，经过有限次前移2格操作之后排列可变为 **…… acb …奇数个元素… d ……** a后移2格变为 **…… cba …奇数个元素… d ……** c每次后移2格，经过有限次前移2格操作之后排列可变为 **…… ba …奇数个元素… dc ……** 达到最终效果。 ④其他相隔偶数个元素的情况 原序列 **…… ab …偶数个元素… cd ……** c每次前移2格，经过有限次前移2格操作之后排列可变为 **…… abc …偶数个元素… d ……** a后移2格变为 **…… bca …偶数个元素… d ……** c每次后移2格，经过有限次前移2格操作之后排列可变为 **…… ba …偶数个元素… dc ……** 由此，得证结论，即**两个排列如果通过偶数次相邻对换可达，那么通过“前移2格”和“后移2格”也一定可达** 综上可得总结论，排列奇偶性相同，那么通过“前移2格”和“后移2格”也一定可达，即**在八数码问题中可以通过操作来达到所有奇偶性相同的排列**。 ## 八数码难题的求解 不给求解过程的难题的不完整的，此处先放一个[我实现的求解器的链接](http://1157.huaying1988.com/8puzzle.html "8数码难题自动求最优解"),大家可以先看看我解的对不对，再看下面的介绍。  ### 求解算法的选择 我看过网上大部分写的八数码问题求解器的介绍，以A*启发式算法以及深度优先遍历为主，我觉得就属于误入歧途了。 首先，求八数码问题的最优解是一个P完全问题（P-complete problem，抱歉，之前想当然的认为是NP完全问题），也就是说，在不进行全局遍历的条件下，得到的往往不是全局最优解，尤其是基于A*启发式算法的深度优先遍历，得到的答案往往是局部最优解，或者连局部最优解都不是（这取决于估值函数的准确程度）。 其次，八数码问题在得知可解性的前提下，对于现代计算机来说，问题规模简直小菜一碟，即便是针对所有状态的完全遍历，规模也算不上大，后面有时间我会完全遍历，并把结果存入SQLite数据库，方便大家对该问题有一个完整的把握。 基于以上原因，我选择的算法是**基于广度优先的层次遍历算法**，由于在遍历过程中每得到一个原先没有遍历过的新状态所经历的路径都是从初始状态到该状态的最短路径，故在一个状态只遍历一次的前提下，首次得到的目标状态所经历的路径一定是步数最少的那个，即最优解路径。 ### 游戏状态的存储 #### 游戏状态是啥？ 游戏状态就是在某一时刻用来刻画游戏当前情况的一个或一系列的值，一个时刻游戏只能有一个状态，但两个不同的时刻的游戏状态却有可能是相同的。 对于8数码难题来说，游戏状态就是当前各数字和空格的位置顺序，如果两个时刻数字和空格的位置顺序完全相同，那么我们认为这是两个相同的状态。 根据以上定义，8数码难题每经过一次移动空格的操作，游戏就从一个状态，变成了另一个状态，但是再经过数次操作之后，状态有可能会回到起点或者变到一个之前存在过的状态。所以为了方便在到达目标状态时回溯路径并识别之前已经存在过的状态，我们要在遍历过程中记录所做的操作以及经历的状态。 #### 为何需要设计游戏状态的存储 根据排列组合的知识，我们知道8数码难题一共有 $$ 9! = 362880 $$ 个状态，如果只看可达的状态的话，奇偶对半是181440个状态。 如果我们用最简单的存储方法，比如用0-8这9个数字的顺序来记录一个游戏状态，给每一个数字分配一个字节的存储，那么我们就需要9个字节来存储一个游戏状态，那么181440个状态就需要1632960个字节来存储，大约是1.56MB的空间，如果要存所有状态的话，大约是3MB多，这个数据量对于现代计算机来说确实是不值一提的。 但是，最近两天我一直在看FC学习机相关的东西，并且开始研究一些芯片、单片机、嵌入式系统方面的东西，这些东西的内存都受限相当严重，这让我意识到我们在处理单纯的算法问题的时候，值得节省的空间以及相应的代价都是需要仔细的研究和讨论的。 #### 最节省空间的存储方案（仅作讨论） 我们先计算一下，存储一个游戏状态至少需要多大的空间。 假设我们给 362880 个状态从0开始依次编号到362879，用编号来代表确定的不同状态的话，那么存储这个编号至少需要 $$ log_2 362880 \approx 18.469133 $$ ，也就是说至少需要19位二进制存储才能分辨每一个状态。 那么假设我们采用19位编号来存储状态的化，如何才能把这个编号对应到相应的状态上去呢？直接想到的就是建一张映射表，然后根据编号去查，但是这是不现实的，因为这个表所占用的空间比我们刚刚省掉的空间还要多。于是就需要这个编号经过精心的设计，保证编号可以通过计算映射到每个状态上去。 此处给出一个我设想的理想方案： 存储编号 = 空格所在位置【0~8】 + 9\*(数字1所在位置【剩余8个位置的0~7】 + 8\*(数字2所在位置【剩余7个位置的0~6】 + 7\*(数字3所在位置【剩余6个位置的0~5】 + 6\*(数字4所在位置【剩余5个位置的0~4】 + 5\*(数字5所在位置【剩余4个位置的0~3】 + 4\*(数字6所在位置【剩余3个位置的0~2】 + 3\*(数字7所在位置【剩余2个位置的0或1】 + 2\*(编号8所在的位置【最后剩下1个的位置恒0】)))))))) 于是，把编号还原回来的方式是通过不断的取整除法和取余运算(\代表向下取整除法): ``` 位置序列 = 【0,1,2,3,4,5,6,7,8】 空格所在位置 = 存储编号 % 9 计算中编号 = 存储编号 \ 9 位置序列 删除 空格所在位置的编号 数字1所在位置序号 = 计算中编号 % 8 计算中编号 = 计算中编号 \ 8 数字1所在位置 = 位置序列【数字1所在位置序号】 位置序列 删除 位置序列【数字1所在位置序号】 数字2所在位置序号 = 计算中编号 % 7 计算中编号 = 计算中编号 \ 7 数字2所在位置 = 位置序列【数字2所在位置序号】 位置序列 删除 位置序列【数字2所在位置序号】 数字3所在位置序号 = 计算中编号 % 6 计算中编号 = 计算中编号 \ 6 数字3所在位置 = 位置序列【数字3所在位置序号】 位置序列 删除 位置序列【数字3所在位置序号】 … … … … … … ``` 由于该方案存储效率最高，但是计算量大且复杂，且极度不利于游戏的推演，故此处只是从理论上讨论理想情况下该如何存储和设计，不要去计较太具体的细节。 #### 当前使用的存储方案 根据上面的讨论可以看到，在节省存储空间的同时，会产生大量的运算代价。经过一番思考、调研，为兼顾存储与计算，采用了下面的存储方案。 1~8这8个数字减1变成0~7记录数字的排列顺序，每个数字需要3 bit的存储空间，空格单独存储位置，需要4bit的存储空间，所以，每个游戏状态需要28 bit的存储空间。 举个例子，空格用0表示的话，下图状态可表示为数字排列 **517432086**。  该排列采用存储方案后就变成 **40632175-6**。 存储时可以采取大端法和小端法。 采用小端法： | 序号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | * | | ----- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | | 数字 | 4 | 0 | 6 | 3 | 2 | 1 | 7 | 5 | 6 | | bit位 | 100 | 000 | 110 | 011 | 010 | 001 | 111 | 101 | 0110 | 采用大端法（当前采用的存储方法）： | 序号 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | * | | ----- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | | 数字 | 5 | 7 | 1 | 2 | 3 | 6 | 0 | 4 | 6 | | bit位 | 101 | 111 | 001 | 010 | 011 | 110 | 000 | 100 | 0110 | 实现的时候分别采用这两种存储方法分别都实现了一下，试了一下，最后经过对比，最终还是采用的大端法。 小端法的基础实现还在页面源码中并没有删除，只是注释掉了，感兴趣的可以切换注释尝试一下，这两种存储方式对于结果并没有什么影响，只是实现的基础方法略有不同。 存储方案制定之后，先要实现普通的数字排列转换为这种存储的方法。普通的数字排列一般是整型数组的形式，这种存储方式由于只占用28bit的存储，用一个32bit的Int就完全可以存储，我把这个**Int32所代表的数字称为该状态的Id**，于是，我先实现了数组转Id的逻辑。 之后顺利成章的应该实现Id转数组的逻辑了，但是我转念一想，数组只是为了方便处理过程的一个临时格式，处理完之后就销毁了。如果我在处理过程中不经过数组这一步的转换，边解析Id边处理的话，就完全不需要数组这么一个临时格式了。于是，我并没有直接实现Id转数组的方法，而是实现了一个Id解析流式处理回调的方法：该方法解析Id中的数字排列，按照数字还原后的排列顺序依次调用参数中的回调函数，达到顺序处理的目的。这样的话Id转数组的方法也是这种流式处理的一种实现而已。有了Id流式处理方法，可以按需求对Id进行各种的转换和格式化，还可以进行灵活的处理过程，而且不用关心Id的具体存储结构是什么。 ### 是否有解判断（对Id处理方法的完善及检验） 上面已经讨论过了，八数码问题是否有解，取决于初始状态与目标状态排列的逆序数奇偶性是否相同。 求排列逆序数的方法十分简单，嵌套遍历两次数字排列，比较计数就行。但是为了更好的实现这两次嵌套遍历，我还专门修改的Id解析流式处理的方法，调用时添加了遍历的起始位置参数、回调函数添加了当前遍历序号的参数。 计算得两个状态的排列逆序数之后，比较两者奇偶性是否相同就行，此处直接采用二进制末位比较的捷径来处理：假设两者的逆序数分别为T1和T2，如果 ( (T1 & 0x01) == (T2 & 0x01) ) 为 True ，则表明奇偶性相同，问题有解，否则，问题无解。 ### 基本对换操作的实现 对换是针对游戏状态排列的基本操作，实现了对换操作之后，其他所有的操作都可以等价为一次或若干次对换操作来完成，故实现一个完善、高效的针对游戏状态Id的对换操作非常重要。 此处将对换操作划分成了两种情况来分别做处理：两个数字之间的对换、数字和空格之间的对换。 #### 两个数字之间的对换操作（巧用异或XOR） 两个数字之间的对换情况较为简单，因为不涉及移位，直接交换Id中的两个数字就行，但是针对一个Int内部位相关的交换操作还并不是那么简单能完成的，此处就使用了一个底层硬件开发常用的小技巧——异或操作。 | A | B | XOR | | - | - | --- | | 0 | 0 | 0 | | 0 | 1 | 1 | | 1 | 0 | 1 | | 1 | 1 | 0 | 异或操作有这么几个优秀的特点 1. 0异或一个数，结果还是这个数 2. 1异或一个数，结果是这个数的取反 3. 一个数异或同一个数两次，又会变回原来的数，即等于没做操作 此处引出一个小的联想，那就是我们日常进行**两个变量值的交换**都要用到第三个变量（临时），如下： ```c t = a ; a = b ; b = t ; ``` 采用临时变量t，对a和b进行了交换操作。那么有没有办法**不使用临时变量完成两个数的交换**呢？当然，也是可以的，如下: ```c a = a + b ; b = a - b ; a = a - b ; ``` 此处巧妙的利用了加法和减法这一对互逆操作，在整个操作过程中，a、b两个变量所蕴含的信息量进行了转移，但并没有发生变化，从而可以使用逆操作还原回a和b的值，但是该操作巧妙的利用了蕴含及还原过程中的信息的转移。 既然加减可以，那么乘除这一对互逆操作也可以，而**异或操作的特点就是自己是自己的逆操作**，过程也是相当神奇： ```c a = a ^ b ; b = a ^ b ; a = a ^ b ; ``` 是的，a和b就这么异或了三次，结果就进行了交换…… 于是异或操作的这个特性导致它用在交换一个二进制数中的不同位的数值时非常有用。 继续用刚才的例子，如我要交换其中1和6这两个数，那么我把1和6先进行异或操作： 1(001)⊕6(110) = 7(111) 然后构造一个等长的掩码，先默认为0，然后把7(111)放在两个要交换的数字位置，掩码就构造好了。用这个掩码去异或原来的数字，得到的结果就是交换后的目标结果。具体过程见下表。 | 序号 | 8 | 7 | **6** | 5 | 4 | **3** | 2 | 1 | * | | -------- | ---- | ---- | ------- | ---- | ---- | ------- | ---- | ---- | ---- | | 原排列 | 5 | 7 | **1** | 2 | 3 | **6** | 0 | 4 | 6 | | 原二进制 | 101 | 111 | **001** | 010 | 011 | **110** | 000 | 100 | 0110 | | 异或掩码 | 000 | 000 | **111** | 000 | 000 | **111** | 000 | 000 | 0000 | | 异或结果 | 101 | 111 | **110** | 010 | 011 | **001** | 000 | 100 | 0110 | | 结果排列 | 5 | 7 | **6** | 2 | 3 | **1** | 0 | 4 | 6 | 此处巧妙的利用了异或操作的特点以及异或掩码的构造：掩码的其他位为0，异或时不改变这些位的值，而要交换的两个数的位置，有这两个数异或的结果，这个结果，异或任何一个数都会得到另一个数。 #### 数字和空格之间的对换操作 数字与空格之间的对换操作可能涉及移位操作，实现起来要比数字间的交换操作复杂的多，而且并没有什么简单的捷径，只能按部就班的分段、分情况处理。 ##### 数字位置与空格位置相邻 如果数字位置与空格位置**相邻**，就不用进行移位操作，因为数字的排列顺序根本就没有发生变化，此时只需要修改最后四位空格的位置即可（空格位置加1或减1）。 ##### 数字位置与空格位置不相邻 如果数字位置与空格位置**不相邻**，除了修改最后四位空格的位置外，还需要对空格位置到数字位置间的数字进行交换和移位操作。实现该操作还是采用异或操作来进行变换，于是问题的重点其实是获得待变换的位置区间以及该区间的目标结果，将两者进行异或操作，构造出需要目标掩码。 还是采用前面的排列做例子，根据空格和数字位置的不同分别讨论操作步骤。 ###### 数字位置在空格位置的前面 当前空格的位置是6，也就是在第6个位置数字1的后面，假设我们要把它跟位置3（数字6）进行交换，操作方法如下表： | 序号 | 8 | 7 | 6 | 5 | 4 | **3 ** | 2 | 1 | **\* ** | | -------- | ---- | ---- | ------- | --- | --- | ------- | ---- | ---- | --------- | | 原排列 | 5 | 7 | 1 | 2 | 3 | **6 ** | 0 | 4 | **6 ** | | 原二进制 | 101 | 111 | 001 | 010 | 011 | **110** | 000 | 100 | **0110 ** | | 待变区间 | 000 | 000 | 001 | 010 | 011 | **110** | 000 | 000 | **0110 ** | | 目标区间 | 000 | 000 | **110** | 001 | 010 | 011 | 000 | 000 | **0010 ** | | 异或掩码 | 000 | 000 | 111 | 011 | 001 | 101 | 000 | 000 | 0100 | | 异或结果 | 101 | 111 | **110** | 001 | 010 | 011 | 000 | 100 | **0010 ** | | 结果排列 | 5 | 7 | **6 ** | 1 | 2 | 3 | 0 | 4 | **2 ** | 注： 异或掩码 = 待变区间 ⊕ 目标区间 ； 异或结果 = 原二进制 ⊕ 异或掩码 。 ###### 数字位置在空格位置的后面 当前空格的位置是6，也就是在第6个位置数字1的后面，假设我们要把它跟位置8（数字5）进行交换，操作方法如下表： | 序号 | **8 ** | 7 | 6 | 5 | 4 | 3 | 2 | 1 | **\* ** | | -------- | ------- | ------- | --- | --- | --- | --- | ---- | ---- | --------- | | 原排列 | **5 ** | 7 | 1 | 2 | 3 | 6 | 0 | 4 | **6 ** | | 原二进制 | **101** | 111 | 001 | 010 | 011 | 110 | 000 | 100 | **0110 ** | | 待变区间 | **101** | 111 | 000 | 000 | 000 | 000 | 000 | 000 | **0110 ** | | 目标区间 | 111 | **101** | 000 | 000 | 000 | 000 | 000 | 000 | **1000 ** | | 异或掩码 | 010 | 010 | 000 | 000 | 000 | 000 | 000 | 000 | 1110 | | 异或结果 | 111 | **101** | 001 | 010 | 011 | 110 | 000 | 100 | **1000 ** | | 结果排列 | 7 | **5 ** | 1 | 2 | 3 | 6 | 0 | 4 | **8 ** | 注： 异或掩码 = 待变区间 ⊕ 目标区间 ； 异或结果 = 原二进制 ⊕ 异或掩码 。 ### 游戏初始状态、目标状态的随机生成 随机初始化序列，又是一个[老生常谈的随机洗牌算法](generate_random_array "C语言中的随机函数分析与生成m个不重复随机数算法比较") ，但是这次可不太一样，还要关心问题是否可解，保证随机生成的问题总是可解的。 此处是这么处理的：先随机决定下一步要生成的该是奇排列还是偶排列，然后调用两次随机洗牌函数分别作为初始状态和目标状态，该随机洗牌函数要保证生成的结果排列都是决定好的奇偶性。 既然是随机洗牌算法，那么奇偶性当然是不能保证的，如果洗牌后的结果不是想要的奇偶性的怎么办呢？那就随便再交换一次好了？真的随便再交换一次就行么？！不完全是。这得分两种情况： 1. 又进行的对换操作是两个数字之间的交换，根据上面的理论奇偶性一定反转； 2. 又进行的对换操作是数字和空格之间的交换，那么相当于该数字前移或这后移了两者的间隔位，根据上面的理论，如果这个间隔正好是偶数，那么奇偶性不变，如果这个间隔正好是奇数，那么奇偶性反转。 为了保证在奇偶性不满足要求的情况下，再进行的这次对换操作奇偶性一定发生反转，我们总是对排列中第一个位置和最后一个位置进行对换操作，由于8数码问题一共有9个位置，第一个与最后一个位置相隔7位（奇数位），这样就保证了这两个位置不管是否有空格，奇偶性一定是反转的。 ### 操作路径、状态路径的存储及重复遍历的避免 当遍历到达目标状态的时候要进行路径回溯，以总结最优路径，由于不能确定哪一个分支最先到达目标状态，于是所有的操作路径都要进行存储，尽管经过上面的一番努力，我们选择了一个相对不那么浪费内存的状态存储方式，但是存储所有路径的方案还是需要经过仔细的设计的。 最先想到的方法是使用链表的方式，每一个状态节点都有一个指针指向来源状态节点，这种方法是可行的，而且是比较节省空间的。但是后来又想到了另一个问题，那就是怎样避免已经遍历过的状态被重复遍历？最容易想到的方法是建立一个Set或Map用来方便查找该状态是否已经被遍历了。但是结合这两个问题之后，我觉得可以把这两种结构进行合并，那就是完全用同一个Map，同时存储路径及状态是否被遍历。 存储方案如下表。Map的Key为游戏状态Id，Value为来源状态Id与来源操作Id的联合体，由于状态Id只占28位，而操作Id只占2位，两者放到一起组成一个整数依然没有超过Int32。Map中的每一个Item表示：value中的来源状态Id经过来源操作Id代表的移动后到达Key所代表的状态Id。Map中只存储Key作为新的未遍历过的状态Id时的来源，这样就能保证Map中存储的每个Key代表的来源路径都是最优的。根据游戏状态的存储规则可知，0和1并不会在游戏状态Id中出现，于是给他们赋予了特殊含义，Value为0代表该Key为初始状态Id，Key为1代表Value为目标状态（该value中存储的操作Id总是0）。 | Key | Value-前28位 | Value-后2位 | | ---------- | ------------- | ------------ | | 初始状态Id | 0 | 0 | | 状态Id-1 | 来源状态Id-1 | 来源操作Id-1 | | 状态Id-2 | 来源状态Id-2 | 来源操作Id-2 | | 状态Id-3 | 来源状态Id-3 | 来源操作Id-3 | | …… | …… | …… | | 1 | 目标状态Id | 0 | 这样Map既方便查找该状态是否被遍历过，同时又隐含了操作路径和状态路径的链表，简洁、方便、直接，一举多得，又没有太大消耗。 ### 移动方向编号及是否可操作判断 我们以空格移动的方向作为操作方向，根据下图，最多有四个操作方向：上、下、左、右  我们要对这四个方向进行编码，为了方便我们进行计算，这个编码还是需要考察研究一下的，我在思考了一段时间后，给出了如下编码方案： | 方向 | 操作Id | 交换位移 | | ---- | ------ | -------- | | 上 | 0 | -3 | | 左 | 1 | -1 | | 右 | 2 | +1 | | 下 | 3 | +3 | 交换位移就是空格所在的位置在移动的过程中与待交换的数字位置之间的差。这里有一个小坑，坑了我一下：左右操作容易理解，位置相邻肯定是差1，但是上下操作的位移是差3而不是差2的，由于上面我们讨论了太多关于前移2位和后移2位的操作，自然就以为上移和下移的位置差是2，后来调试了很久才想明白，这是个坑。 之所以这么进行编码，因为由于空格跟数字是个交换操作，所以，空格和数字的移动方向是正好相反的，有时我们会按照数字的移动方向来定义操作，那么左右和上下都要进行反转，这样编码可以通过3减去操作Id来直接转换空格方向与数字方向的关系。 第二个原因是，这样操作Id可以方便的转换为交换位移，方便进行对换操作，只需要左移1位的操作Id（即2倍的操作Id）减去3，即是交换位移。 有了操作Id的编码之后，下一个问题就是，不是所有的状态都有这四个操作方向的，其实，更确切的说，只有空格在九宫格的中间位置的时候，这四个操作方向才是全的。这时候就要进行状态和方向的可操作性判断。这儿并没有再给大家什么惊喜，本本分分的根据空格所在的位置转换为行列坐标编号（行=空格位置\3；列=空格位置%3），然后根据行列位置判断该移动方向是否可操作。 ### 游戏的求解过程（层次遍历过程）及回溯 终于到了最后一步，也就是遍历过程了，完成了这一步，求解器就基本完成了（其实后面还有格式化输出，但这不是本文的讨论重点）。 上面已经说了，求解选用的是广度优先的层次遍历算法，根据我们学过的《数据结构》的知识，层次遍历需要用到的数据结构是 —— 队列。 有了队列的知识，层次遍历过程也不是那么的难，于是遍历算法的伪代码如下： ``` 判断初始状态与目标状态的奇偶性是否相同，不同则返回不可达状态; Map初始化: Map[初始状态] = 0; 队列初始化：初始状态 入队列; 当 队列 不为空 时 循环: 队列 取出 当前状态 四个方向操作依次循环： 对 当前状态 执行 当前操作 如果 执行失败(当前状态不支持该操作)，直接进行下一次循环； 如果 执行成功： 如果 结果状态在Map中存在 直接进行下一次循环 否则： Map[结果状态] = (当前状态<<2 | 当前操作) 结果状态 入 队列; 如果 结果状态 == 目标状态 返回**回朔路径**; 结束 如果 结束 如果 结束 方向操作循环 结束 队列循环 最终还是没有遍历到目标状态，返回不可达状态。 ``` 遍历过程之后，就只剩下从Map中回朔路径还没有实现了，实现方法也很简单，顺着Map中存储的来源状态Id往回找，依次放到线性表中，最后再把线性表反转就行了（因为回朔的时候路径是反向遍历的），此处不再做更详细的描述。 ### 最终效果 历经千辛万苦，8数码难题求解器终于实现了，此处再给一遍链接和效果图： [八数码难题（8 Puzzle）最优解求解器](http://1157.huaying1988.com/8puzzle.html "8数码难题自动求最优解") 效果图:  ## 利用luaGD生成最优路径的gif动图 js的代码已经有了，只需要把js转成lua代码就行了。其实这步并没有花费太多的时间，但是我还是考虑过使用自动化工具来完成这种转换，因为我渐渐感觉有时候我经常需要在js和lua两个代码环境下进行切换,这个以后再说。 代码也不是一次翻译成功的，中间也是出了一些问题，好在使用 `LuaEditor` 可以单步调试，然后对比js在chrome下的单步调试，对比各变量的值，可以快速的定位问题，这就是有一个正确的代码做单步调试变量对照的好处。 翻译本身并不是很麻烦，再加上工具加成，很快生成gif动图的程序就写出来了，不过，美化工作令我很犯愁。搞了半天，效果还只是凑合的状态，大家多包涵。 在此提供 [利用luaGD库生成8数码问题解题动图的工具及代码包链接](luajit_luaGd_8Puzzle.7z) ，方便大家研讨学习。 生成解题gif动图的效果图：  有了这个工具之后，我又改造了之前的求解器页面，添加了生成求解过程的动图，这样就能方便大家动态直观的了解求解过程了。 注意看，每次刷新页面，上面显示的gif动图的状态都不一样哦~因为这个动图的初始状态和目标状态也是随机动态生成的~ [八数码难题（8 Puzzle）最优解求解器](http://1157.huaying1988.com/8puzzle.html "8数码难题自动求最优解")页面添加gif动图后的效果：  ## 以下章节未完待续 基于某些原因，以下章节未完待续，敬请期待…… ## 探索八数码难题的上帝之数 ## 从上帝视角重新规划求解过程