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.
Asked
Active
Viewed 6.7k times
28
-
2The question is poorly phrased and the question that is voted "correct" is not, in fact, the correct answer. This shows why the "easiest algorithm to code" may not be what you want --- the program may never finish. And it shows why you need to be concerned with efficiency. – vy32 Aug 30 '09 at 21:54
-
You could just rephrase to, 'What is the easiest algorithm to code that gives results in our lifetime' :-) – Yannick Motton Aug 30 '09 at 22:11
7 Answers
57
Perform random operations until you get the right solution. The easiest algorithm and the least efficient.
Rushyo
- 7,495
- 4
- 35
- 42
-
43Hahaha with 4.33 * 10^19 permutations that is very truely the least efficient :-) – Yannick Motton Aug 30 '09 at 21:37
-
1@ Rushyo lol well played sir @Yannick can you explain how you calculated the permutations please? – kokokok Aug 30 '09 at 21:41
-
I am not very good at maths but am I right if I say because the 6 middle pieces will always stay in the same spot we have, 6*8 = 48 spots and 8 pieces of 6 different colors which can occupy those spots so the possible permutations will be (48!)/((8!)(8!)(8!)(8!)(8!)(8!)) – kokokok Aug 30 '09 at 21:47
-
The author is correct: this is the easiest algorithm to implement but also the worst performing algorithm. It will not find a solution in our lifetimes. – vy32 Aug 30 '09 at 21:53
-
_May_ not. It's entirely possible it would find the perfect solution first time... infinite monkeys. – Rushyo Aug 30 '09 at 21:55
-
And technically, the worst performing algorithm would be one that explicitly avoided the correct answer until a trigger told it to find the solution. – Rushyo Aug 30 '09 at 21:56
-
2Quoted from wikipedia: 'The original (3×3×3) Rubik's Cube has eight corners and twelve edges. There are 8! (40,320) ways to arrange the corner cubes. Seven can be oriented independently, and the orientation of the eighth depends on the preceding seven, giving 37 (2,187) possibilities. There are 12!/2 (239,500,800) ways to arrange the edges, since an odd permutation of the corners implies an odd permutation of the edges as well. Eleven edges can be flipped independently, with the flip of the twelfth depending on the preceding ones, giving 211 (2,048) possibilities.[19]' – Yannick Motton Aug 30 '09 at 22:06
-
11
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.
pppery
- 3,731
- 22
- 33
- 46
ire_and_curses
- 68,372
- 23
- 116
- 141
4
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
Yannick Motton
- 34,761
- 4
- 39
- 55
3
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.
Anthony Gatlin
- 4,407
- 5
- 37
- 53
1
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.
tk_y1275963
- 588
- 6
- 13
1
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.
Jay Dangar
- 3,271
- 1
- 16
- 35
-
Kudos for mentioning the Chen Shuang repository. Actually his code is full based on the Kociemba's algorithm, which is one of the best programming pieces oever. – Lucas Sousa Aug 04 '20 at 19:59
0
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.
