能不能用小板子做一个会智能推箱子的小车啊？

xieyug2012

发现一个sokoban automatic slover源码 ，(CSDN搜索 :推箱子自动求解及游戏(最终算法源码及程序),只能说“很强大”。就是说，把推箱子关卡输入软件中，就能得出答案。但软件是vc写的。好吧，改成linux的，然后让小车根据答案步骤去把箱子们一个一个推到终点。

除了要把vc程序移植到linux上以外，还要在小车组件及控制程序中增加以下基础功能 ：
1，增加实体关卡地板，可以嵌入 墙、工人、箱子等基础板块，以便让推箱子的小车能根据视频扫描把实体关卡变成电子地图，存入小车内存。
2，编制光学识别程序，进行关卡识别。
3，编制小车行走程序，按照答案推箱子。
4，行走程序需要能随时调整方向以保证行走方向的精度。也就是巡线、定位功能啦，根据地板上的特殊符号进行判定就行了。
5，还要保证一个特制的箱子在移动过程中不能偏离中线，停放位置不能歪斜。可以考虑用适当深度的凹坑自动定位的方式。

特点如下：
1，有趣，新颖，创新，推广智龙小板子的黑马小高招。.....至少我是这么认为的。
2，编程难度应该不是很大，基本程序算法有VC版的可以借鉴，实在不符合开源要求的话，我也弄了一个程序算法凑合着用。不过我的是java的。网上也很多。另外，这个游戏原产地是japan的，好玩就行。
3，能追赶当今世界人工智能的潮流。类似智能驾驶啦 ，#￥%……& 应该简单得多，而且安全。
4，费用可能高了点，个人购买的可能性不太大，作为团队学习、竞赛项目也不错。
5，参加个展览，推广会啥的，比较上档次，就是展位面积稍微大了点。
6，把外观做得萌一些，可以引起小朋友的兴趣。
7，关卡千变万化，避免枯燥感。小朋友们只要会自己摆关卡，就可以玩得不亦乐乎，不像3D打印机，绝大多数小朋友们应该都不会画CAD.
8，坏了可以修修补补，拆拆又装装的折腾，锻炼小朋友的动手能力。其实现在这世道许多大朋友们也需要舒缓心理压力了。

有兴趣的话试试吧。

sn2015ol

我觉得很好

xieyug2012

这种思维方式也可以试试 。
都说司马光砸缸是一种逆向思维，其实大禹治水也是逆向思维。

xieyug2012

好吧，研究了一下源码之后，发现努力是必须的，否则........。另外发现了一款JSOKO软件，Java版智能推箱子软件，也很强大，有源码,不过，这些强大的源码需要强大的分析能力。

xieyug2012

先找个地图分析一下 ：


这个地图一共有39个空间，6个箱子，一个精灵，按照排列组合的计算方法共39*38*37*36*35*34*33=77519922480 种位置组合关系。


以上打叉的15个地方不能放箱子 ，则位置组合减少为 39*23*22*21*20*19*18=2834591760种，是原来的1/27。
   
如果一不留神走成这两样 ，就得重来了。

当然这种错误还会有很多 ，即便仅仅计算箱子的位置组合 也有23*22*21*20*19*18=72681840 种，其中有210步才是有用的步骤，所以要优化算法，减少错误数，才能尽快找出答案。

注： 本帖及后续帖所用推箱子地图因时间较长，已经忘记出处及原作者，在此先行对原作者表示感谢。如有不便，还望海涵并明示。

xieyug2012

这个地图是不是够有水平 ？


考眼力，这是什么字 ？
感兴趣的话可到以下网站进一步了解更多内容及“XSB格式和LURD格式简介” ：http://sokoban.cn/xsb_lurd.php 。

xieyug2012

如果对楼上的地图不太适应的话，试试下面这个小清新的 。
  

daling

这个还挺有意思的。

xieyug2012

  
一个歪果仁提出了这么个公式，那么我们就先研究一下第一个概念 。
古代中国人对世界的各种理解中有一种是这样的 :


这个五行相生相克图就是数据结构课本目录中的最复杂的东东 ：图 （graph）。进一步讲，这个图是有向图 （digraph）。此图非彼图也 ~~@￥&


在这个地图中，从位置组合【推车(3,5)箱子(1,5)(2,5)】到达【推车(1,6)箱子(1,5)(2,5)】的每一步都是可逆的，也就是双向的。
推一下箱子到了位置组合【推车(1,5)箱子(1,4)(2,5)】就不能复原了，因为游戏规则只允许推箱子，不允许拉箱子。
这就表明，这个游戏的数据结构本质上是有向图。
至于算法么，那就看八仙过海各显其能了。
可以参看这个网址（科普中国权威解释）
https://baike.baidu.com/item/%E7%AE%97%E6%B3%95/209025?fr=aladdin


这里所指的“方法”是从策略的层面而言的。      
穷举法应该是最容易理解的方法，就像一江春水向东流，润泽沿途的每一颗小草。又像那一千零一夜的故事，虽步步惊心，但终能解脱。而在这个大数据的年代，我们却总是希望获得一份“众里寻他千百度，蓦然回首，那人却在灯火阑珊处”的小确幸。咋办吶？  动动脑筋转转脑壳吧！
对于本帖问题而言，就是在所有的 2834591760  种步骤中逐一比对箱子的位置与终点的位置，直到找到最终答案。

xieyug2012

研究了好些天，终于找了些资料可以来诓一下递推法了。直接说吧，如下：

        这果然又是一次古今中外的共识。通过一个人儿童时期两个时间段的观察就可以看出这个人半百之年的境遇.........这已经可以理解为递推了。Don‘t you know ?
        不过这个算法思想对本贴问题来说，暂时还看不出有什么用处 。

xieyug2012

         看到这个情况想起来什么算法了吗 ？没错，这就是递归算法。
         还有一首歌的歌词如下 ：

         这是一种很奇特的现象，本人认为，这也算递归。然而擅长解梦的周公却没提这回事儿。不过，我想，很可能是被这种解释抢了风头 ：

          如果您看过歪果仁的《盗梦空间》这部电影，你会对这种现象有一个科幻味儿很浓的理解过程。         
         另外，如果用摄像机头对着自己正在拍摄的屏幕，会在屏幕中出现无穷层次的摄像机。怎么样？ 当不了大导演，给你一个当小导演的机会也不错吧 ？
         更复杂一些的情况叫“间接递归” 。简单的讲，比如贾宝玉梦见甄宝玉，其实是这两个宝玉同时都在梦中相见.....有点懵吧 ？
         如果你站在两个镜子的中间，你会发现什么呢 ？别忘了一个镜子上贴个“前”字，另一个镜子上贴个“后”字。
         有空看看这篇文章：


         这个算法对本帖应该还是有用的。网址如下 ：

http://kns.cnki.net/KCMS/detail/detail.aspx?dbcode=CJFQ&dbname=CJFD2014&filename=DNKF201409010&v=MTIyMzFxRnkvblY3dlBJU1BBYUxHNEg5WE1wbzlFWklSOGVYMUx1eFlTN0RoMVQzcVRyV00xRnJDVVJMS2ZZT2Q=