基于A*算法的滑动拼图mathematica实现

作者：winnie de pooh

关键词：滑动拼图，估价函数，A*算法，逆序数，动态交互

1、前言

滑动拼图是非常经典的游戏，网络上有各种语言实现的滑动拼图程序。本程序是在mathematica当中实现的滑动拼图，在Wolfram Demostrations Project上有一个差不多的CDF项目，觉得十分地有意思，所以模仿了一下，完全没有使用Project的代码。

图1  Wolfram Demostrations Project滑动拼图

相比网站上的例子，本程序采用逆序数定理保证每一个初始情况都能被还原，也增加了通常模式下支持自己图片导入游戏的模式，更是增加了一个挑战模式，增加了A*算法寻找最优解的函数和功能，能够得到目前初始条件下的达到最优解的步数。

本程序使用的是Button作为按键，动态功能使用Annotation实现，而网站上Project使用的是Manipulate，本程序使用的是DynamicModule，具有更快且更好自定义的特点。

图2  本程序的界面和A*算法预测的最佳步数

本程序的挑战模式的每块拼图都是隐藏的，在点击下才会显示，每次只会同时显示一张图片，所以增加了相应的还原难度。

图3  挑战模式

2、滑动拼图中的A*算法

A*算法是一种启发式的局部贪婪算法，通过将当前状态下的所有后续节点与最终目标解进行对比，对于某个格局，通过一次移动滑块而得到的格局，称为其后继格局。我们需要找到某个中间格局的所有后继格局，即每种可能的走法所能得到的格局，并计算得到这个格局的代价。同时，为了尽快到达目标格局，我们需要对这些后继格局进行评价，找出一个可能最先到达目标格局的。

图4  初始状态和后续可能状态对比

通过比较初始状态所对应的所有可能状态与目标状态的差值，将差值最小的后续节点作为下一步节点。

   差值为33  

图5  后续状态与目标状态的差值

按照最小差值的状态移动之后，再次生成其所对应的可能后续状态（不包含前一步状态），再次计算与目标状态的差值，执行下一步移动，如此循环，直到达到目标状态，程序结束。

3、逆序数定理

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。也就是说，对于n个不同的元素，先规定各元素之间有一个标准次序（例如n个不同的自然数，可规定从小到大为标准次序），于是在这n个元素的任一排列中，当某两个元素的实际先后次序与标准次序不同时，就说有1个逆序。一个排列中所有逆序总数叫做这个排列的逆序数。

初始状态的逆序数可以判断该初始状态能否达到目标状态，只有逆序数为偶数的初始状态才能还原为目标状态。

最后,欢迎通过公众号"320科技工作室"联系我们.