Java 最简单的魔方编码算法？

Easiest to code algorithm for Rubik's cube?

提问by kokokok

What would be a relatively easy algorithm to code in Java for solving a Rubik's cube. Efficiency is also important but a secondary consideration.

用 Java 编写代码来解决魔方问题的相对简单的算法是什么。效率也很重要，但次要考虑。

采纳答案by ire_and_curses

The simplest non-trivialalgorithm I've found is this one:

我发现的最简单的非平凡算法是这个：

http://www.chessandpoker.com/rubiks-cube-solution.html

http://www.chessandpoker.com/rubiks-cube-solution.html

It doesn't look too hard to code up. The link mentioned in Yannick M.'s answerlooks good too, but the solution of 'the cross' step looks like it might be a little more complex to me.

编码看起来并不难。Yannick M. 的回答中提到的链接看起来也不错，但是“交叉”步骤的解决方案对我来说似乎有点复杂。

There are a number of open source solver implementations which you might like to take a look at. Here's a Python implementation. This Java appletalso includes a solver, and the source code is available. There's also a Javascript solver, also with downloadable source code.

您可能想查看许多开源求解器实现。这是一个Python 实现。这个Java 小程序还包括一个求解器，并且提供了源代码。还有一个Javascript solver，也有可下载的源代码。

Anthony Gatlin's answermakes an excellent point about the well-suitedness of Prolog for this task. Here's a detailed article about how to write your own Prolog solver. The heuristics it uses are particularly interesting.

Anthony Gatlin 的回答很好地说明了 Prolog 非常适合这项任务。这是一篇关于如何编写自己的Prolog 求解器的详细文章。它使用的启发式方法特别有趣。

回答by Rushyo

Perform random operations until you get the right solution. The easiest algorithm and the least efficient.

执行随机操作，直到获得正确的解决方案。最简单的算法，效率最低。

回答by Yannick Motton

Might want to check out: http://peter.stillhq.com/jasmine/rubikscubesolution.html

可能想看看：http: //peter.stillhq.com/jasmine/rubikscubesolution.html

Has a graphical representation of an algorithm to solve a 3x3x3 Rubik's cube

具有求解 3x3x3 魔方的算法的图形表示

回答by Anthony Gatlin

I understand your question is related to Java, but on a practical note, languages like Prolog are much better suited problems like solving a Rubik's cube. I assume this is probably for a class though and you may have no leeway as to the choice of tool.

我知道您的问题与 Java 相关，但实际上，像 Prolog 这样的语言更适合解决魔方等问题。我认为这可能是针对一门课程的，您可能没有选择工具的余地。

回答by tk_y1275963

You can do it by doing BFS(Breadth-First-Search). I think the implementation is not that hard( It is one of the simplest algorithm under the category of the graph). By doing it with the data structure called queue, what you will really work on is to build a BFS tree and to find a so called shortest path from the given condition to the desire condition. The drawback of this algorithm is that it is not efficient enough( Without any modification, even to solver a 2x2x2 cubic the amount time needed is ~5 minutes). But you can always find some tricks to boost the speed.

您可以通过执行 BFS（广度优先搜索）来实现。我认为实现并不难（它是图类别下最简单的算法之一）。通过使用称为队列的数据结构来完成它，您真正要做的是构建一个 BFS 树并找到从给定条件到期望条件的所谓最短路径。该算法的缺点是效率不够高（未经任何修改，即使求解 2x2x2 立方体所需的时间约为 5 分钟）。但是你总能找到一些技巧来提高速度。

To be honest, it is one of the homework of the course called "Introduction of Algorithm" from MIT. Here is the homework's link: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/assignments/MIT6_006F11_ps6.pdf. They have a few libraries to help you to visualize it and to help you avoid unnecessary effort.

老实说，这是麻省理工学院《算法导论》课程的作业之一。这是作业的链接：http: //ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/assignments/MIT6_006F11_ps6.pdf。他们有一些库可以帮助您将其可视化并帮助您避免不必要的努力。

回答by Jay Dangar

For your reference, you can certainly look at this java implementation. --> Uses two phase algorithm to solve rubik's cube. And have tried this code and it works as well.

供您参考，您当然可以查看此 java 实现。--> 使用两阶段算法来解决魔方。并尝试过这段代码，它也能正常工作。

回答by TOGD

One solution is to I guess simultaneously run all possible routes. That does sound stupid but here's the logic - over 99% of possible scrambles will be solvable in under 20 moves. This means that although you cycle through huge numbers of possibilities you are still going to do it eventually. Essentially this would work by having your first step as the scrambled cube. Then you would have new cubes stored in variables for each possible move on that first cube. For each of these new cubes you do the same thing. After each possible move check if it is complete and if so then that is the solution. Here to make sure you have the solution you would need an extra bit of data on each Rubiks cube saying the moves done to get to that stage.

一种解决方案是我猜同时运行所有可能的路线。这听起来确实很愚蠢，但这是逻辑 - 超过 99% 的可能争夺将在 20 步以内解决。这意味着，尽管您在大量可能性中循环，但最终您仍会这样做。从本质上讲，这可以通过将您的第一步作为加扰的立方体来工作。然后，对于第一个立方体上的每个可能的移动，您都会将新的立方体存储在变量中。对于这些新立方体中的每一个，您都执行相同的操作。在每个可能的移动之后检查它是否完整，如果是，那么这就是解决方案。为了确保您拥有解决方案，您需要在每个魔方立方体上提供额外的数据，说明为达到该阶段所做的动作。