首先：
算法思路完全来自博客: 推箱子游戏自动求解算法设计(四)https://blog.csdn.net/prsniper/article/details/44265537
以及参考了：推箱子游戏中AI的实现https://www.ixueshu.com/document/c8b6be6a31949cab318947a18e7f9386.html
箱子死锁的判断：
GUI的图片来自：https://github.com/MoRanQingChen/pushBox
再次感谢博主 孤胆游侠 的分享讲解。
虽然原博已经有了详细的算法讲解，可我还是想写一个博客来记录我的完成过程。
前言：
本程序的实现效果：
操作：上下左右键移动，点击帮助按钮会自动寻路，点击选择关卡可以选关（只添加了5个关卡，喜欢可以按格式自己添加）。
（不过对于第5关（如图）的结果跑不出来，会抛出内存不够用的异常。不过如果箱子改成5个，则就可以搜寻到结果了，说明优化还差一点火候）
代码已经上传至github：https://github.com/qihe777/pushbox
本程序不存在逻辑上的bug，请放心使用，不过因为是个人开发，写的很丑陋。（地图最大支持20*20，地图文件读取未添加错误处理）
程序还是比较简单的，算法部分1天的代码量，GUI部分一天的代码量。不过我用了一个多星期的时间，先是想如何解决花了几天，想不出来又查的资料，最后优化查找算法又花了几天时间，但是优化的效果一点不明显 ( ′ д｀ )…彡…彡。
本算法还不够智能，对于大小超过19*11，箱子数量超过6个的地图（如图）很容易出现内存耗尽（尽管运行时内存可以达到1G），抛出内存不够的异常。
虽然不够智能，但是还是有学习交流的价值。如果各位有更好地优化策略，欢迎评论。
因为程序比较小，而且源码基本都有注释，而且基本都是简单的逻辑判断，所以就不贴代码了，只记录一下思路就好了。
关于推箱子问题的了解：
关于推箱子内容了解 可以从推箱子社区http://sokoban.cn/中获取
网站中指出了电脑求解的可能性：
问：推箱子关卡可以用电脑求解吗？
答：对不太大，箱子不太多的关卡，目前有不少程序都能够求出答案。但是，推箱子已经被数学家和计算机科学家证明 是PSPACE完全(PSPACE-complete)问题，即基本可以认为不存在快速（多项式时间）的求解算法。对于比较大的关卡（如我们MF8推箱子比赛的关卡）， 如今的个人电脑还无能为力。
所以，在推箱子求解上，人脑还是胜过电脑。
对于“NP难问题”的理解：https://blog.csdn.net/u014295667/article/details/47090639
推箱子格式:http://sokoban.cn/xsb_lurd.php
因为可求解的地图较小，没有实用性，所以就没有必要 实现把求解路径 按格式输出成lurd格式的文件。我只实现了读取xsb格式地图的功能。
程序整体结构设计：（uml图）
有点麻烦，有机会再画吧。
程序分层介绍：
1.GUI：有关界面显示的java swing
2.COMMAND：GUI调用command来处理请求，command调用logic来完成处理。
3.LOGIC：逻辑层，主要是算法的实现：箱子移动逻辑：MoveLogic，A*算法：Astar，扫描线种子填充法：BoundaryFilling，以及路径搜索逻辑：FindLogic。
4.STRUCT：本程序中的数据机构，讲解见下文
5.TEST：部分功能的测试
整体流程讲解：
1.点击开始按钮，PlayPage类初始化,调用FindCommand类中getMap函数获得其返回的数组，来进行页面的初始绘制，并初始化Datastatic类中的静态变量。getMap函数则是调用startLogic类中的findMap(rank)获取其从地图文件中读取得到的地图数组，并初始化Datastatic中的静态变量。
2.playPage页面监听键盘消息，当移动时，传递按键值给FindCommand类中move()函数。move()函数根据键值转换成代表方向的数字（数字代表的方向是人为规定的），并调用MoveLogic中的move函数，完成画面的移动。
3.给帮助按钮添加事件监听，当按钮被点击时，调用FindCommand类中help()函数。help()函数则是调用当前类的findPath()函数获取人物的移动路径，然后将移动路径转化成方向再调用MoveLogic中的move函数，完成画面的移动。
FindCommand中的findPath()函数讲解：调用FindLogic()类中的findPath()函数（讲解见下文的场景分析算法），来获取箱子全部到达时的场景，然后通过遍历情景的父节点，来获移动信息（情景保存的有map数组，得到当前场景需要移动的箱子及方向），根据得到的移动信息，可以确定人要到的为值，通过Astar类中的findRenyiPath（）算法来获取人移动的完整路径。
数据结构讲解：
1.char [ ] [ ]来存储地图，其中数据表示见 推箱子格式。
2.Mypoint：记录坐标。
3.Situation：记录场景。
4.Graph：将地图char[ ][ ]转化成邻接矩阵来存储图。A*算法使用
5.Node：A*算法使用，用来寻路时保存节点。
6.SimpeSitu：用来简化situation，减少内存使用。
java集合类的使用和比较：
见我的博客
部分算法讲解：
算法思路还是比较简单的，难得是优化。
1.场景分析算法（不是通用性算法，而是我起的名字）：节选自开头提及的博主
这是求解路径的核心代码
1.初始化队列，提取第一个场景到当前场景（Situation类）
2.当前场景所有箱子归位，函数返回当前situation。
3.分析场景（人移动哪个箱子及方向）得到若干个新场景，过滤重复（需要一个集合类来保存到达过的场景）并判断：如果箱子位于死结(箱子到达后不能再移动的位置)则将当前场景过滤（不添加到队列中）
4.如果过滤后新场景数量为零，此场景无解，删除场景（可优化，见下一篇）
5.追加新场景到队列，分析队列下一个场景，重复2-4
6.队列场景数量为零，场景无解（或队列太小，内存不足），返回null
注意本程序是将新场景加入队列，而不是递归。虽然这样是广度优先搜多，要搜索的内容十分庞大（地图中箱子可以到达点的数量的（箱子个数）次方，可以达到上万种情况，因而对于大地图会抛出内存不够的异常），但是使用递归来进行深度优先搜索也会有相当大的数量，而且递归搜索到的路径不不会是最短路径，而广度优先搜索搜到的可以认为是最短路径，因为只要搜索到一种路径就停止运行，得到的成功的情况就是箱子移动最少的路径。
2.扫描线种子填充法
https://www.cnblogs.com/JDomain/p/6555808.html
用来判断人是否能到达目标位置，得到填充路径后，通过查看目标点是否在路径中，来判断人是否能到达。因为这样就不用通过寻路来判断联通了，速度比较快。
3.A*算法讲解：
https://www.cnblogs.com/21207-iHome/p/6048969.html
4.hash排序以及CRC32
因为java集合类本来就有hashset，和hashmap所以不用自己实现hash算法的，不过其中hashcode只能是int，而且java自带crc32类，我又加上了，不过加上也没啥用。
我尝试过的优化方式：
1.死锁减枝，参考开头提到的网址。我已经实现了正方形死锁，死角死锁，还有一个之字形死锁，不过并没有出现明显的效率变化。
2.新增simpleSitu类来作为situation的精简版，来保存和记录箱子的到达路径，以减少内存。
针对地图5来说，我觉得优化的重点应该放在连续终点处，减少箱子没有意义的跑动。
我的见解：
推箱子和五子棋的智能算法还是有一些差距的，五子棋只用根据当前局面来判断最优落棋点，而推箱子则不一样，以本程序采用的遍历算法来看：它需要筛选不重复的路径，而如果要筛选，则必须记录走过的路径状态，而根据简单的排列组合会知道这种情况会出现庞大的局面种类（比如10*10的地图6个箱子，粗略会有（100）的6次方种可能的局面），因此需要强劲的筛选算法，来完成计算。然而如果不使用遍历搜索而采用启发式搜索算法的话，推箱子又存在重复路径问题，以我目前接触的算法来看是无法解决的。
后记：
询问了老师如何处理内存耗尽的问题，老师说：最好不要保存全部场景，而是向围棋智能算法那样实现智能搜索和增加减枝条件。而我对于围棋或者五子棋的算法完全不了解，只听说过一个alpha-beta剪枝算法，完全不知道进一步优化从哪下手，只能完成到这种程度了，等以后掌握了更多的算法，再来补坑，将程序进一步优化。