[next] [prev] [up] Date: Wed, 08 Jan 92 21:20:01 -0500 (EST)
[next] [prev] [up] From: Dan Hoey <hoey@aic.nrl.navy.mil >
[next] ~~~ [up] Subject: Rubik's Cube, the minimax number of moves

mkt@vax5.cit.cornell.edu (Gregory E. Dionne) asks:

Does anybody know what the minimum number of moves are required to
solve the 3x3 and/or 4x4 cubes in the worst-case scenario?

and receives some answers, some of them accurate. The following is my
understanding of the best answers now known, which I am sending both
to rec.puzzles and the Cube-Lovers mailing list. The latter will, I
hope, excuse some information repeated from the archives.

First, you have to decide what you mean by a move. On grounds of
symmetry and parsimony I prefer to count each quarter-turn of a face
as a (QT) move. However, most of the literature counts either a
quarter-turn or a half-turn of a face as a single (HT) move, and there
has been more work done on the problem by the HT contingent.

Second, you have to be careful to define what constitutes solved!
While most people are content to make each face a solid color, some
cubes have markings that display whether the face centers are twisted
with respect to the rest of the cube.
[This has recently been done commercially in an spectacularly
braindamaged way, in a product known as ``Rubik's cube--the
fourth dimension'' or some such nonsense. The mfrs have marked
only four face centers, breaking symmetry while they fail to show
the surprising invariant of the Supergroup. What bagbiters!]
But that is a topic for other messages; I will not further discuss the
invisible features of cubes here, save to note that there are more
invisible features in larger cubes, and that if you take them into
account, the cube will be harder to solve and require more moves than
if you don't.

Third, you have to understand that in either case, nobody knows the
exact answer except for the tiny cubes. It boils down to knowing
lower bounds L and upper bounds U, such that there must be some
positions requiring at least L moves, while any position can be solved
in at most U moves. I will discuss these in turn, below.

For lower bounds, it is easy to calculate how many positions of
Rubik's cube are achievable, and we may reason that only a few
positions are within a few moves of start. Counting them, we can
determine that at least 21 QT (or 18 HT) are needed to solve some
positions of the cube. In fact, at least half of the positions of the
cube require at least 18 HT, and at least 90% of the positions require
at least 20 QT. The calculations are elementary, and have been known
for over a decade. Nobody knows any other very good way of finding
lower bounds. In Rubik's_Cubic_Compendium (1987), Tamas Varga writes
Experts believe that even in the worst cases--the patterns
furthest away from start--it should be possible to restore the
cube in 20-odd [HT] moves, maybe 25, not more.
However, such beliefs are clearly conjectural, based on the behavior
of much simpler puzzles.

The known upper bounds are constructive, consisting of a solution
procedure guaranteed to solve any cube within U moves. The best known
bound is embodied in a procedure invented by Morwen B. Thistlethwaite,
and improved by students of Donald E. Knuth (The students are not
identified in R_C_C). The improved procedure requires at most 50 HT
in the worst case. Thistlethwaite was hoping (in 1980) to improve
this to 41 HT, but (rumors to the contrary) he apparently did not
succeed. A 1989 article by Hans Kloosterman entitled ``Rubik's Cube
in 44 moves'' refers to an attempt to refine Thistlethwaite's method.
I have not heard of any success there, either.

Since any HT is at most 2QT, any Rubik's cube position can be solved
in at most 100 QT using Thistlethwaite's method. According to my
understanding of the method, this can actually be reduced to 97 QT,
but this is still poor. A method tailored to minimizing QT would
almost certainly guarantee a much shorter solution.

Unfortunately, Thistlethwaite's method requires enormous tables of
partial solution methods. Gerszon Keri describes a simpler method in
R_C_C that requires at most 97 HT and which humans can memorize. The
method is attributed to ``a Cambridge group,'' which I think must
refer to England. According to Keri the Cambridge method has been
refined to use only 79 HT, but I do not know if the refined version is
still humanly comprehensible.

For the 2x2x2 cube, the worst-case number of moves is known to be
exactly 14 QT (11 HT).  Only 276 (2644) positions require all 14 QT
(11 HT).  Half of the positions can be solved in 11 QT (9 HT) or
fewer.

For the 4x4x4 and larger cubes, the problem of defining a move is more
complicated. Besides the QT/HT dichotomy, there is the question of
whether a move consists of a slice (turning one part of the cube with
respect to the other) or a slab (turning a 1x4x4 section of the cube
with respect to the rest). We might expect that, as we do not count
the center-slab moves of the 3x3x3 as a single move, we should not
count the inner-slab moves of the 4x4x4 as a single move. However, I
have discovered excellent reasons of symmetry (send email if you want
to know) for us to consider all slabs alike, whether internal or face,
with the exception of the center slab of an odd-sized cube. This is
known as the Eccentric Slabist metric.

According to my calculations of some years ago, some 4x4x4 positions
require at least 37 slab QT or 41 slice QT to solve. The Eccentric
Slabist also calculates at least 59, 81, 111, 138, 175, and 208 QT for
the 5x5x5 through 10x10x10 cubes. (And yes, I've heard the widespread
misinformation that Rubik's cubes larger than six cubies on an edge
are impossible).

I seem to recall calculating HT lower bounds, but I can't seem to find
them. I do not recall whether upper bounds have been calculated for
the large cubes, other than that they are O(N^2)--see J. A. Eidswick's
article in the March 1986 Math Monthly.

Dan Hoey
Hoey@AIC.NRL.Navy.Mil


[next] [prev] [up] [top] [help]