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

• cube.plg describes the problem space for the 1x1x1 cube puzzles.
• bigcube.plg describes the problem space for the 2x2x2 cube puzzle.

Values

• Dir :- direction, one of [n, s, e, w, ne, se, sw, nw]
• Piece :- Colour-Piece, for example b-1 is the first piece of the blue cube.
• Orientation :- [0,1,2,3]/[up,dn], for example 3/dn. This is the hardest concept to visualise. The number is the number of 90 degree rotations clockwise. up/dn is whether the piece is flipped left-to-right. Note, it's flip then rotate. 0/up is the default position, 0/dn is just flipped.

  If this doesn't make sense, look in cubestuff.plg for the rotate/3 predicate, it has some helpful pictures.

• Side :- [0,1,2,3,4,5,6,7], the bit string that represents the side when looking at the piece from above, going clockwise (ignore the corners). A one means there is a block there, a zero means there isn't. Note, that matching pieces don't match the obvious way. A piece with a side 6 (110) on the left will match a piece with a 4 (100) on the right. See the flip/2 and match/2 predicates.
• Position :- pN, eg p5. Positions are abstract in the sense that the don't necessarily represent anywhere in particular. However, for the purposes of output you can specify a position so mere mortals can read the results.

Predicates

• 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 there.

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.

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

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

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

Source can be downloaded here: cubepuzzle.tar.gz.