The Cube Puzzle

Up: Puzzle solving by computer  
Prev: Tagged types for PostgreSQL   Next: The pentomino 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 here. They 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 available anymore.

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.

The problem

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 files: 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 predicates:

Values

Predicates

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 thing.

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] lists.

The solution

  1. Careful use of the setof/3 predicate yields sets of all the possible pieces, locations, corners and edges.
  2. 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.
  3. 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.

  4. 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 solutions.

Speed

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.


Up: Puzzle solving by computer  
Prev: Tagged types for PostgreSQL   Next: The pentomino puzzle  
By Martijn van Oosterhout (kleptog (at) svana.org)
Copyright © 2000-2006 - Last modified 3/04/2006