华容道算法基础版

今天来聊聊华容道算法具体实现方法，华容道算法我会通过链表和红黑树两种方法实现查找算法，程序体现出来的效率差别很大。

本篇文章拿华容道横刀立马做分析，华容道游戏下图所示。游戏原理是每个方块每次只可以移动一个方格，如何将正方形移除到方块外部。拿到这个需求我们首先需要构建数学模型，该游戏设计到的方块数量较少，走法也比较少，那么可以采取穷举思想计算出最佳走法。

图 1

当方块每移动一步时，程序应该获取到当前游戏盘面下一步可以执行的路径，如果不考虑去除重复状态，那么程序每个盘面节点数量会成指数增加，这样导致计算量太大。华容道效率出现在比较上，不同的查找策略会导致效率差别在几十倍，几百倍上。

游戏数学模型如下图所示，程序应该通过一个数据结构保留查找过程中出现的所有状态，本次采用链表。程序每走一步应该获取下一步可走的路径，并且把可走路径呈现的盘面结点保存到链表中，同时应该剔除相同盘面结点。同时每个结点还会有结点指针指向下一个盘面和指向父盘面，保留这个指针的意义在于，当程序找到了方块最终应该有的状态，程序可以通过父指针回溯到最佳捷径路径，然后通过栈先进后出策略完成最终路径寻找。

图 2

程序思路已经很清楚，如何构造每个盘面结点呢？早期由于计算机内存比较小，华容道算法都采取牺牲性能来换取内存空间，一个盘面采用一个int就可以表示完全。盘面和走法图片来源于网络。

图 3 盘面表示方法

图 4 程序走法思想

上图是用性能换内存思想，现在电脑的内存都比较大，盘面编码方式也随之改变，本次编码采用最简单的数字编码，整个游戏盘面是5*4=20方格，编码方式如下如图所示。

图 5

其实这种编码方式效率比较低，如果2和5对调其实是一种状态，本次实验为了简单，由浅入深分析算法效率。下面开始代码编写环节。盘面结点与初始值状态值如下所示，state二维数组用来存储每个结点的实际值,并且赋值为横刀立马的初始值。

图 6

判断下一步可以的走法，采取遍历二维数组方式。

图 7

每次判断得到新的状态，链接到c这个链表后面，上图的整个循环是获取当前盘面的可走的所有方法，在得到可走的路径时需要判断是否与以前盘面结点重复。如何判断下一步可走，下面只列举正方形的走法。其他的棋子走法请看源代码。正方形走法如下所示。

图 8

如何判断重复比较重要的环节，本次同样采用效率最低的遍历去判断重复，重链表头比对到链表尾巴，每个结点状态通过一一比较数组的值来判断当前盘面是否重复，这个编码方式与判断重复是最简单的，但效率是最低的，下篇文章提高效率。

图 9

棋子连续走几步解决方案，当前从棋子布局初始状态变化到如下状态，如果按照一步一步走法算，这个路径是两步，如果棋子可以拐弯或者走几步，那么达到现在这个状态最多算一步。本次实验没有优化这个代码，下篇文章会提供优化好的华容道算法。

本次实验结果是，该程序运行花费时间为2~3小时，下篇文章优化效率后时间不到10ms。

源码下载：https://download.csdn.net/download/qq_21792169/11044867