如何开始编码大脑的8益智游戏，以计算最少的动作

Question

我设法解决这个问题与RNG蛮力大约需要4-5秒找到最佳的解决方案，即使工作网格是一个3×3。

我想知道我如何才能生成蛮力在没有暴力的情况下发现的相同动作。

我会列出2个例子，并找到解决方案蛮力。我试图分析解决方案，找出它为什么选择他们，我什么都不知道。

此游戏的工作原理是利用在两个方向（从右到左）

左到右循环旋转做到这一点
If [a, b, c] then [b, c, a]
从右到左循环旋转做到这一点
循环旋转（左到右）和If [a, b, c] then [c, a, b]

游戏数据可以说是这样的（它可以是1至9中的任一置换）
例如
Data = 7, 2, 6, 1, 5, 4, 3, 8, 9

我可以通过8种不同的方式移动桌子上的棋子。
1）基于行的循环旋转（从左到右）。
2）基于行循环旋转（从右到左）。
3）基于列的顶部到底部。
4）根据列自下而上。
现在5到8不需要列或行，因为它们是对角设置的。
5）从左上到右下（从左到右）。
6）从左上到右下（从右到左）。
7）右上角到左下角（从左到右）。
8）右上角到左下角（右到左）。

的数据被加载为以下

• 007 | 002 | 006
• 001 | 005 | 004
• 003 | 008 | 009

解蛮力被迫：
1）。 [右上]到[左下]（右到左）
2）。从下到上，列：0
3）。从左到右，行：1

下面是解simlutated

1）。[右上]到[左下]（右到左）

• 007 | 002 |
• 001 | | 004
• | 008 | 009

2）。底部到顶部，列：0

• | 002 | 003
• | 006 | 004
• | 008 | 009

3）。从左到右排：1

• 001 | 002 | 003
• | |
• 007 | 008 | 009

下面是实施例2这需要6点移动到解决

• 009 | 008 | 007
• 006 | 005 | 004
• 003 | 002 | 001

解决方法：（6步）
1）。 [右上]到[左下]（右到左）
2）。从上到下，列：1
3）。从下到上，列：0
4）。 [左上]到[右下]（从左到右）
5）。从左到右，行：1
6）。从右到左，行：2

所以这是一个非常简单的谜题，但找到高效的解决方案并不是一项简单的任务。 有人可以指引我在正确的方向。

Answer 1

如果你想尝试一些比BFS更好的东西（也许你想要毕业到14个难题或什么东西），试试看启发式搜索方法，如A *（发音为A-星）。这些算法使用某种规则作为评估哪些路径可能成功的代理。在A *的情况下，最坏的情况是它会减少到广度优先搜索。

具有挑战性的部分是想出一个很好的启发式使用。对于A *，您需要一种永不过高估计路径的启发式方法，只会低估。因此，通常可以通过想象最佳情况或放松对问题的限制来提出良好的启发式方法。例如，如果你试图找到从一个点到另一个点的最短路径，点之间的直线距离是一个很好的启发。在8拼图的情况下，你需要某种度量标准，随着你越来越接近解决这个难题而逐渐改善。

Answer 2

而不是使用您的随机数发生器解决方案，更有条不紊。

A breadth first search（BFS）易于实施，并且可以保证您找到最佳解决方案。 BFS只是测试当前状态的所有后续状态，然后递归地测试所有这些状态的所有后续状态，直到找到解决方案。更直接地，BFS测试解决方案长度为1的所有移动，然后测试解决方案长度为2的所有移动等，直到找到解决方案。

天真的实现有多次测试相同位置的下降，但是您可以通过在搜索中存储所有以前的状态及其深度并跳过存储值低于当前值的任何重复深度。 BFS有很多改进，但对于这个游戏的简单性（只有9个状态），用更复杂的算法看不出有多少改进。