What is known about bounds on solving Rubik's cube?
competition/games/rubiks/rubiks.cube Added material
Problem
What is known about bounds on solving Rubik's cube?
Show solution
The "official" world record was set by Minh Thai at the 1982 World
Championships in Budapest Hungary, with a time of 22.95 seconds.
Keep in mind mathematicians provided standardized dislocation patterns
for the cubes to be randomized as much as possible.
The fastest cube solvers from 19 different countries had 3 attempts each
to solve the cube as quickly as possible. Minh and several others have
unofficially solved the cube in times between 16 and 19 seconds.
However, Minh averages around 25 to 26 seconds after 10 trials, and my
best average of ten trials is about 27 seconds (although it is usually
higher).
Consider that in the World Championships 19 of the world's fastest cube
solvers each solved the cube 3 times and no one solved the cube in less
than 20 seconds...
God's algorithm is the name given to an as yet (as far as I know)
undiscovered method to solve the rubik's cube in the least number of
moves; as opposed to using 'canned' moves.
The known lower bound is 18 moves. This is established by looking at
things backwards: suppose we can solve a position in N moves. Then by
running the solution backwards, we can also go from the solved position
to the position we started with in N moves. Now we count how many
sequences of N moves there are from the starting position, making
certain that we don't turn the same face twice in a row:
N=0: 1 (empty) sequence;
N=1: 18 sequences (6 faces can be turned, each in 3 different ways)
N=2: 18*15 sequences (take any sequence of length 1, then turn any of the
five faces which is not the last face turned, in any of 3
different ways); N=3: 18*15*15 sequences (take any sequence of
length 2, then turn any of the five faces which is not the last
face turned, in any of 3 different ways); : : N=i: 18*15^(i-1)
sequences.
So there are only 1 + 18 + 18*15 + 18*15^2 + ... + 18*15^(n-1)
sequences of moves of length n or less. This sequence sums to
(18/14)*(15^n - 1) + 1. Trying particular values of n, we find that
there are about 8.4 * 10^18 sequences of length 16 or less, and about
1.3 times 10^20 sequences of length 17 or less.
Since there are 2^10 * 3^7 * 8! * 12!, or about 4.3 * 10^19, possible
positions of the cube, we see that there simply aren't enough sequences
of length 16 or less to reach every position from the starting
position. So not every position can be solved in 16 or less moves -
i.e. some positions require at least 17 moves.
This can be improved to 18 moves by being a bit more careful about
counting sequences which produce the same position. To do this, note
that if you turn one face and then turn the opposite face, you get
exactly the same result as if you'd done the two moves in the opposite
order. When counting the number of essentially different sequences of N
moves, therefore, we can split into two cases:
(a) Last two moves were not of opposite faces. All such sequences can be
obtained by taking a sequence of length N-1, choosing one of the 4 faces
which is neither the face which was last turned nor the face opposite
it, and choosing one of 3 possible ways to turn it. (If N=1, so that the
sequence of length N-1 is empty and doesn't have a last move, we
can choose any of the 6 faces.)
(b) Last two moves were of opposite faces. All such sequences can be
obtained by taking a sequence of length N-2, choosing one of the 2
opposite face pairs that doesn't include the last face turned, and
turning each of the two faces in this pair (3*3 possibilities for how it
was turned). (If N=2, so that the sequence of length N-2 is empty and
doesn't have a last move, we can choose any of the 3 opposite face
pairs.)
This gives us a recurrence relation for the number X_N of sequences of
length N:
N=0: X_0 = 1 (the empty sequence)
N=1: X_1 = 18 * X_0 = 18
N=2: X_2 = 12 * X_1 + 27 * X_0 = 243
N=3: X_3 = 12 * X_2 + 18 * X_1 = 3240
:
:
N=i: X_i = 12 * X_(i-1) + 18 * X_(i-2)
If you do the calculations, you find that X_0 + X_1 + X_2 + ... + X_17 is
about 2.0 * 10^19. So there are fewer essentially different sequences of
moves of length 17 or less than there are positions of the cube, and so some
positions require at least 18 moves.
The upper bound of 50 moves is I believe due to Morwen Thistlethwaite, who
developed a technique to solve the cube in a maximum of 50 moves. It
involved a descent through a chain of subgroups of the full cube group,
starting with the full cube group and ending with the trivial subgroup
(i.e. the one containing the solved position only). Each stage involves a
careful examination of the cube, essentially to work out which coset of the
target subgroup it is in, followed by a table look-up to find a sequence to put
it into that subgroup. Needless to say, it was not a fast technique!
But it was fascinating to watch, because for the first three quarters or
so of the solution, you couldn't really see anything happening - i.e. the
position continued to appear random! If I remember correctly, one of the
final subgroups in the chain was the subgroup generated by all the double
twists of the faces - so near the end of the solution, you would suddenly
notice that each face only had two colours on it. A few moves more and the
solution was complete. Completely different from most cube solutions, in
which you gradually see order return to chaos: with Morwen's solution, the
order only re-appeared in the last 10-15 moves.
* Mark's Update/Comments ----------------------------------------------
* Despite some accounts of Thistlethwaite's method, it is possible to
* follow the progression of his algorithm. Clearly after Stage 2 is
* completed the L and R faces will have L and R colours on them only.
* After Stage 3 is complete the characteristics of the square's group
* is clearly visible on all 6 sides. It is harder to understand what
* is accomplished in Stage 1.
*
* ---------------------------------------------------------------------
With God's algorithm, of course, I would expect this effect to be even more
pronounced: someone solving the cube with God's algorithm would probably
look very much like a film of someone scrambling the cube, run in
reverse!
Finally, something I'd be curious to know in this context: consider the
position in which every cubelet is in the right position, all the corner
cubelets are in the correct orientation, and all the edge cubelets are
"flipped" (i.e. the only change from the solved position is that every edge
is flipped). What is the shortest sequence of moves known to get the cube
into this position, or equivalently to solve it from this position? (I know
of several sequences of 24 moves that do the trick.)
* Mark's Update/Comments ----------------------------------------------
*
* This is from my file cmoves.txt which includes the best known
* sequences for interesting patterns:
*
* p3 12 flip R1 L1 D2 B3 L2 F2 R2 U3 D1 R3 D2 F3 B3 D3 F2 D3 (20)
* R2 U3 F2 D3
*
* ---------------------------------------------------------------------
The reason I'm interested in this particular position: it is the unique
element of the centre of the cube group. As a consequence, I vaguely suspect
(I'd hardly like to call it a conjecture :-) it may lie "opposite" the
solved position in the cube graph - i.e. the graph with a vertex for each
position of the cube and edges connecting positions that can be transformed
into each other with a single move. If this is the case, then it is a good
candidate to require the maximum possible number of moves in God's
algorithm.
-- David Seal dseal@armltd.co.uk
To my knowledge, no one has ever demonstrated a specific cube position
that takes 15 moves to solve. Furthermore, the lower bound is known to
be greater than 15, due to a simple proof.
* ---------------------------------------------------------------------
* Mark> Definitely sequences exist in the square's group of length 15
* > e.g. Antipode 2 R2 B2 D2 F2 D2 F2 T2 L2 T2 D2 F2 T2 L2 T2 B2
* ---------------------------------------------------------------------
The way we know the lower bound is by working backwards counting how
many positions we can reach in a small number of moves from the solved
position. If this is less than 43,252,003,274,489,856,000 (the total
number of positions of Rubik's cube) then you need more than that
number of moves to reach the other positions of the cube. Therefore,
those positions will require more moves to solve.
The answer depends on what we consider a move. There are three common
definitions. The most restrictive is the QF metric, in which only a
quarter-turn of a face is allowed as a single move. More common is
the HF metric, in which a half-turn of a face is also counted as a
single move. The most generous is the HS metric, in which a quarter-
turn or half-turn of a central slice is also counted as a single move.
These metrics are sometimes called the 12-generator, 18-generator, and
27-generator metrics, respectively, for the number of primitive moves.
The definition does not affect which positions you can get to, or even
how you get there, only how many moves we count for it.
The answer is that even in the HS metric, the lower bound is 16,
because at most 17,508,850,688,971,332,784 positions can be reached
within 15 HS moves. In the HF metric, the lower bound is 18, because
at most 19,973,266,111,335,481,264 positions can be reached within 17
HF moves. And in the QT metric, the lower bound is 21, because at
most 39,812,499,178,877,773,072 positions can be reached within 20 QT
moves.
Lately in this conference I've noted several messages related to Rubik's
Cube and Square 1. I've been an avid cube fanatic since 1981 and I've
been gathering cube information since.
Around Feb. 1990 I started to produce the Domain of the Cube Newsletter,
which focuses on Rubik's Cube and all the cube variants produced to
date. I include notes on unproduced prototype cubes which don't even
exist, patent information, cube history (and prehistory), computer
simulations of puzzles, etc. I'm up to the 4th issue.
Anyways, if you're interested in other puzzles of the scramble by
rotation type you may be interested in DOTC. It's available free to
anyone interested. I am especially interested in contributing articles
for the newsletter, e.g. ideas for new variants, God's Algorithm.
Anyone ever write a Magic Dodecahedron simulation for a computer?
Drop me a SASE (say empire size) if you're interested in DOTC or if you
would like to exchange notes on Rubik's Cube, Square 1 etc.
I'm also interested in exchanging puzzle simulations, e.g. Rubik's Cube,
Twisty Torus, NxNxN Simulations, etc, for Amiga and IBM computers. I've
written several Rubik's Cube solving programs, and I'm trying to make
the definitive puzzle solving engine. I'm also interested in AI programs
for Rubik's Cube and the like.
Ideal Toy put out the Rubik's Cube Newsletter, starting with
issue #1 on May 1982. There were 4 issues in all.
They are: #1, May 1982
#2, Aug 1982
#3, Winter 1983
#4, Aug 1983
There was another sort of magazine, published in several languages
called Rubik's Logic and Fantasy in space. I believe there were 8
issues in all. Unfortunately I don't have any of these! I'm willing
to buy these off anyone interesting in selling. I would like to get the
originals if at all possible...
I'm also interested in buying any books on the cube or related puzzles.
In particular I am _very_ interested in obtaining the following:
Cube Games Don Taylor, Leanne Rylands
Official Solution to Alexander's Star Adam Alexander
The Amazing Pyraminx Dr. Ronald Turner-Smith
The Winning Solution Minh Thai
The Winning Solution to Rubik's Revenge Minh Thai
Simple Solutions to Cubic Puzzles James G. Nourse
I'm also interested in buying puzzles of the mechanical type.
I'm still missing the Pyraminx Star (basically a Pyraminx with more tips
on it), Pyraminx Ball, and the Puck.
If anyone out here is a fellow collector I'd like to hear from you.
If you have a cube variant which you think is rare, or an idea for a
cube variant we could swap notes.
I'm in the middle of compiling an exhaustive library for computer
simulations of puzzles. This includes simulations of all Uwe Meffert's
puzzles which he prototyped but _never_ produced. In fact, I'm in the
middle of working on a Pyraminx Hexagon solver. What? Never heard of it?
Meffert did a lot of other puzzles which never were made.
I invented some new "scramble by rotation" puzzles myself. My favourite
creation is the Twisty Torus. It is a torus puzzle with segments (which
slide around 360 degrees) with multiple rings around the circumference.
The computer puzzle simulation library I'm forming will be described
in depth in DOTC #4 (The Domain of the Cube Newsletter). So if you
have any interesting computer puzzle programs please email me and
tell me all about them!
Also to the people interested in obtaining a subscription to DOTC,
who are outside of Canada (which it seems is just about all of you!)
please don't send U.S. or non-Canadian stamps (yeah, I know I said
Self-Addressed Stamped Envelope before). Instead send me an
international money order in Canadian funds for $6. I'll send you
the first 4 issues (issue #4 is almost finished).
Mark Longridge
Address: 259 Thornton Rd N, Oshawa Ontario Canada, L1J 6T2
Email: mark.longridge@canrem.com
One other thing, the six bucks is not for me to make any money. This
is only to cover the cost of producing it and mailing it. I'm
just trying to spread the word about DOTC and to encourage other
mechanical puzzle lovers to share their ideas, books, programs and
puzzles. Most of the programs I've written and/or collected are
shareware for C64, Amiga and IBM. I have source for all my programs
(all in C or Basic) and I am thinking of providing a disk with the
4th issue of DOTC. If the response is favourable I will continue
to provide disks with DOTC.
-- Mark Longridge <mark.longridge@canrem.com> writes:
It may interest people to know that in the latest issue of "Cubism For Fun" %
(# 28 that I just received yesterday) there is an article by Herbert Kociemba
from Darmstadt. He describes a program that solves the cube. He states that
until now he has found no configuration that required more than 21 turns to
solve.
He gives a 20 move manoeuvre to get at the "all edges flipped/
all corners twisted" position:
DF^2U'B^2R^2B^2R^2LB'D'FD^2FB^2UF'RLU^2F'
or in Varga's parlance:
dofitabiribirilobadafodifobitofarolotifa
Other things #28 contains are an analysis of Square 1, an article about
triangular tilings by Martin Gardner, and a number of articles about other
puzzles.
--
% CFF is a newsletter published by the Dutch Cubusts Club NKC.
Secretary:
Anneke Treep
Postbus 8295
6710 AG Ede
The Netherlands
Membership fee for 1992 is DFL 20 (about$ 11).
--
-- dik t. winter <dik@cwi.nl>
References:
Mathematical Papers
-------------------
Rubik's Revenge: The Group Theoretical Solution
Mogens Esrom Larsen A.M.M. Vol. 92 No. 6, June-July 1985, pages
381-390
Rubik's Groups
E. C. Turner & K. F. Gold, American Mathematical Monthly,
vol. 92 No. 9 November 1985, pp. 617-629.
Cubelike Puzzles - What Are They and How Do You Solve Them?
J.A. Eidswick A.M.M. Vol. 93 No. 3 March 1986, pp 157-176
The Slice Group in Rubik's Cube, David Hecker, Ranan Banerji
Mathematics Magazine, Vol. 58 No. 4 Sept 1985
The Group of the Hungarian Magic Cube
Chris Rowley Proceedings of the First Western Austrialian
Conference on Algebra, 1982
Books
-----
Rubik's Cubic Compendium
Erno Rubik, Tamas Varga, et al, Edited by David Singmaster
Oxford University Press, 1987
Enslow Publishers Inc
Additional material
[ Editor: Herbert Kociemba's program Cube Explorer (version 1.5, 1997,
for Windows 95) implements his Two-Phase Algorithm. According to its
home page, given a scrambled cube it quickly provides a solving
sequence of 19 moves on average, usually only one or two moves more
than the perfect solution, and occasionally finds a solution that is
provably optimal. It also searches for "pretty patterns" with short
generating maneuvers, for example this 15-move generator: ]
L2 D U L2 D2 R2 D' L F' D F2 D' F L' R2 (15)
-- Herbert Kociemba <kociemba@hrz1.hrz.th-darmstadt.de> [ Editor:
source is the Cube Explorer home page (1997), summarized above ]
[ Editor: a 1997 pointer to solutions on the Web (address as posted
then): ]
If you are [ Editor: having trouble with Rubik puzzles ], then check out "Cubic
Puzzles - the SIMPLEST Solution" page at
http://www.nether.net/~sterling/solves.html. There, you'll find COMPLETE
solutions to the Pyraminx, Megaminx, Skewb, and NxNxN cubes.
-- Tim Browne <ue451@freenet.Victoria.BC.CA>
[ Editor: from a thread asking for the minimum number of moves that
solves every position, and whether a cube can be made unsolvable by
taking it apart and reassembling it. ]
"Kevin P. Smith" <kpsmith@cookie.engr.sgi.com> writes:
I have no idea about the minimum number of moves required (I had
heard rumors on the order of 22-23 before, but had no reason to
believe the source was accurate)
There is a known pattern that is believed to be the most distant from
the start, namely the superflip (flip all 12 edge pieces). That
position is known to require 22 turns (I believe by the quarter-turn
metric).
However, it is very easy to make a rubik's cube unsolvable by
rotating just one of the corner pieces or flipping just one of the
side pieces. I think that there are six fundamentally different
configurations. So if you broke a rubik's cube and put the pieces
back together in a random configuration, I think there is a 1/6
chance that it will be solvable.
[Editor: several words ending in "-ble", "-ly" or "cube" appear
garbled as "...gry" in the original]
There are 12 different orbits of the cube, so if you were to take it
apart and reassemble it at random, there is a 1/12 chance of being
able to solve the result.
-- Buddha Buck <bmbuck@acsu.buffalo.edu>
[ Editor: the 12 orbits come from 3 corner twists x 2 edge flips x 2
permutation parities. The superflip (the "12 flip" above) is given
in this entry with a sequence of 20 moves counting half turns as one
move; in the quarter-turn metric each half turn counts as two. ]
[ Editor: postings of 1993-1997 that update or add to the entry above.
They are in date order; the figures are as of their dates. ]
Bounds on God's algorithm (1993-1994)
-------------------------------------
It is a pity my corrections apparently do not make it to the archives.
Here come some:
> The known lower bound is 18 moves.
Just the last weeks I have found configurations that require 19 moves.
So the current proven lowerbound is 19.
> He gives a 20 move manoeuvre to get at the "all edges flipped/
> all corners twisted" position:
> DF^2U'B^2R^2B^2R^2LB'D'FD^2FB^2UF'RLU^2F'
It was this configuration that requires at least 19 moves (proven with my
program that implements the algorithm). That took about 2 weeks of computer
time for 3 computers (SGI Indigo R4k).
> % CFF is a newsletter published by the Dutch Cubusts Club NKC.
> Secretary:
> Anneke Treep
> Postbus 8295
> 6710 AG Ede
> The Netherlands
> Membership fee for 1992 is DFL 20 (about$ 11).
This information is severely outdated. Information about the newsletter
can be obtained from
Gerald Maurice
Groen van Prinstererstraat 7-2
1051 ED Amsterdam
The Netherlands
e-mail: gm@phys.uva.nl
Current membership fee is DFL 25.
-- Dik T. Winter <dik@cwi.nl> (September 1993)
Recently my address was given as being the secretary's of the
Dutch Cube Club. This is not correct (I'm the president)! Please note:
The Dutch Cube Club was founded on September 26, 1981 and has survived
the fading of the fad. Now, the Club is interested in all kinds of
puzzles.
A newsletter is published 3 times a year. To obtain a membership
application form, please contact the secretary by sending a self-addressed
envelope with reply coupon to:
Frits Gobel
Schubertlaan 28
7522 JS Enschede
The Netherlands
-- Anneke Treep <anneke@echelon.uucp> (September 1993)
> The upper bound of 50 moves is I believe due to Morwen Thistlethwaite, who
> developed a technique to solve the cube in a maximum of 50 moves.
Since December 1992 it is known that the upper bound is 37 moves.
> To my knowledge, no one has ever demonstrated a specific cube position
> that takes 15 moves to solve. Furthermore, the lower bound is known to
> be greater than 15, due to a simple proof.
The following configuration:
L2 U R2 B2 U2 B2 L2 D2 L2 F2 D' L2 B2 F2 L2 F2 U' D
requires 18 moves to solve. I did prove this by exhaustive search
(took about 3.5 hours computer time). I think I also proved that 20
moves was the minimal solution for the 12-flip, but I do not remember
whether that search was exhaustive.
> It may interest people to know that in the latest issue of "Cubism For Fun" %
> (# 28 that I just received yesterday) there is an article by Herbert Kociemba
> from Darmstadt. He describes a program that solves the cube. He states that
> until now he has found no configuration that required more than 21 turns to
> solve.
An update: In July/August 1993 I solved over 10000 random configurations.
I let the solver run until it had a solution of 20 moves or less, or
until the solution was proven to be minimal. All configurations could
be solved in 20 moves or less. I have yet to see a configuration that
can not be solved in less than 20 moves. (In Kociemba's article was one
configuration his program solved in 21 moves; with my program, based on
his article, that number was reduced to 20.) Note: this does not say that
there are configurations that require 20 moves; the solver would not search
for a minimal solution if there was already a solution of 20 moves or less.
The program can be found at ftp://ftp.cwi.nl/pub/dik/cube.tar.Z.
-- Dik T. Winter <dik@cwi.nl> (November 1994)
Calculating the number of total cube configurations gives ((3 * 8!) * (2
* 12!) * (1 * 6!)) (that's corners, edges, center pieces). This gives a
total of 8.3e16 configurations. If you figure that there are a total of
18 different moves (there are 3 X cross sections, 3 Y cross sections,
and 3 Z cross sections, each of which can move clockwise or counter
clockwise), and you eliminate one move (the "undo" of the previous
move), then any board configuration can be derived from any other board
configuration in 18 * 17^(n-1) moves, where n is the total number of
moves.
Using 14 for n gives (18 * 17^13) = 1.8e17, using 13 for n gives (18 *
17^12) = 1.0e16. Any cube is solvable in 14 moves.
-- Ian D Romanick <idr@cs.pdx.edu> (November 1996)
[ Editor: a count of move sequences can only give a lower bound, not an
upper one; and the entry above gives 43,252,003,274,489,856,000
(about 4.3e19) positions, more than 18 * 17^13 = 1.8e17. ]
Essentially different positions (1995)
--------------------------------------
[ Editor: from a thread on storing a table of optimal moves for every
position. ]
> >The actual number of positions is 43,252,003,274,489,856,000 ....
> >Now, if we manage to store only the 901,083,404,981,813,616
> >essentially different positions*....
> >[* The number of essentially different positions, up to the symmetries
> > of the cube, is not that widely known--I calculated it last year.
> > I don't know of a computationally feasible way to index into a table
> > of positions reduced by symmetries. ]
> The 43,... etc. figure *is* the number of possible positions accounting
> for symmetry. To find the number of "positions" assuming rotating
> the cube to any side in any of the cardinal directions, merely
> multiply this figure by 24. It beats me where you get this "divide
> by 48" figure from.
Consider the cube positions that have X's on all six sides. There are
seventeen of them. One is the Pons Asinorum, in which each edge is
swapped with its diametric opposite. In eight of them, each edge is
involved in a 3-cycle around a long diagonal axis. And in eight more,
each edge is involved in a 6-cycle in a zigzag around a long diagonal
axis.
But all you need to know to solve these is one of each of the three
kinds. If you want to solve one of the 3-cycle X positions and you
know how to solve another such, you can move the cube in space until
the one you need to solve is the one you know how to solve (up to
a uniform recoloring of the cube).
Similarly, all twelve of the positions one quarter-turn from SOLVED
can be solved using a robot that only knows how to turn the F face a
quarter-turn clockwise, provided that the robot has the ability to
move the cube in space (so that the desired face is foremost) and to
reflect the cube in a mirror (in case the desired turn is
anticlockwise). After doing so, the robot may turn the F face
clockwise and finally move (or reflect) the cube back to its original
position. So all the positions one quarter-turn from SOLVED are
essentially the same, up to conjugation by the symmetries of the cube.
My calculations showing that the number of essentially different cube
positions are in
http://www.math.rwth-aachen.de:8000/~mschoene/Cube-Lovers/
Dan_Hoey__The_real_size_of_cube_space.html
or in the cube-lovers archives
ftp://ftp.ai.mit.edu/pub/cube-lovers/cube-mail-13.gz
Though you may need to read more of the archives to understand the
nomenclature, and perhaps learn some group theory.
If you want to join the cube-lovers mailing list, you may send email
to Alan Bawden at cube-lovers-request@ai.mit.edu; be careful not to
bother the list itself with such administrivia.
> >... So you might be able to make a table of all the positions for
> >under a billion dollars.
> Then again, why would you want to?
Well, such a file would give you an optimal solution method for any
position. Some of us think that would be a good thing. Maybe not a
gigabuck's worth, but maybe we can get the cost down to something
reasonable.
-- Dan Hoey <Hoey@AIC.NRL.Navy.Mil> (July 1995)
Solving methods
---------------
Here is an outline. If you're interested in solving by
a computer, these methods might not be desirable.
Terminology.
+---+---+---+ +---+---+---+---+
/ / / 3 /| 1: center cubes / / / / 3 /|
+---+---+---+ | 2: edge cubes +---+---+---+---+ |
/ / 1 / 2 /| + 3: corner cubes / / / 4 / 2 /| +
+---+---+---+ |/ 4: inner cubes +---+---+---+---+ |/
Tsukuda's original cube has white side and blue side
opposite. I used to start from the white side, so does
the following description. If the coloring is different
on your cube, please substitute appropriately.
For the cube (3x3x3):
o Relative position among center cubes does not change.
Match edge and corner cubes with center cubes.
1. Put corner cubes in right positions.
2. Try three edge cubes on the white side.
3. Using the position for the last white edge as
temporal storage, fix three edge cubes on blue
(opposite of the white side).
4. Put the remaining white edge and the blue Edge at
the same time (a little training needed).
5. You are left with 4 edge cubes. You'll find the
cube completed now if you're lucky enough. Use the
Rubik's maneuver or the following `procedure' if
necessary.
red side --> ______
(top) /_/A/_/|
/_/_/_/ |
blue side -> /_/_/_/ | <- white side
(invisible) |_|B|_| /
|_|_|_| /
|_|C|_|/
The following 4 step procedure rotates three cubes
A->B->C->A and keep other cubes unmoved:
1. turn center line upward 90 degree.
2. turn red (top) side 180 degree.
3. turn center line downward 90 degree.
4. turn red (top) side 180 degree.
(I found this procedure on Japanese magazine)
This method lines up the cube in 1 minutes. Training
will shorten the required time upto 30 seconds.
To solve Revenge (4x4x4):
o There is no *fixed* cubes. Look closely in corner
cubes.
1. Corners.
2. White side and blue side. (similar to the cube)
I try in the following order:
Inner white cubes but one
Inner blue cubes but one
White and blue inner cubes, simultaneously
Edge cubes similarly to 3x3x3 version
3. Other edge cubes
Some experience is needed.
4. Inner cubes (red, yellow, green, and orange cubes)
The following procedure will exchange cube A
with cube C, and B with D.
white side --> ________ _______
(top) /_/_/_/_/| |_|_|_|_|
/_/E/H/_/ | |_|_|_|_|
/_/G/F/_/ | <- |_|C|D|_| (back view)
/_/_/_/_/ | |_|_|_|_|
|_|_|_|_| |
|_|_|_|_| /
line X->|_|A|B|_| /
|_|_|_|_|/ <- blue side (bottom)
^ ^
Y Z
1. turn Y line upwards 90 degree
2. Z downwards 90
3. X 180
4. turn Y line downwards 90 degree
5. Z upwards 90
6. X 180
Side effect: exchange E <-> F, G <-> H likewise at
the bottom. Putting completed side (white and
blue) top and bottom, this side effect becomes
irrelevant. (I found this procedure myself)
Solving Revenge with this procedure is like solving
sokoban. Align cubes to be swapped at the opposite
side, apply the procedure, then trace the
preprocess in reverse order. It reminds me a
matrix multiplication like: B = P A P^{-1} :-)
I used to solve the Revenge in 6 minutes (average)
with this method. My father could do in 30 minutes
or so, utilizing this procedure (I told him this
procedure, but nothing else). Later I found it
easier to try white and blue inner cubes prior to
corner cubes.
I hope my poor English not to be an obstacle. It is
hard to describe `procedures' on paper. Try the
procedures with your own hand, and you'll find them not
quite difficult.
There were many publications (even articles in weekly
gossip magazines) on the cube 12 years ago, but I lost
them now.
-- Kaoru Maeda <kaoru@is.s.u-tokyo.ac.jp> (forwarded by Myron Souris
<souris@ug.eds.com>, February 1995)
RUBIK'S CUBE --- 4 formula solution
***********************************
Do the cube NEVER TWICE THE SAME WAY!!!
For those who are bored...
What can you do?
Make all faces at the same time
| corners first
| edges first
| corners & edges randomly
Make one face each time (any face next)
| opposite faces first
| adjacent faces first
| faces randomly
After the cube is done - you can make any color patterns
Last challenge: make color patterns starting with a random cube
(note: some patterns are impossible)
----------------------------------------------------------------------------
Each formula only moves 2 or 3 pieces.
_- +----M----+ <-. MOVE 3 EDGES ( formula #1 )
| | . M . | |
| | . . . | |
| | . . . | / <----- front face
| |____M____|
| | . M . | <-.
| | . . . | |
| | . M . | | <----- face below
`--> |____M____| __/
+---------+---------+---------+---------+
| . | . | . . . | . A . | . . . |
| . | . | . . . | . | . | . . . |
| . V . | ======> | . | . | ======> |
|_________|_________|_________|_________|
2 moves 2 moves
/----------.
V |
+---------+ | MOVE 3 CORNERS ( formula #2 )
/ | M . . | |
| | . . . | | <----- front face
`-> | M . M | /
|_________|
\_____A
+---------+---------+---------+---------+---------+---------+---------+-------+
| | . . | . . . | . . A | . . . | A . . | . . . | . . | | . . .
| | . . | . . . | . . | | . . . | | . . | . . . | . . | | . . .
| V . . | ------> | . . | | <------ | | . . | ------> | . . V | <------
|_________|_________|_________|_________|_________|_________|_________|________
mnemonic: looks like the movement of a pendulum
+---------+ ROTATE 2 EDGES ( formula #3 )
| . . . |
| R . R |
| . . . |
|_________|
+---------+ +---------+---------+ +---------+---------+
| | | | | | . A . | . . . | | . A . | . . . |
| | | | | + 4*| . | . | . . . | + 4*| . | . | . . . |
| V V V | | . | . | ------> | | . | . | <------ |
|_________| |_________|_________| |_________|_________|
move the
entire cube /\ /\
|| ||
|| ||
you must repeat this 4 times
|
<--/ +---------+ ROTATE 2 CORNERS ( formula #4 )
| R . . |
| . . . |
| R . . |
<--\ |_________|
|
+---------+---------+---------+---------+---------+---------+---------+-------
| | . . | . . . | . . A | . . . | A . . | . . . | . . | | . .
| | . . | . . . | . . | | . . . | | . . | . . . | . . | | . .
| V . . | ------> | . . | | <------ | | . . | ------> | . . V | <-----
|_________|_________|_________|_________|_________|_________|_________|_______
(formula #2)
+
+---------+
| . . A |
| . . | |
| ------/ |
|_________| (rotate the entire cube)
+
+---------+---------+---------+---------+---------+---------+---------+--------
| . . | | . . . | A . . | . . . | . . A | . . . | | . . | . . .
| . . | | . . . | | . . | . . . | . . | | . . . | | . . | . . .
| . . V | <------ | | . . | ------> | . . | | <------ | V . . | ------>
|_________|_________|_________|_________|_________|_________|_________|________
(inverse of formula #2)
sometimes you are making the last face and you reach a dead end!
solutions:
1- rotate the last face (one movement),
and then use the 4 previous formulas
2- use the following formula
+---------+ SWITCH 2 CORNERS + SWITCH 2 EDGES
| W M W |
| . . |
| . M . |
|_________|
+---------+
| | | | |
| | | | |
| V V V |
|_________| (rotate the entire cube)
+ 3*
+---------+---------+---------+---------+---------+---------+---------+--------
| ------\ | . . . | <-----\ | . . . | . . | | . . . | . . A | . . .
| . . | | . . . | . . | | . . . | . . | | . . . | . . | | . . .
| . . V | ------> | . . | | <====== | . . V | ------> | . . | | <------
|_________|_________|_________|_________|_________|_________|_________|________
rotate rotate 2 times
front face front face /\
||
||
you must repeat this formula 3 times
mnemonic: try to follow the path of the right-up corner
There must be a 15 movements formula to do this...
If you know it tell me about it.
------------------------------------------------------------------------------
NOTE FOR BEGINNERS
You must do some previous movements in order to use these formulas
and then undo the changes.
Example:
___________ ___________ ___________ ___________
/ . . . /| / . . . /| / . . . /| / . . . /|
/ . . . /.| / . . . /.| / . . . /.| / . . . /.|
/ . . . /..| / . . . /..| / . . . /..| / . . . /..|
+---------+..M| +---------+...| +---------+...| +---------+...|
| M . . |.. | = | . . . |.. | + | M . . |.. | + | . . . |.. |
| . . . |M / | . . . |. / | . . . |. / | . . . |. /
| . . . | / | <------ | / | M . M | / | ------> | /
|_________|/ |_________|/ |_________|/ |_________|/
you must use but first OK now you to finish,
the formula #2 you must can do undo the
move bottom formula #2 extra movements
-----------------------------------------------------------------------------
PS: as you can see, this is not intended to speed...
corrections & suggestions are welcome.
-- Ze Oliveira <si504340@ci.uminho.pt> (July 1995)
Actually, I have written a program to [solve the cube]. The algorithm
used is from the official solution by Ideal. You can solve the cube, or
let the computer do it for you. It's probably not very useful in
general, though, because currently there is no way to enter an arbitrary
configuration or have it "lead" you through (it just solves it VERY
quickly, but I guess it should be quite easy to change that). The
program currently runs only under MS-DOS (simple VGA graphics). If you
just want the source (in C), let me know and I can mail you a copy.
Some one has done an X-Windows-based Cube program called xrubik which
uses my solving code. It has quite a few more features than mine (but
no pseudo-3D interface). That program is in the X11 archives (e.g.
ftp.x.org:/contrib/R5/games/puzzles or something like that).
BTW, can anyone out there help me with Rubik's Revenge? (I think) I can
get most of it, but the last few bits are REALLY ugly.
-- Michael B. Martin <martinm@sps1.phys.vt.edu> (December 1994)
A related puzzle (1996)
-----------------------
I do have a Rubik puzzle without any special name. It consists of two
3 X 3 cubes that share an edge as shown below:
/\/\
\/\/
Do you know of this one? I've had it for years but never cracked it.
I'm trying to locate a solution at the moment. Does anyone out there
know of one?
-- George Haywood <george@lushegg.demon.co.uk> (April 1996)
[ Editor: no reply was collected. ]
References (1994)
-----------------
[ Editor: from Ivan Filippenko's summary of Rubik's Cube math sources;
four papers and the Compendium already listed above are omitted, and
Rowley's paper is repeated for its fuller citation. ]
"Metamagical Themas:
The Magic Cube's cubies are twiddled by cubists and solved by cubemeisters."
Douglas R. Hofstadter
Scientific American, March 1981, pp. 20-39.
"Metamagical Themas:
Beyond Rubik's Cube: Spheres, pyramids, dodecahedrons and God knows what else."
Douglas R. Hofstadter
Scientific American, July 1982, pp. 16-31.
"Rubik's Cube and a model of quark refinement."
Solomon W. Golomb
Amer. J. Phys., 49 (11), November 1981.
"The Group of the Hungarian Magic Cube."
Chris Rowley
Algebraic Structures and Applications,
Proceedings of the First Western Australian Conference on Algebra, 1982.
"Rubik's Cube and Beyond"
Christoph Bandelow
Birkhauser, 1982
pb 120 pp. + biblio
ISBN 3-7643-3078-3
the price _was_ 3.95
"Notes on Rubik's Magic Cube"
David Singmaster
Enslow Publishers
Hillside, NJ
1981
ISBN 0-89490-043-9
[ his shingle was at:
Mathematical Sciences and Computing
Polytechnic of the South Bank
London SE1 OAA, England
This was privately published.
There are a couple of addresses & telephones on the inset.
Singmaster
66 Mount View Rd
London N4 4JR, UK
01-348-7266
Enslow Publishers
Bloy St. and Ramsey Ave.
Hillsdale, New Jersey
201 964-4116 ]
"Handbook of Cubik Math"
A. H. Frey and D. Singmaster
Enslow Publishers
Hillside, NJ
1982
-- Ivan Filippenko <ivan@Aero.org> (November 1994)
Clubs, newsletters and mailing lists
------------------------------------
Check into subscribing to the cube-lovers mailing list which
has members talking about anything related to cubes and puzzles
in general. Subscribe by sending E-Mail to:
cube-lovers-request@ai.mit.edu
This list is processed by a hu-man be-ing so feel free to write
to him (Alan Bawden) in full english sentences.
Thanks for the plug. Indeed, the list is maintained manually, which
apparently strikes many people as somewhat quaint and old-fashioned judging
from the number of messages I have received recently that make fun of this
fact.
-- Alan Bawden <Alan@LCS.MIT.EDU> (March 1994)
Cubism For Fun number 33.
This is a periodical dedicated to puzzles.
I just received #33. It is dated February 1994, so it is a bit late ;-).
Here a summary of the contents.
1. Dr. Dragon's Polycons by Bernhard Wiezorke and Jacques Haubrich
A new, apparently interesting, puzzle from Japan, a lot like
polyominoes. Given a rectangular grid you can make pieces from
the horizontal and vertical lines connecting the points. The
writers coin the term 'monocon' for the piece consisting of a
single line segment, 'dicon' for the two different pieces that
consist of two connected line segment (one is angled, the other
not). Similarly there are 5 'tricons' and 16 'tetracons'. The
puzzle consists of 10 of the 16 'tetracons' that must be put on
a 5x5 rectangular grid. The authors also look at extensions of
the puzzle.
2. The Hollow Pyramid by Jan de Ruiter.
In a previous issue there was a puzzle about a hollow pyramid made
up of balls that must be constructed by the 25 different pieces
that consist of 4 connected balls. Jan de Ruiter was the first to
solve the puzzle (with a computer). Here he explains the program.
3. Junior Polycubes by Jacques Haubrich.
Pieces consist of 1 to 4 connected cubes that must be put on a
6x6 square. Not so much a puzzle, more like Tangram: create forms.
4. Folding Puzzles by Leo Links.
About puzzles where some intricate folding is needed to solve.
5. Cross Pattern Piling by Dieter Gebhardt.
A puzzle where you put counters on a square and its four neighbours.
The goal is to pile up to a common height for all the squares. The
article also discusses a modified version where counting is done mod
2. Associated with it comes the 24th CFF contest.
6. Gouge Packing Puzzle by Gaetan Gouge.
Description of and some elaborations about a packing puzzle.
7. Spots Puzzle by Harold Cataquet.
Elaborations about a puzzle from A.L.Hoffman, Puzzles old and new,
New York, 1920.
8. Arrow-Minded by Ivan Moscovich.
Start with a fully-connected hexagon. Put random arrows on all edges.
Next add nodes on all intersections. This gives 19 nodes in all. The
problem is to find a Hamiltonian path along the nodes, minding the
arrows (not always possible). An original puzzle by the writer.
9. Prime Pentacube Packings by Frits Gobel.
Start with the pentacube consisting of a square base of four cubes and
one cube on top of it in a corner. Is it possible to pack a 5x5x5
cube with 25 such pentacubes? What other figures can be packed?
10. Contest 25 by Ekkehard Kuenzell.
Pack a figure with all 29 different pentacubes.
11. Rubik's Rabbits by Luc de Smet.
Discussion of this latest by Rubik.
12. Party Impressions by Gerald Maurice.
Impressions of the Puzzle Party and Cube Day, August 1993 in the
Netherlands.
Further results of contest 23, a book review by Mark Peters and the first
of a series of columns by Edward Hordern.
Cubism For Fun is a newsletter published by Nederlandse Kubus Club NKC
(Dutch Cubists Club), it is in English. Applications for membership to
the treasurer:
Lucien Matthijsse
Loenapad 12
3402 EP IJsselstein
The Netherlands
Membership fee NLG 25.- (about US$ 15.-; add transaction costs).
-- Dik T. Winter <dik@cwi.nl> (April 1994)
Someone asked how to subscribe to the Rubik's cube mailing list.
Send e-mail to cube-lovers-request@ai.mit.edu
Also there is a magazine called "Cubism for Fun" published by the
Dutch Cube Club, issued about three times per year to members.
Annual membership costs 30 gulden and I think the treasurer is:
Lucien Matthijsse
Loenapad 12
3402 PE IJsselstein
The Netherlands
But the magazine now discusses lots of other puzzles besides
Rubik's shapes.
-- Norman Diamond <diamond@jrd.dec.com> (June 1995)
[ Editor: Web pages on the cube posted in 1994-1997 (solutions by Tom
Magliery, Mark Jeays and Alan Hensel, cube sources, Square 1) are
collected in references/web.sites. ]