有一个相对简单的Java算法来解决魔方，效率也很重要但次要考虑因素。
魔方最容易编写的算法是什么？
28
- kokokok
2
2该问题的措辞不清，被投票“正确”的答案实际上并不正确。这表明为什么“最容易编写的算法”可能不是您想要的---程序可能永远不会完成。因此需要关注效率。 - vy32
你可以简单地改述为：“在我们的有生之年内，编写起来最容易且能够得出结果的算法是什么？” :-) - Yannick Motton
7个回答
57
随机进行操作，直到获得正确的解决方案。这是最简单但效率最低的算法。
- Rushyo
8
43哈哈哈，有4.33 * 10^19种排列方式，那确实是最低效的 :-) - Yannick Motton
1@ Rushyo 哈哈，干得好先生。
@ Yannick 你能解释一下你是如何计算排列组合的吗？ - kokokok
作者是正确的：这是最容易实现但也是最糟糕的性能算法。它将无法在我们的有生之年中找到解决方案。 - vy32
2引用自维基百科：“原始的（3×3×3）魔方有八个角和十二个边。有8!（40,320）种方法可以排列角块。其中七个可以独立定向，第八个的定向取决于前面七个，因此有37（2,187）种可能性。有12！/2（239,500,800）种方法可以排列边缘，因为角落的奇排列意味着边缘的奇排列。十一个边缘可以独立翻转，第十二个的翻转取决于前面的边缘，因此有211（2,048）种可能性。” - Yannick Motton
你不能否认这个！ - Derek 朕會功夫
显示剩余3条评论
11
我找到的最简单的非平凡算法是：
http://www.chessandpoker.com/rubiks-cube-solution.html
这看起来编码起来不太难。Yannick M.的回答中提到的链接也很好，但是“交叉”步骤的解决方案对我来说似乎有点更加复杂。
有许多开源的求解器实现，您可能想要查看一下。这里有一个Python实现。这个Java小程序也包括一个求解器，并且源代码可用。还有一个Javascript求解器，同样有可下载的源代码。
Anthony Gatlin的回答提出了关于Prolog非常适合这项任务的重要观点。这里有一篇详细的文章，介绍如何编写自己的Prolog求解器。它使用的启发式方法特别有趣。
- ire_and_curses
4
建议查看：http://peter.stillhq.com/jasmine/rubikscubesolution.html
该网页提供了一个图形化算法，用于解决3x3x3魔方。
- Yannick Motton
3
我理解你的问题是关于Java的，但实际上，像Prolog这样的语言更适合解决魔方问题。不过我猜这可能是为了一个课程，你可能没有选择工具的余地。
- Anthony Gatlin
2
很遗憾，对于这门课程我必须使用Java来完成。 - kokokok
2答案很明显：用Java编写一个Prolog解释器！ - John Fouhy
1
你可以通过BFS（广度优先搜索）来实现。我认为它的实现并不难（在图的类别下，它是最简单的算法之一）。通过使用名为队列的数据结构进行操作，你将真正需要做的是构建一个BFS树，并找到从给定条件到期望条件的所谓最短路径。这种算法的缺点是效率不够高（即使对于2x2x2的立方体，没有任何修改，所需时间也约为5分钟）。但你总可以找到一些技巧来提高速度。
坦白说，这是麻省理工学院课程“算法导论”的作业之一。以下是作业链接：http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/assignments/MIT6_006F11_ps6.pdf。他们有几个库可以帮助你可视化它，并帮助你避免不必要的努力。
坦白说，这是麻省理工学院课程“算法导论”的作业之一。以下是作业链接：http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/assignments/MIT6_006F11_ps6.pdf。他们有几个库可以帮助你可视化它，并帮助你避免不必要的努力。
- tk_y1275963
1
供您参考，您可以查看这个Java实现。--> 使用两阶段算法解决魔方。我已经尝试过这段代码，它也可以正常工作。
- Jay Dangar
1
表扬提到陈爽的代码库。实际上，他的代码完全基于Kociemba算法，这是最好的编程之一。 - Lucas Sousa
0
一种解决方案是同时运行所有可能的路径，虽然听起来很愚蠢，但是这是有逻辑的 - 超过99%的可能的打乱情况都可以在不到20步内解决。这意味着尽管您需要循环处理大量的可能性，但最终您仍将成功找到解法。基本上，这将通过将打乱的魔方作为第一步来实现。然后，您将为第一个魔方上每个可能的移动存储在变量中的新魔方。对于这些新魔方，您要做的是相同的事情。每次进行可能的移动后，检查它是否已完成，如果是，则找到了解法。为确保您拥有解决方案，您需要在每个魔方上添加额外的数据，以说明达到该阶段所做的移动。
- TOGD
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接