The Cube Puzzle
Here I describe the cube puzzle. You know, the ones with 6 pieces with
blocks on the edge that you have to make into a cube? There are examples to
be seen here
and here and
are mostly sold as promotional gifts but I first came in contact with them
as an actual puzzle. They came in a set of six in different colours and
difficulty levels (red being the easiest, followed by orange, yellow, green,
blue and finally purple being the hardest). These don't appear to be
The puzzle is to take the peices and form a cube. However, it can also be a
puzzle to get them back into the flat form. The big puzzle is to take a
subset of all the peices (36 total) and make a big 2x2x2 cube. I never
managed it by hand, but by computer I finally did it.
In a break from previous puzzles, I actually used Prolog to solve this one.
This due partially to me wanting to use Prolog for something and partially
because the problem seemed to better map to Prolog than to C. In Prolog, you
simply define what the solution looks like and it will go and find one (or
all of them) for you.
Here I used SWI-Prolog. Although the language is quite standardised, some
things may not work. Please let me know if you have any problems.
Actually these cubes form the basis for all sorts of problems. So the common
stuff is abstracted into a file called cubestuff.plg. There are two
I say problem space because that's precisely what it defines. The program
works from a database you define which is based on the following values and
- cube.plg describes the problem space for the 1x1x1 cube puzzles.
- bigcube.plg describes the problem space for the 2x2x2 cube puzzle.
If you're find all this hard to visualise, you're not alone. If you look at
the source files, you'll that I've put in several ASCII drawings of the
pieces and structures so you can see how the predicates relate to the real
- s(Dir,Piece,Side) :- On Dir (n,s,e,w) side of piece Peice, give the Side value.
- c(Dir,Piece,Val) :- In corner Dir (ne,se,sw,nw) of piece
Piece, there is a corner Val (0 or 1). You only need to specify 1, anything
you leave will be assumed to be zero.
- p(Dir,Position1,Position2) :- If you go direction Dir from
Position1, you get to Position2. Note, you better have something going from
Position2 back to Position1, otherwise it'll never know which sides to test.
- cr( [ [Position,Dir], ... ] ) :- Set of Position/Dir pairs
indicating which corners meet at the same point. The test is basically that
for a given corner, only one of the pieces in those positions has a corner
The last two predicates are not used in the solution funding, but for
drawing the output. Drawing the result to the screen is extremely useful and
a lot easier to read than just an array of [Piece,Position,Orientation]
- char(Position,'char') :- Use given character when displaying
given Position. Any character is allowed, though obviously you should try
to avoid to adjacent positions using the same chars.
- pos(Position,X,Y) :- Draw the position at the given (X,Y)
coordinates. They can't be negative. It's the user's responsibility to
ensure they don't overlap.
- Careful use of the setof/3 predicate yields sets of all the possible
pieces, locations, corners and edges.
- Initialise the result set as an array of [Piece,Position,Orientation]
where each position is given exactly once and the other two values are unknown.
- The main predicate is check2(Pieces, Set, Pairs) (not
imaginative, I know). Pieces is the set of pieces available for use. Set is
the result set at this point. Pairs is the remaining edges to test. Each
piece must appear in either the Pieces list, or in Set.
It basically recursively tests each edge (from Pairs). It uses member/2 to
make sure it uses a piece from the Set. This also makes a choice point so
from here it can backtrack to find other ways.
- Finally, if we have a set which satisfies all the edge requirements,
check all the corners. Mostly it's a formality but with the big cube and
so many similar pieces, you need this at the end to weed out invalid
For a single cube scenario it finds a solution in seconds. For the big cube
it takes a while (depending on your computer) but it eventually gets there.
It will find multiple solutions, as long as you keep asking. It will find
duplicate solutions also. It's pretty hard to avoid this given that a single
cube can be oriented in 24 different ways that are actually the same.
There is some code (getdistinctpieces/1) which tries to determine
the pieces that are map to themselves, so we could cut down on the number of
searches and duplicates. It doesn't work yet though.
To use it, basically you type:
> findsolution(X), drawsolution(X).
drawsolution/1 is in output.plg, so you'll have to load that first
if you want output.
Source can be downloaded here: cubepuzzle.tar.gz.
By Martijn van Oosterhout (kleptog (at) svana.org)
Copyright © 2000-2006 - Last modified 3/04/2006