我在思考什么是找到这个谜题所有解的最佳算法。
http://1cup1coffee.com/puzzle/endice/
回溯法是否可以作为解决此问题的一种方法，或者你能推荐其他方法吗？
谢谢。
谢谢。
一个骰子问题的算法
3
- excray
3
有趣。我不知道Armor Games也制作益智游戏。我正在玩它。(顺便说一句，我认为先做最小的骰子数字将是一个很好的启发式方法。)编辑：哦，骰子可以推动骰子吗？这是增加复杂性的好方法。 - Xavier Ho
另一个评论：我发现“困难级别”（20-30级）比15-19级要容易得多，因为他们给我们的骰子数量更多，有时我们可以使用几个6点骰子。我认为解决这个问题的算法可以简单地使用A*搜索，其中您的启发式是骰子移动的奇偶性加上剩余总移动次数以某种方式组合。 - Xavier Ho
该链接指向一个没有受信任安全证书的网站。Grr. - Kimball Robinson
2个回答
1
回溯法绝对是如果你想要所有的解决方案的方法。BFS / A* / Dijkstra 等等可能会起作用（需要证明），但无论如何它们很可能不会给你所有的解决方案。
在这里使用回溯法不应该花费太长时间，因为可玩区域非常小，而且你有相对较少的棋子和移动次数，这允许使用良好的启发式算法。
在这里使用回溯法不应该花费太长时间，因为可玩区域非常小，而且你有相对较少的棋子和移动次数，这允许使用良好的启发式算法。
- IVlad
1
为了避免搜索每个可达位置，您需要一种快速确定位置是否无解的方法。您无法快速排除所有无解位置，但可以排除其中许多。
一个要检查的事情是对于每个骰子D和每个孔H，是否可能让骰子D到达孔H。即使这也不容易准确地弄清楚。作为保守边界，您可以将所有骰子上剩余数字相加，假设D还有那么多的移动量（因为每个这样的移动都可以理论上推动D），然后看看D是否能够到达H。稍微不那么保守的边界是，您可以将所有多余的移动分配给最接近能够推动D的骰子E，然后看看D（在E的帮助下）是否能够到达H。
一旦确定了哪些骰子仍然可能到达哪些孔，如果有一个骰子无法到达任何孔，或者有一个孔无法被任何骰子到达，则该位置无解。同样，如果有N个骰子无法到达N个不同的孔，或者有H个孔无法被N个不同的骰子到达，则该位置无解。
这种启发式方法不能完全解决您的问题，但它可以使某些范围的棋盘搜索空间更易于管理。
一个要检查的事情是对于每个骰子D和每个孔H，是否可能让骰子D到达孔H。即使这也不容易准确地弄清楚。作为保守边界，您可以将所有骰子上剩余数字相加，假设D还有那么多的移动量（因为每个这样的移动都可以理论上推动D），然后看看D是否能够到达H。稍微不那么保守的边界是，您可以将所有多余的移动分配给最接近能够推动D的骰子E，然后看看D（在E的帮助下）是否能够到达H。
一旦确定了哪些骰子仍然可能到达哪些孔，如果有一个骰子无法到达任何孔，或者有一个孔无法被任何骰子到达，则该位置无解。同样，如果有N个骰子无法到达N个不同的孔，或者有H个孔无法被N个不同的骰子到达，则该位置无解。
这种启发式方法不能完全解决您的问题，但它可以使某些范围的棋盘搜索空间更易于管理。
- mathmike
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接