这篇文章介绍了 Sokoban Minimum Moves Solver 这款推箱子游戏的最少步数计算器。它不同于一般的解算软件，能够找到最佳解决方案，并且通过先进算法快速完成计算。软件内置了大量关卡，同时支持导入自定义关卡进行计算。
文章提到这款软件的最大特色是采用逆向搜索方法，从目标状态反推到初始状态，从而减少无用搜索并提高效率。此外，它还使用了广度优先搜索和二维队列技术来优化计算过程，并通过隧道修剪和矩阵修剪等技术排除不可能的路径，确保找到最短步数的解决方案。
不过，软件也有一些限制，比如最多只能处理八个箱子，而且最终的20个步骤会被隐藏。虽然这些功能已经非常强大，但我觉得对于一些喜欢推箱子游戏的人来说，可能还是有些不够人性化。希望未来能改进一下这些小细节，让用户体验更好。
总体来说，这款工具对寻找最优解的玩家来说非常实用，尤其是它的逆向搜索和修剪技术，确实让人眼前一亮。期待它以后能加入更多功能！
Sokoban Minimum Moves Solver是一款非常强大的推箱子最少步数计算器，和一般的推箱子解算软件不同，它是可以找出最佳的解决方案的，同时拥有先进的算法，可以快速完成计算。在计算时它会显示当前的计算进度并且结果中显示步数。软件已经内置了大量的关卡供用户体验，同时也可以导入自定义关卡来进行计算。
软件特色
该程序根据最短的步数搜索最短路径的解决方案。
但是，箱子数量限制为最多八个。
此外出于某种原因，即使您找到了解决方案，最后 20 个步骤也会被隐藏。
软件功能
采用从完成型到初始型的逆向解决方案
在从初始类型开始搜索的普通搜索方法中，除非加入大量修剪，否则将出现大量无用搜索，从而解决推箱子问题。
然而，逆向求解中的错误过程经常会困住你并使搜索收敛，使得修剪几乎没有必要。
关于一次操作的概念
如果你想找到最短步数的解法，一个动作的概念应该是一步，但既然没有必要徒劳地走动，“以最短的时间走到目标行李的前面拉行李只有一次”。这个操作是一个操作。如果是这样，是否有可能找到最小推动而不是最短步数的解决方案？不，不会发生的秘密将在下一节中描述。
使用二维队列的广度优先搜索
这个程序基本上使用了“第4章：广度优先搜索”。但是，有很多队列而不是一个。在上面的示例中，从父阶段到子阶段使用了5 个步骤。在这种情况下，父阶段从n 步队列中取出，子阶段排队n + 5 步。当 n 步队列为空时，移动到从队列中移除n + 1 步。
隧道内修剪
隧道是一条宽度为1平方的直线通道。把行李留在这个隧道的阶段永远不会达到最短步数的解决方案，所以它不会被注册为子阶段。
矩阵修剪
找出N 对夫妇是否由N 个行李和 N 个目标组成。例如，如果有4件行李（行李A、行李B、行李C、行李D）并且在某个位置pos1只能携带行李A，则Bits [pos1] = 1000（二进制）和位置pos2中如果可以携带行李A、行李B、行李D三件物品，设置Bits [pos2] = 1101（二进制数），提前查看所有方格可以携带行李的情况（Bits []）。 .
在反向解搜索时，将四个包裹（行李1、行李2、行李3和行李4）的每个位置的Bits[]值，创建一个矩阵。用这个矩阵作为N车问题（N皇后问题的车版），看看有没有解。
共有 0条评论