Category : Miscellaneous Language Source Code
Archive   : RUBECUBE.ZIP
Filename : CREAD.ME

Rubik's Cube (TM) Solver - by Zachary Stern
(for more information, write: 403 Suffield Drive
Gaithersburg, MD 20878)


This Rubik's Cube (TM) solver will run on most IBM PC/AT compatible
computers with monochrome or color displays and at least 512K of available
RAM. The program has been tested and run successfully on a Tandy 100 SX,
an 8 MHz IBM PC/AT and a 10 MHz Compaq 286. The program was written in
Turbo Prolog v1.0 (Borland) and is divided into several linkable files:

cube.pro main file includes goal and database predicates
cube_use.pro contains user interface predicates
cube_boo.pro contains procedure for solving cube
cube_dom.pro contains global domain declarations
cube_glo.pro contains global predicate declarations
menu.pro contains standard menu user interface predicates
keybd.pro contains keyboard interface predicates

To run the solver, enter CUBE.


About the program...

This program incorporates cursor driven bar menu selection to modify and solve
a rubik's cube. The display is divided into two windows. The window on the
left contains a display of the current state of the cube. The window on the
right contains the solution path if one has been found, or contains the
menu overlays.

Cube Display Window

The cube is displayed as if it were an unfolded box, with each face
turned so that it faces you. The faces are layed out as shown below:

6 T
1 2 3 4 OR L F R P
5 B

The cube faces are labeled by letters representing their orientation with
respect to the front face, or the cube face that is facing you. The front
face is labeled F, the right face is R, the left face is L, the bottom
face is B, the top is T, and the face on the opposite side of the cube from
the front face is the posterior face labeled P.

The individual tile on each face may be displayed in color on color monitors,
or may be displayed as a monochrome number, 1-6, representing the color of
that tile. Rubik's cubes are not all labeled with the same colors, therefore
the colors on your cube may not match those on the screen. The display
of colored tiles may be toggled on and off by selecting "toggle color" from
the main menu. The cube display is normally updated every time the state of
the cube changes. If you wish to reduce cube solution time, this automatic
update may be suspended temporarily by selecting "toggle graphics" from the
main menu. To redisplay the cube after the solution is complete, reselect
"toggle graphics" and the current state of the cube will be displayed.

Below the cube display, the current values of G and H are displayed. G
represents the number of cube moves made to take the cube from the initial
state to its present state. H represents the result of a static evaluation
function that estimates the number of moves required to move the cube from
its present state to the goal state (all faces the same color).

The Solution and Menus

The main menu displays the following options
"modify current cube",
"toggle graphics",
"toggle color",
" ",
"direct cube solution ( < 60s. )",
"heuristic cube solution ( forever )",
"view solution",
" ",
"reinitialize cube"

The program starts with the cube displayed in the solved state. You must
modify the state of the cube (mess it up) so that the program will have
something to solve! Upon selecting "modify current cube" the following
menu of options will be displayed:
"top plus",
"top minus",
"front plus",
"front minus",
"left minus",
"left plus",
"right plus",
"right minus",
"bottom minus",
"bottom plus",
"posterior minus",
"posterior plus",
" ",
"random sequence of moves",
"set-up new cube"

The first twelve options are all the individual moves that can be applied to
the cube. For example, selecting the first option "top plus" will move the
top face of the cube in the plus direction (clockwise), the fourth option
"front minus" will move the front face of the cube in the minus direction
(counter clockwise). There are two other ways to modify the cube. Upon
selecting "random sequence of moves" the user will be prompted to enter
an integer number of random moves to be made. Enter any number you like.
The program will make the requested number of random moves and really mess
the cube up.

Finally, the user may choose to set the cube up in one specific position. To
do this, select the last option "set-up new cube". Some more instructions
will be displayed, and then the user will be prompted to enter a number from
1 to 54 representing the location of each of the 54 cube tiles. To
determine which number to enter, use the folowing tables:

Edge Block (two-faced) Table

front other code to enter
color color

1 6 2
1 2 6
1 5 8
1 4 4
2 1 13
2 6 11
2 3 15
2 5 17
3 2 22
3 6 20
3 4 24
3 5 26
4 3 31
4 6 29
4 1 33
4 5 35
5 1 40
5 2 38
5 3 42
5 4 44
6 1 49
6 4 47
6 3 51
6 2 53


Corner Block (three-faced) Table

front other code to enter
color colors

1 4,6 1
1 2,6 3
1 2,5 7
1 4,5 9
2 1,6 10
2 3,6 12
2 3,5 18
2 1,5 16
3 2,6 19
3 4,6 21
3 4,5 22
3 2,5 25
4 3,6 28
4 1,6 30
4 1,5 36
4 3,5 34
5 1,2 37
5 2,3 39
5 3,4 45
5 1,4 43
6 1,4 46
6 3,4 48
6 2,3 54
6 1,2 52

The first table shows the code numbers to enter for edge tiles (those with
only two sides), while the the second table shows the codes for three sided
corner tiles.

Solving the Cube

After modifying the cube to your satisfaction, the cube may then be solved
in two ways:
"direct cube solution ( < 60s. )"
"heuristic cube solution ( forever )"

Direct Solution

The direct solution is by far the recommended method to use when solving the
cube. This solution is purely procedural, and uses moves adapted from "The
Simple Solution to Rubik's Cube", by James G. Nourse. This method solves the
cube by moving tiles to their correct locations in the following order:
top edges
top corners
middle edges
bottom corners
bottom edges
With the graphics turned on, this solution will take about a minute, but will
usually require less than 200 cube moves. With graphics turned off, the
solution usually takes less than 30 seconds. (Times given for Tandy 1000 SX).
This procedural method guarantees that a solution will always be found.

The solution is shown in the "Solution" window on the right side of the
screen. The solution is a sequence of moves shown in their abbreviated form.
For example, tp stands for top plus, and pm stands for posterior minus as
given in the modify cube menu. There is one additional abbreviation, cr,
which is not given in the modify cube menu, and it stands for cube right.
This move is the same as taking the entire cube and rotating it counter
clockwise as you look down on it from the top face. This action is not
counted as a move since no part of the cube moves with respect to another
part.
Heuristic Solution

A second attempted method of cube solving is also included. This method
is a result of the author being over optimistic in his abilities to create
an admissable algorithm! The heuristic search evaluates the current cube
state, generates offspring of the current state, and selects the first one
that produces a smaller heuristic evaluation. If no offspring result in
a smaller evaluation, a move is chosen at random. This process is repeated
until the cube is solved. The evaluation function counts the number of cube
tiles that are not next to their correct neighbors. There are two major
problems with this approach. First, the program does not remember what cube
states it has already visited, so it is quite possible for it to return
often to the same states. the random move generator was an unsuccessful
attempt at resolving this problem. The second problem lies with the
static evaluator. To solve the cube, it is often necessary to make the
cube much more disordered, before it becomes ordered; however, the heuristic
here is a simple hill climber, and is unable to avoid local minima of
the evaluation function. This method is not guaranteed to find a solution,
and I have only seen it solve very simple cubes.

Happy Cubing!