java - 找出打乱游戏的最少步数

Question

我想创建一个小型 Jumbler 游戏。我打算使用 Java 编程语言来制作这个游戏。以下是游戏的小屏幕截图。我找不到 包含此游戏的任何其他网站。

Screen shot of the game at the end of the page

在这个游戏中我想添加两个功能。

1. Manually solve the problem.
2. Automatically solve the problem.

Manually solve the problem

意味着我们玩并找到使数字按顺序排列的解决方案

Visually solve the problem

表示计算机以图形方式显示所需的最少移动次数 为解决方案。这意味着计算机以图形方式显示移动并确定移动最少的解决方案。

那么如何对这种情况进行编程呢？

我在互联网上搜索并获得了一些与线性规划相关的教程。我应该学什么 为了解决这类问题？我不知道如何解决自动解决方案。请给 一些很好的教程，我可以轻松掌握。

Answer 1

当你只有一把锤子时，一切看起来都像钉子 - 所以我想说这类问题可以使用 constraint programming 来解决.但这只是我的一点经验。

基本上，您有一个棋盘布局，每个“步骤”都有少量有效移动。目的是进入已知布局(升序)。

要“自动”执行此操作，您需要让程序搜索 寻找解决方案路径。执行此操作的步骤如下所示:

1. 根据当前布局，确定有效的移动。
2. 在完成每个有效 Action 后计算布局。
3. 检查是否有任何计算出的布局是解决方案；如果是，你就完了。
4. 如果所有走法都没有解决方案，则计算出所有新的有效走法，并从 1 开始重复。

这样做会遇到一些问题。首先，内存限制(制作大量的电路板布局副本可能行不通)。其次，时间/计算限制(可能需要很长时间才能找到解决方案)。您可以采取一些措施来至少将这些问题造成的损害降到最低。

1. 选择一个好的搜索方法。 Breadth-first而不是 Depth-first ， 例如。这将减少寻找解决方案所需的时间并降低内存需求。
2. 有些 Action 是“向后”的。例如，将方 block A 移动到 B，然后将方 block B 移动到 A(重复移动)。搜索这些“循环”既毫无意义又浪费资源，因此您要确保自己不这样做。
3. 搜索空间中可能存在对称性。我还没有解决你的具体问题，我不能给你具体的例子，但是 n-queens有一个关于特定于该问题的对称性的很好的部分 - 如果您试图在您的问题中找到对称性，它可能值得一读。

这可能会给您一些信息或开始寻找的想法。