Easiest to code algorithm for Rubik's cube?

Question

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.

Answer 1

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

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

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

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 applet also includes a solver, and the source code is available. There's also a Javascript solver, also with downloadable source code.

Anthony Gatlin's answer makes 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.

Answer 2

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

Answer 3

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

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

Answer 4

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.

Answer 5

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.

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.

Answer 6

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.

Answer 7

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.