A Prolog program and demonstration of an efficient heuristic search method
by David Lee Winston Miller

Selected as the Geek Site of the Day.

(Reviewed in the Ziff-Davis magazine and received "Four Stars", Voume 2, Issue 4, April 1997.  Also reviewed online at http://www.underground-online.com/webguide/)

". . . efficient programs can be developed that automatically generate profile tables (and solutions) when given most any problem involving a definable goal and state space."

Note: This project was originally completed for Dr. Jorge Novillo's graduate level Logic Programming class (CSC545). The program runs on the Arity/Prolog Compiler and Interpreter (Arity Corporation). Photo depicts face of a cardboard cube used in modelling the state space. No other special knowledge of Rubik's cube was used to write the program!

Click here for very short Rubik demo.

Rubik's cube is simply a finite state machine and accepts a language like any other such machine. The language accepted is composed of a string of moves. However, the number of states that this machine can assume is extremely large. This makes searching its state space impractical unless most possibilities are eliminated from consideration.

We can simplify our view of this machine if we bring our attention to the smaller cubes from which the larger cube is constructed. These smaller cubes are also finite state machines each accepting a particular language. The intersection of all these languages is the language that the larger cube accepts.

To understand the cube, lets begin by looking at its topography--its flat layout. We will then reconstruct the cube and take it apart again. However, when we take the cube apart again, we will not explore its topography but rather its submachines--the smaller cubes that we will refer to as mini-cubes:

     |           |
   __ ___ ___ ___ __
     | R | R | R |
     |___|___|___|
     | R | R | R | ^Red             Arrows point to "top"
     |___|___|___|  (Right)             of the cube.
     | R | R | R |           |
  __ |___|___|___|___ ___ ___ __
     | B | B | B | Y | Y | Y |
     |___|___|___|___|___|___|
Blue | B | B | B | Y | Y | Y | >Yellow
(Bot)|___|___|___|___|___|___|  (Back)
     | B | B | B | Y | Y | Y |           |
  __ |___|___|___|___|___|___|___ ___ ___ __
                 | O | O | O | W | W | W |
     |           |___|___|___|___|___|___|
         >Orange | O | O | O | W | W | W | White
          (Left) |___|___|___|___|___|___| (Top)
                 | O | O | O | W | W | W |
               __|___|___|___|___|___|___| __
                             | G | G | G |
                 |           |___|___|___|
                     Green   | G | G | G |
                     (Front) |___|___|___|
                             | G | G | G |
                          __ |___|___|___| __

                             |           |

                                            ____ ____  ___
Fold it on the       |\_W_\_W_\_W_\
fold lines and       ||\_W_\_W_\_W_\
you get this:        |||\_W_\_W_\_W_\
                     |||| G | G | G |
             Orange  ||||___|___|___|
             Side    |||| G | G | G |
                     \|||___|___|___|
                      \|| G | G | G |
                       \|___|___|___|

                                       Y
                                       |
                                       |
                                       |
A Numbering System                     |
for the mini-cubes:                          7
                                      6 ____________8       (Not all
                                       |\___\___\___\        numbers
                                       ||\___\___\___\ 12    shown.)
                                     4 |||\___\___\___\
                                       ||||   |   |   |20
                                       ||||___|___|___|
                                      1||||   |   |   |17  _ _ _ _ _ X Explanation:                            \||___|___|___|
                                        9\|   |   |   |
As you can see, the mini-                 |___|___|___|
cubes are ordered in a natural           13    14     15
fashion mostly according to location        \
in X-Y-Z space. A preliminary number for     \
each cube can be obtained by assigning it an  \
integer according to its location along each   \
each axis (relative to the origin). Therefore,  Z
each cube can be described by three integers.

A single decimal number for each mini-cube location can be obtained as follows:

                Z axis      Y axis      X axis      Base 3   Base
                coordinate  coordinate  coordinate  (ZYX) #  ten #  Place #
Cube at
origin:         0           0           0           000      0      1st

Cube farthest
from origin:    2           2           2           222      26     27th

However, six of the mini-cubes are "stationary" and the core mini-cube is not relevant. Therefore, we count the cubes in the order above using the base ten system, but we skip the stationary mini-cubes as well as the core.

             7                         6----7----8  Think of the cube
 6 _______________________8            |         |\  as being divided
 |\      :\      :\      :\            4    Y    5 \  into three
 |  \ ______\ ______\ ______\          |         |  \  slices--Back,
 |   |\11:    \  :    \  :   :\12      1----2----3   \  Mid, and
 |...|..\.______\:______\:___:__\       \             \  Front.
 |\  |   |\      :\      :\  :   :\      \   11---W---12
4|  \|   |  \ ______\ ______\.______\20   \  |         |\
 |   |\  |   |18 :   | 19.   |`. :   |     \ O    X    R \
 |...|..\|...|...:...|...:   |  `:   |      \|         |  \
 |\  |   |\  |   :   |   :`. |   :`. |       9----B---10   \
 |  \|   |  \|_______|_______|______`|        \             \
 |   |\  | 16|   :   |   .   |`. :   |         \   18--19---20
1|...|..\|...|.......|...:   |  `:   |17        \  |         |
  \  |   |\. |   `.  |    `. |   :`. |           \ 16   G   17
    \| . | .\|_______|_______|______`|            \|         |
      \  |   |`.     |`.     |`. :   |             13--14---15
      9 \|...|..:....|..:....|..::   |
          \  |    `. |    `. |    `. |
            \|_______|_______|_______|
            13          14           15      In one cube there are:
                                                20 movable mini-cubes
                  FRONT VIEW                    6 "stationary" mini-cubes
                                                1 center core

The Flat layout of the General
Mini-cube Numbering System:

                                   For reference, copy this, color it, cut
      |           |                along outside lines, fold, and tape to
    __ ___ ___ ___ __              make a cube. You may have to fudge a
      |20 |12 | 8 |                little since printer aspect ratios vary.
      |___|___|___|
      |17 | R | 5 | ^Red
      |___|___|___|  (Right)                Arrows point to top
      |15 |10 | 3 |           |             of cube. (White face).
   __ |___|___|___|___ ___ ___ __
      |15 |10 | 3 | 3 | 5 | 8 |                    This cube is not
      |___|___|___|___|___|___|                    necessarily
Blue  |14 | B | 2 | 2 | Y | 7 | >Yellow            "perfect". For
(Bot) |___|___|___|___|___|___| (Back)             this reason, each
      |13 | 9 | 1 | 1 | 4 | 6 |           |        movable mini-cube
   __ |___|___|___|___|___|___|___ ___ ___ __      is numbered in-
                  | 1 | 4 | 6 | 6 | 7 | 8 |        stead of colored.
      |           |___|___|___|___|___|___|
          >Orange | 9 | O |11 |11 | W |12 | White
          (Left)  |___|___|___|___|___|___| (Top)
                  |13 |16 |18 |18 |19 |20 |
               __ |___|___|___|___|___|___| __
                              |18 |19 |20 |
                  |           |___|___|___|
                        Green |16 | G |17 |
                      (Front) |___|___|___|
                              |13 |14 |15 |
                           __ |___|___|___| __

                              |           |

Now, let's learn more about mini-cubes and the conventions used in this program:

Each mini-cube is identified by colors. (Note: We will consider white to be a color also.) The faces that you don't normally see are colorless (black). Each mini-cube's exposed faces are colored and each mini-cube's unexposed faces are colorless. No two mini-cubes are alike.

There are really four different basic types of mini-cubes: Corner cubes, edge cubes, mid-face cubes and, of course, the cube in the very center that is never seen. (We will never be concerned with the center cube since it has no colors and is not part of the puzzle.)

By convention, we will refer to the mid-face cubes as "stationary." This is because we can move the other exposed cubes without ever moving the mid-face cubes to another position. In fact, the mid-face cubes always remain constant in relation to each other. This is one of the few things about Rubik's cube that can give us a sense of security--Everything else is volatile!

We will always consider the exposed part of each "stationary" cube to be facing a given direction. For instance, the green-faced "stationary" cube will be considered to be facing to the front.

*Note: The word "hidden" instead of "back" is used so that any use of letters to represent the "back" side will not be confused with the "bottom." (The back side is "hidden" from view when you view the cube from the front.)

Every mini-cube has six sides. If we were to remove a given mini-cube from the whole cube (keeping it oriented as before), we could see all six sides and identify which colors faced what direction. This information defines the state of a mini-cube. A mini-cube state can be defined as follows:

mc(Front,Top,Left,Hidden,Bot,Right) or mc(F,T,L,H,B,R)
where each argument contains a color: green (g), white (w), orange (o), yellow(y), blue (b), red (r), none (n).

An actual instantiation for the #1 mini-cube might be mc(n,n,o,y,b,n). This means that the front facing side is presently non-colored (or "none"), the top is "none", the left side is orange, the "hidden" side (the back) is yellow, the bottom is blue, and the right side is "none." (With this particular instantiation, the #1 mini-cube is in the "solved" position.)

A result of all of this is that you do not have to describe the state of the whole cube by the colors on each face: We can mentally break the cube apart into mini-cubes and note the orientation of each mini-cube.

For instance, the #1 mini-cube could be positioned with the orange side toward the front. However, we must also know more about its orientation to know its state. While the orange side is toward the front, the yellow side could be facing up, right, down or left. In other words, the #1 mini-cube could be in any of 24 states total:

mc(n,b,y,o,n,n) mc(n,y,n,o,n,b) mc(n,n,n,o,b,y) mc(n,n,b,o,y,n) mc(b,n,n,n,o,y) mc(b,y,n,n,n,o) mc(b,o,y,n,n,n) mc(b,n,o,n,y,n) mc(y,n,b,n,o,n) mc(y,b,o,n,n,n) mc(y,o,n,n,n,b) mc(y,n,n,n,b,o) mc(o,b,n,n,n,y) mc(o,y,b,n,n,n) mc(o,n,y,n,b,n) mc(o,n,n,n,y,b) mc(n,n,y,b,o,n) mc(n,y,o,b,n,n) mc(n,o,n,b,n,y) mc(n,n,n,b,y,o) mc(n,n,n,y,o,b) mc(n,b,n,y,n,o) mc(n,o,b,y,n,n) mc(n,n,o,y,b,n)

This representation of the states of each mini-cube can be simplified if we assign a letter to each state. Then a mini-cube can be represented by the letters "a" through "x." Ways in which each letter can be assigned to a state will not be fully discussed here. However, it should be noted that different methods have different advantages and disadvantages. A method has been devised that allows each mini-cube to use the same basic scheme where state "a" for one mini-cube has certain things in common with state "a" of another mini-cube.

The state of the whole cube can be represented as follows:

st(MC1,MC2,MC3,MC4,MC5,MC6,MC7,MC8,MC9,MC10, MC11,MC12,MC13,MC14,MC15,MC16,MC17,MC18,MC19, MC20)
where MC1 through MC20 are the states of mini-cubes #1 through 20.

The "MC" variable names above are used only to make the point that each variable "belongs" in a certain place in the twenty-tuple relation named "state." In actual practice, we could name the variable states of each mini-cube by the colors in each mini-cube:

st(OYB,YB,YBR,OY,YR,WOY,WY,WYR,OB,BR, WO,WR,GOB,GB,GBR,GO,GR,WO,GW,GWR)

or for simplicity, we can let "A" represent the state of the first mini-cube, "B" the state of the second, etc. . .

st(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T)

If you examine the cube topography, you will indeed find that, when in the solved position, mini- cube #1 is orange, yellow and blue, where mini-cube #2 is only yellow and blue. Again, no two mini-cubes have the same colors.

An example of the state of a whole cube might be:

st(a,a,c,b,c,b,g,h,e,d,l,p,l,j,f,v,f,v,w,o)
where the first mini-cube is in state "a" and the last is in state "o."

When we are presented with an unsolved cube, we could lay the mini-cubes all on a table in a row, oriented in the directions that they were when the cube was whole, and solve the puzzle by finding a series of moves that causes every mini-cube to be in its solved orientation. This is analogous to the method used in the Rubik program. Assuming that we have learned what moves have what effect on what states, we will no longer be concerned with the cube as a whole. Usually, we will only be concerned with the orientation of the individual mini-cubes (although we apply a common series of moves to the entire set of mini-cubes).

We will notice that the effect that each move has on a given mini-cube depends on the cube's orientation and what basic type of mini-cube it is. In some orientations, certain moves have no effect at all.

So, what moves have what effect? Let's start by explaining moves: There are only twelve moves. There are six faces and each can be turned 90 degrees to the "left" (counterclockwise) and 90 degrees to the right (clockwise). We will name a face of the whole cube by the color of its "stationary" square. Accordingly, the moves are green-right (gr), green-left (gl), white-right (wr), white-left (wl), orange-right (or), orange-left (ol), yellow-right (yr), yellow-left (yl), blue-right (br), blue-left (bl), red-right (rr), and red-left (rl). Of course, we know that we can move a face 180 degrees or another multiple of 90. However, we will consider such moves to be two or more 90 degree moves.

Note that since the green "stationary" square is always facing the front (by convention), a "green- right" move could just as easily be considered to be a "front-right" move. It turns out that a mini- cube is not affected by a green-right (or left) move unless its front facing side is colored. Likewise, a mini-cube is not affected by a white move unless its top side is colored. The same pattern is true for all other moves.

By experimentation, we can see that a green-right move does not affect the front or hidden (back) face of any mini-cube. If a mini-cube is affected at all by this move, only its top, right, bottom and left faces are changed. In this case, the top gets the color of the left, the right gets the color of the top, the bottom gets the color of the right, and the left gets the color of the bottom. A similar set of rules can be stated for each of the remaining moves.

We can use this information to construct tables that tell us what state any mini-cube changes to when subjected to a move. The series of moves that cause all mini-cubes to change to their solved state, is the solution to a given Rubik puzzle.

The goal is for each mini-cube to be properly oriented (in its solved position). For example, mini- cube #1 would not be properly oriented if its yellow side faced left. However, if its orange side faces left, its yellow side hidden (toward the rear), and its blue side down (bot), then it is properly oriented. This can be expressed as mc(_,_,o,y,b,_) in the relation below.

          "Old" color state designation   letter designation   mini-cube #
goal( st( mc(_,_,o,y,b,_),                a,                   1
          mc(_,_,_,y,b,_),                a,                   2
          mc(_,_,_,y,b,r),                c,                   3
          mc(_,_,o,y,_,_),                b,                   4
          mc(_,_,_,y,_,r),                c,                   5
          mc(_,w,o,y,_,_),                b,                   6
          mc(_,w,_,y,_,_),                g,                   7
          mc(_,w,_,y,_,r),                h,                   8_________
          mc(_,_,o,_,b,_),                e,                   9
          mc(_,_,_,_,b,r),                d,                   10
          mc(_,w,o,_,_,_),                l,                   11
          mc(_,w,_,_,_,r),                p,                   12________
          mc(g,_,o,_,b,_),                e,                   13
          mc(g,_,_,_,b,_),                f,                   14
          mc(g,_,_,_,b,r),                m,                   15
          mc(g,_,o,_,_,_),                j,                   16
          mc(g,_,_,_,_,r),                m,                   17
          mc(g,w,o,_,_,_),                j,                   18
          mc(g,w,_,_,_,_),                r,                   19
          mc(g,w,_,_,_,r)                 s                    20
        )
    ).

As mentioned before, the choice of letters will not be fully explained. However, one can see that the use of letters to designate states would simplify expressions involving states when compared to the "old" color designation method.

The "best-fast" program is an A* capable which uses a best-first type algorithm to solve Rubik's cube. It could be used, of course, to solve other problems as well. This algorithm differs from the one used in the textbook (Prolog Programming for Artificial Intelligence by Ivan Bratko, second edition, 1990, Addison-Wesley Publishers) in a number of ways. (Note: Some of the code may use elements from the text). First, the textbook program is limited to instantiations of 64K when used with Arity Prolog. However, the "best-fast" program presented here is limited to 2GB. Also, experience has demonstrated that the "best-fast" program finds solution faster than the best-first program in the textbook. This is largely because the program uses a b- tree data structure to store search-tree nodes. Heuristic generated values are used as keys. This should give a tremendous advantage when solving large problems.

Another important difference is the use of tables (which we will call profile tables) in the heuristic algorithm. A profile table is a relation that relates certain characteristics of states to the number of moves that a state is from the solved position. We will call this number of moves "the goal distance." Like most other heuristics, profiles are not always correct. However, using the lowest goal distance generated always produces an underestimate of the number of moves necessary to solve a cube. When an entry in the profile table is not found, a simple conventional heuristic is used instead. Unfortunately, the conventional heuristic tends to grossly underestimate the goal distance. An advantage of the profiles is that they tend to produce better estimates and extremely rapid solutions once the search enters the state space covered by the tables. (That is once the search enters the state space defined by the "change-over distance", which is defined below.)

Profile tables have a limit of state space coverage which is evidenced by the largest goal distance reported in the table. We will call this the "change-over distance" since it is after this point that a conventional heuristic must be used.

To generate profile tables, one needs only to produce values that are associated with states known to be at a given goal distance. For a given goal distance covered by the table, one or more profiles will be generated. An optimal profile is one that has a one-to-many correspondence exclusively with states that are a given number of moves away from the solved state. However, this is not required to guarantee the shortest solution (in terms of moves) to any problem. Values may also be (incorrectly) associated with states at other goal distances as long as there is at least one "correct" profile for every state within the "change-over distance." A profile is considered "correct" when its goal distance matches the state it is associated with. Since a profile may be associated with many states, it may be "correct" with respect to one state and "incorrect" with respect to another.

To make profile tables faster they are hashed using the profile values as keys. To make profile tables more accurate (and thus encourage faster searching) they could be dynamically tracked to check the accuracy of any assumption generated by the profile table. Using this method, an assumption can be proved wrong if a successor state's profile is inconsistent with an assumption made about its predecessor. New assumptions can then be made and the new information can propagate through the search tree. Although dynamic tracking is not presently implemented in the program, the program was designed to eventually accommodate such an algorithm. Presently, this accommodation slows the execution. However, with full implementation of profile tracking, execution speed should increase.

For Rubik's cube, solutions are presently time-limited/memory-limited to about 9 moves deep on slow machines. Shortest solutions (A* searching) can be guaranteed using the parameters outlined below. The depth limitation will increase with the use of larger profile tables and the implementation of profile tracking. Also, the program was designed for the 16-bit version of Arity Prolog: Using the 32-bit version may increase depth. The use of a supercomputer to generate larger profile tables would make a big difference. The resulting data is very economical because modest sized profile tables cover an enormous state space.

Profile tables could also be employed beyond a set goal distance in an incomplete or even statistical manner. (To do this, we must be willing to either relax A* search requirements or redefine the concept of the change-over distance.) In using incomplete profile tables, we would be laying down sparse profile paths throughout the state space. In effect, we would be casting a wide "net" hoping that eventually, a candidate path will cross a profile path. Although this may seem unlikely, such a method seems to have the potential of reducing problems that tend to require a search of xⁿ nodes, to problems that tend to require a search of something like x^n-m nodes where x^m is the size of the state space covered by the profile table. (Not to be confused with the size of the table itself.) Further research is required to see if this assumption is correct.

The intent of this approach is to solve problems in a more general way without a great deal of experience with the problem. For example, algorithms exist that can solve Rubik's cube. In the design of the program presented, these algorithms were not examined. The idea was to be able to solve Rubik's cube without specific knowledge about its solution. The author of this program and report still does not know how to solve Rubik's cube! (But the program does.)

In fact, it seems reasonable to assume that efficient programs can be developed that automatically generate profile tables (and solutions) when given most any problem involving a definable goal and state space. In conjunction with the "best-fast" program, many problems could be solved using no other special knowledge of the problem.

Before using the rubik15.ari program, you must first copy the file efile.txt to the same directory that API is located in. You may also want to modify your api.env file to take advantage of all of your systems capabilities. (A sample api.env file is provided with the rubik program and should work for most systems.) Start the API and consult dcorn2.ari, dedge2.ari, bfast3.ari and rubik15.ari. Before running the first time, you should type "makeehash." If you fail to type "makeehash", the profile tables will not be used in the search (the conventional heuristic will be uesed instead) and the search will take longer and consume more memory. You will see a lot of data dumped to the screen to indicate the data that is being hashed. You are now ready to query.

A number of cubes are already defined. If you type "goal(A).", A will be instantiated to be the state of the cube when the goal is satisfied. If you type "start3(A).", A will be instantiated to a predefined cube that has been subjected to 3 moves. There are several such predefined predicates. To solve a cube that has been subjected to 5 moves, type "start5(A), bestfast(A,Sol,0.99,1), showall(Sol).". The arguments of bestfirst are explained in the program documentation. For most practical purposes, the above arguments will produce an A* search. To theoretically guarantee an A* search, change "bestfast(A,Sol,0.99,1)" to "bestfast(A,Sol,1,1)". However, the former arguments are generally recommended. If you wish to define your own cube, you may type something like: "goal(Solved), move(Solved, gr, NoLongerSolved), bestfast(NoLongerSolved, Solution, 0.99, 1), showall(Solution).". This particular example takes a solved cube, subjects it to a green-right move, solves the cube, and reports the solution.

During the search process you will see a lot of data on the screen. This data is mainly intended for diagnostic and demonstration purposes. It is not particularly well-formatted and can be removed by deleting write statements from the program.

Copyright 1996, David Lee Winston Miller. All rights reserved.

Downloads:
efile.txt     api.env     dcorn2.ari     dedge2.ari     bfast3.ari     rubik15.ari

Note: You must download all of the files and must have Arity Prolog to run the rubik15.ari program. The heuristics generator program is not included above. Instead, a small sample profile table is included (efile.txt). Please read terms at beginning of program files. Program is not intended to be a product but rather a tool for artificial intelligence research. If you are looking for a really cool cube program, there are better programs on the Web than this one in terms of entertainment and graphics. All downloads, Copyright 1996, David Lee Winston Miller. All rights reserved.

Professional Resume         Homepage         Email           Rubik Demo          Beginning of Article

This page has been accessed   times since noon 11-29-96.