The Best Rubik’s Cube Solvers and Cheats
Check out this great group of Rubik’s Cube Solvers. If you are having trouble solving it with the algorithms and notations, then get a few hints from a computer simulation!
3×3x3
http://wrongway.org/cube/solve.html
http://www.speedcubing.com/CubeSolver/CubeSolver.html
4×4x4
http://wrongway.org/mcube/solve.html
Rubik’s Cube Tutorial, Notation Tutorial, Algorithm
A great Rubik’s Cube Learning Tutorial, with notation, and algorithm solution. Check it out!
Upper Bounds Rubik’s Cube Algorithm
The first upper bounds were based on the ‘human’ algorithms. By combining the worst-case scenarios for each part of these algorithms, the typical upper bound was found to be around 100. The breakthrough was found by Morwen B. Thistlethwaite; details were published in Scientific American in 1981 by Douglas R. Hofstadter. The approaches to the cube that lead to algorithms with very few moves are based on group theory and on extensive computer searches.
Thistlethwaite’s idea was to divide the problem into subproblems. Where algorithms up to that point divided the problem by looking at the parts of the cube that should remain fixed, he divided it by restricting the type of moves you could execute. In particular he divided the cube group into the following chain of subgroups:
* G0 = L,R,F,B,U,D
* G1 = L,R,F,B,U2,D2
* G2 = L,R,F2,B2,U2,D2
* G3 = L2,R2,F2,B2,U2,D2
* G4 = {I}
Next he prepared tables for each of the right coset spaces G[i+1]\Gi. For each element he found a sequence of moves that took it to the next smaller group.
After these preparations he worked as follows. A random cube is in the general cube group G0. Next he found this element in the right coset space G1\G0. He applied the corresponding process to the cube. This took it to a cube in G1. Next he looked up a process that takes the cube to G2, next to G3 and finally to G4.
Although the whole cube group G0 is very large (~4.3×1019), the right coset spaces G1\G0, G2\G1, G3\G2 and G3 are much smaller. The coset space G2\G1 is the largest and contains only 1082565 elements. The number of moves required by this algorithm is the sum of the largest process in each step. In the original version this was 52.
This algorithm was improved by Herbert Kociemba in 1992. He reduced the number of intermediate groups to only two:
* G0 = L,R,F,B,U,D
* G1 = L,R,F2,B2,U2,D2
* G2 = {I}.
As with Thistlethwaite’s algorithm, he would search through the right coset space G1\G0 to take the cube to group G1. Next he searched the optimal solution for group G1. The searches in G1\G0 and G1 were both done with a method equivalent to IDA*. The search in G1\G0 needs at most 12 moves and the search in G1 at most 18 moves, as Michael Reid showed in 1995. By generating also suboptimal solutions that take the cube to group G1 and looking for short solutions in G1, you usually get much shorter overall solutions. Using this algorithm solutions are typically found of less than 21 moves, though there is no proof that it will always do so.
Next in 1995 it was proven by Michael Reid that using these two groups every position can be solved in at most 29 face turns, or in 42 quarter turns. This result was improved by Silviu Radu in 2005 to 40.
Using these group solutions combined with computer searches will generally quickly give very short solutions. But these solutions do not always come with a guarantee of their minimality. To search specifically for minimal solutions a new approach was needed.
In 1997 Richard Korf announced an algorithm with which he had optimally solved random instances of the cube. Of the ten random cubes he did, none required more than 18 face turns. The method he used is called IDA* and is described in his paper “Finding Optimal Solutions to Rubik’s Cube Using Pattern Databases.” Korf describes this method as follows
IDA* is a depth-first search that looks for increasingly longer solutions in a series of iterations, using a lower-bound heuristic to prune branches once a lower bound on their length exceeds the current iterations bound.
It works roughly as follows. First he identified a number of subproblems that are small enough to be solved optimally. He used:
1. The cube restricted to only the corners, not looking at the edges
2. The cube restricted to only 6 edges, not looking at the corners nor at the other edges.
3. The cube restricted to the other 6 edges.
Clearly the number of moves required to solve any of these subproblems is a lower bound for the number of moves you will need to solve the entire cube.
Given a random cube C, it is solved as iterative deepening. First all cubes are generated that are the result of applying 1 move to them. That is C * F, C * U, … Next, from this list, all cubes are generated that are the result of applying two moves. Then three moves and so on. If at any point a cube is found that needs too many moves based on the upper bounds to still be optimal it can be eliminated from the list.
Although this algorithm will always find optimal solutions there is no worst case analysis. It is not known how many moves this algorithm might need. An implementation of this algorithm can be found here.
In 2006, Silviu Radu further improved his methods to prove that every position can be solved in at most 27 face turns or 35 quarter turns.
In August 2007, Daniel Kunkle and Gene Cooperman used a supercomputer to show that all unsolved cubes can be solved in no more than 26 moves. Instead of attempting to solve each of the billions of variations explicitly, the computer was programmed to bring the cube to one of 15,000 states, each of which could be solved within a few extra moves. All were proved solvable in 29 moves, with most solvable in 26. Those that could not initially be solved in 26 moves were then solved explicitly, and shown that they too could be solved in 26 moves.
Rubik’s Cube Move Notation
Most 3×3×3 Rubik’s Cube solution guides use the same notation, originated by David Singmaster, to communicate sequences of moves. This is generally referred to as “Cube notation” or in some literature “Singmaster notation” (or variations thereof). Its relative nature allows algorithms to be written in such a way that they can be applied regardless of which side is designated the top or how the colours are organized on a particular Cube.
* F (Front): the side currently facing you
* B (Back): the side opposite the front
* U (Up): the side above or on top of the front side
* D (Down): the side opposite Up or on bottom
* L (Left): the side directly to the left of the front
* R (Right): the side directly to the right of the front
When an apostrophe follows a letter, it means to turn the face counter-clockwise a quarter-turn, while a letter without an apostrophe means to turn it a quarter-turn clockwise. Such an apostrophe mark is pronounced prime. A letter followed by a 2 (occasionally superscript) means to turn the face a half-turn (the direction does not matter).
This notation can also be used on the Pocket Cube, the Revenge, and the Professor, with additional notation. They not only have the F, B, L, R, U, D notation but also f, b, l, r, u, d. For example: (Rr)’ l2 f’
(Some solution guides, including Ideal’s official publication, The Ideal Solution, use slightly different conventions. Top and Bottom are used rather than Up and Down for the top and bottom faces, with Back being replaced by Posterior. + indicates clockwise rotation and - counterclockwise, with ++ representing a half-turn. However, alternative notations failed to catch on, and today the Singmaster scheme is used universally by those interested in the puzzle.)
Less often used moves include rotating the entire Cube or two-thirds of it. The letters x, y, and z are used to indicate that the entire Cube should be turned about one of its axes. The X-axis is the line that passes through the left and right faces, the Y-axis is the line that passes through the up and down faces, and the Z-axis is the line that passes through the front and back faces. (This type of move is used infrequently in most solutions, to the extent that some solutions simply say “stop and turn the whole Cube upside-down” or something similar at the appropriate point.)
Lowercase letters f, b, u, d, l, and r signify to move the first two layers of that face while keeping the remaining layer in place. This is of course equivalent to rotating the whole Cube in that direction, then rotating the opposite face back the same amount in the opposite direction, but is useful notation to describe certain triggers for speedcubing. Furthermore, M, E, and S (and respectively their lowercase for larger sized cubes), are used for inner-slice movements. M signifies turning the layer that is between L and R downward (clockwise if looking from the left side). E signifies turning the layer between U and D towards the right (counter-clockwise if looking from the top). S signifies turning the layer between F and B clockwise.
For example, the algorithm (or operator, or sequence) F2 U’ R’ L F2 R L’ U’ F2, which cycles three edge cubes in the top layer without affecting any other part of the Cube, means:
1. Turn the Front face 180 degrees
2. Turn the Up face 90 degrees counterclockwise
3. Turn the Right face 90 degrees counterclockwise
4. Turn the Left face 90 degrees clockwise
5. Turn the Front face 180 degrees
6. Turn the Right face 90 degrees clockwise
7. Turn the Left face 90 degrees counterclockwise
8. Turn the Up face 90 degrees counterclockwise
9. Finally, turn the front face 180 degrees.
For beginning students of the Cube, this notation can be daunting, and many solutions available online therefore incorporate animations that demonstrate the algorithms presented. For an example, see an animation of the above sequence.
4×4×4 and larger Cubes use slightly different notation to incorporate the middle layers. Generally speaking, upper case letters (FBUDLR) refer to the outermost portions of the cube (called faces). Lower case letters (fbudlr) refer to the inner portions of the cube (called slices). Again Ideal breaks rank by describing their 4×4×4 solution in terms of layers (vertical slices that rotate about the Z-axis), tables (horizontal slices), and books (vertical slices that rotate about the X-axis).
Rubik’s Cube Fun Facts
* It won a Spiel des Jahres Best Puzzle prize in 1980.
* From 1983 to 1984, a Ruby-Spears produced Saturday morning cartoon based upon the toy Rubik, the Amazing Cube aired on the American Broadcasting Company as part of a package program, “The Pac-Man/Rubik, The Amazing Cube Hour”.
* Saturday Night Live has had two commercial parodies for Rubik’s cube-esque products: Rubik’s Teeth (a pair of dentures that are multicoloured like a Rubik’s cube) and Rubik’s Grenade (a live hand grenade with a Rubik’s cube puzzle on the side that explodes if the puzzle isn’t solved correctly)
* In the movie UHF (starring “Weird Al” Yankovic), a blind man is shown solving a Rubik’s cube and asking the person next to him, “Is this it?” after every turn.
* In the 1998 movie The Wedding Singer, Holly Sullivan, played by Christine Taylor, plays with the cube unsuccessfully and gives up in frustration. She throws it down and says, “No one will ever solve that.”
* In episodes of The Simpsons, Homer Simpson can be seen playing with a Rubik’s Cube in the power plant where he works. This Rubik’s Cube almost caused the destruction of The City of Springfield, simply because he was fiddling with the cube while he was being trained what to do during a core melt-down. Also, in the episode HOMR, Homer is seen solving a basket full of Rubik’s cubes after a crayon is removed from his brain.
* In the movie Dude, Where’s My Car?, Seann William Scott’s character finds a Rubik’s Cube in the pocket of his new sportsuit. When he finally solves the cube, it transforms into the Continuum Transfunctioner referred by the aliens throughout the movie.
* In the movie The Pursuit of Happyness, Will Smith’s character solves a Rubik’s Cube during a cab ride and impresses a potential boss. Smith was trained by Tyson Mao, a world famous speed cuber who had become the first person to complete a Cube in less than two minutes while blindfolded.
* In The Goodies episode Holiday Grame Garden is seen playing with a giant Rubik’s Cube as he claims it helps him relax,he then puts it down and continues to turn his hands as if it were still there,then after finding he can’t relax he screams “I NEED THE CUBE! I NEED THE CUBE!”,he then picks up the cube,only for it to comically fall to pieces.
* In the third verse of the Group X song, “You Would Give Me Kiss (If I Were On Soccer Team)”, the lead singer expresses his discovery that he is skilled at the Rubik’s Cube, how he joins the Rubik’s Cube team, and his new popularity. The final chorus is altered to “I don’t need you and I don’t need your soccer team, ’cause now, bitch, I’m on the Rubik’s Cube team”.
* In an episode of The Golden Girls, Blanche Devereux is seen solving a Rubik’s Cube to everyone’s astonishment. It turns out later that she had once dated Rubik.
