An example of some work I have done using C++.


Description of problem:

This program solves the soma cube problem in 3 dimensions for a cube with an arbitrary number of pieces.

A size 3 soma cube made up of 6 pieces is shown below. I call it size 3 since there are 3 unit cubes along each edge of the completed cube. The puzzle consists of putting together the various pieces on the left to form the cube on the right.

Figure 1) The soma cube problem: Assemble all the pieces on the left to form the cube shown at right.

To run the program:
In order to run the program you will need to download the source code (which are listed at the end of this page) , compile and link it.

To run the program type

puzzle [argument] < input_file_name>

The program's name is 'puzzle'. The argument is optional, and represents the number of solutions the user would like to see. If no argument is entered, all the unique solutions are printed to the standard output. input_file_name is the name of a file describing the size of the soma cube, the number of pieces the program is to assemble, and each piece.

program input

The format for the input file is as follows:

2 // length of edge
3 // number of pieces
11 // first piece
10
00
00
11 // second piece
10
00
00
11 // third piece
00
00
00

where the remaining text on a line after the double slashes (//) is ignored. The first number indicates the number of unit cubes per edge for the cube. Hence, the example above would represent a 2 by 2 by 2 soma cube problem. The following number (i.e. 3 in the example above) represents the number of pieces the program must assemble to construct the soma cube. The remaining numbers describe the pieces.

Each of these remaining numbers describes a unit cube of a piece. A zero means that the unit cube is not occupied, whereas any other character means that the unit cube is occupied. Each piece consists of 8 numbers, since we need 8 unit cubes to construct a 2 by 2 by 2 soma cube. If the sum of the unit cubes occupied in each piece does not add up to the volume of the soma cube desired, the program prints an error message to standard error and quits. A more precise description of the geometry describing each piece is given below, when I describe the class piece.

program output

The output of the program is printed to standard out. An example is shown below. In this case the user asks for the first two unique solutions, and gives inp2 as the name of the input file.

$ puzzle 2 < inp2

Solution 1 is

12
13
22
13

Solution 2 is

22
13
12
13
Figure 2) A graphical representation of the solution given at left.

The first number of solution one (i.e.1) represents the piece that occupies the lower, front left unit cube of the soma cube. The second number (i.e.2) represents the piece that occupies the lower, front right unit cube. The two numbers on the next line (i.e. 1 and 3) represent the lower, back left and right unit cubes, respectively. The next four numbers represent the top layer of the finished cube (compare with Figure 2)

How the program works

I will now describe each specific class used in the program, and how each works and interacts with the other classes.

class piece

This class is used to represent individual pieces or sums of pieces. The geometry I used has been hinted at already in describing the program's output.

Each unit cube is represented by an element of a 3 by 3 by 3 vector of integral type (i.e. vector< vector< vector <int> > >). I can access the individual elements of each piece using the operator [ ]. Thus I can write pieceX[x][y][z] to access element (x,y,z) of piece X. Of course, (x,y,z) also stands for the spatial coordinates of the unit cube that the element represents. The geometry used is shown in Figure 3, which indicates the exact coordinates of each unit cube in a size 2 soma cube.

It is convenient to think of the coordinates as representing a 3-digit, base N number (where N is the size of the soma cube). In this scheme we can refer to 'larger' or 'smaller' coordinates without confusion. For example, the coordinates (0, 1, 0) < (1, 0, 0) since (0, 1, 0) represents a smaller base-N number than (1, 0, 0).

Each element of the piece vector contains a non-negative integer. Zero indicates that the unit cube is not occupied, whereas any non-zero value indicates that the unit cube is occupied.

Figure 3) The coordinate system used for this program.

The exact value of the non-negative integer indicates the piece number (or color, if you like). Thus, in the example shown in Figure 2, element (0,0,0) of the first piece would contain the value 1, but element (0,0,1) would contain the value zero (each piece is represented as an entire soma cube with only certain unit cubes occupied). For the piece representing the solution shown in Figure 2, element (0,0,0) contains the integer 1 and element (1,0,0) contains the integer 2. That a single piece contains elements with different non-negative integers indicates that the piece was built up from smaller pieces. This organization makes it convenient for adding pieces together, for checking which pieces we have added, for comparing solutions, etc.

Each piece is also equipped with an ID number, which is the number given to the piece when it is read in from the input file. The ID number corresponds with the non-negative integer stored in each occupied element. Hence the first piece read in will use the integer 1 to indicate that a certain unit cube is occupied (and 0 for unoccupied, of course), and will have a piece ID of 1. The second piece will use 2 as its ID number and will use the integer 2 to indicate that a given unit cube is occupied. The trend is obvious.

Finally, each piece also contains a size, which is the size of the soma cube it will eventually be a part of.

There is also a member function in the class piece that returns the centroid of the piece. The centroid (for lack of a better term) is analogous to the center of mass of the piece, but is returned in base 10 form. The centroid is calculated as follows:

where Q is the Heavyside function (i.e. a step function). Thus one can think of the X coordinate of the center of mass of the piece as being the least-significant digit and the Z coordinate of the center of mass as being the most-significant digit of the centroid. Having access to the centroid is convenient for iterating through all possible translations of a piece, as will be discussed in connection with the class translation.

class Translation

Class translation is used to translate pieces throughout a soma cube volume, in order to find a space into which the piece will fit. More precisely, it translates the occupied unit cubes throughout the soma cube volume, without changing the spatial relationship between the unit cubes. It takes as an argument a piece, which is the piece it will translate. Class translation provides an iterator which may be used to iterate through all possible translations of a piece.

The class translation itself contains two private data elements: a 'current piece', and a 'last piece'. The last piece is initialized at construction to be the given piece, translated to the last possible position (i.e. the position with the largest possible centroid that is still inside the cube.) This is done since the translation iterator often needs to compare the current piece position against the last piece, to see if it is possible to continue translation.

In order to accomplish translations, class translation provides the following member functions:

  1. nextPosition and prevPosition which shift the current piece position (i.e. the current piece) to larger or smaller coordinates, respectively. If they are able to move the piece, they return a Boolean value of true, otherwise they return false. These functions make use of another member function of the class translation,
  2. shift. The function shift takes as arguments the axis along which to shift (X, Y, or Z) and the direction (positive or negative). If it is able to shift the current piece in the given direction, it returns true (and shifts the piece), if not it returns false and does not shift the piece. In order to determine if it can shift a piece, it uses the function
  3. sliceOpen. This function determines if there is an unoccupied slice available in the direction in which we want to shift the piece. It takes as arguments the axis along which we are shifting, and the slice number we would like to check. The slice number represents a slice of the cube perpendicular to the axis along which we are shifting. Although this number can be arbitrary in principle, it is always either zero or the maximum (i.e. the cube size 1) in this program. The reason for this is that if a slice representing an exterior face of the soma cube is not occupied, then it is certain that we may shift the piece in the appropriate direction while still keeping the piece inside the soma cube.
  4. The member function setPosition sets the position of the current piece to the position of its argument, which is a piece. This is used by the iterator to set the position of the current piece, before asking for the next or previous translation.
  5. Finally, class translation allows the user to see the current piece by using the member function getPiece, which returns a const reference to the current piece.
The iterator for the class translation is a bi-directional iterator that allows dereferencing (in which case it returns a piece), pre- increment and decrement, and Boolean comparison with other translation iterators to determine, for example, which pieces have been translated the most. The iterator class stores a piece, along with the centroid of the piece and an unphysical centroid (one that indicates a piece is outside the soma cube). In order to increment or decrement, the iterator first compares its centroid against the unphysical centroid to see if it is at the position corresponding to 'last' (i.e. one past the last physically possible translation). It then proceeds to translate its own piece by using the class translation. First it sets the current position of class translation's piece to the position of the iterator's piece (using setPostion), then it asks the class translation for the next or previous translation. If the translation is successful, the new position of the piece is copied from the class translation. If the translation is not successful (in the case of incrementing the position), it means the iterator is already at the last physically possible position so it sets its centroid to the unphysical centroid to indicate it has arrived at last.

class rotNumber

Class rotNumber (rotation number) is used by the class rotation to rotate pieces by 90 degrees about the X, Y or Z axis. Class rotNumber contains a private data element that is a 3 element vector. The first element of this vector represents rotations (following the right-hand rule) about the X axis, the second element rotations about the Y axis and the final element rotations about the Z axis. Thus the rotation number (1, 2, 0) would mean rotate once around the Z axis, twice about Y and none about X (the rotation numbers are represented in reverse order Z, Y, X, for reasons that will become clear). Note that the order in which the rotations are executed is important.

In three dimensions there are 24 possible 90-degree unique rotations about the three orthogonal axes. Using the rotation number convention, these rotations are:

1: (0, 0, 0) 4: (0, 0, 3) 7: (0, 1, 2) 10: (0, 2, 1) 13: (0, 3, 0) 16: (0, 3, 3) 19: (1, 0, 2) 22: (1, 2, 1)
2: (0, 0, 1) 5: (0, 1, 0) 8: (0, 1, 3) 11: (0, 2, 2) 14: (0, 3, 1) 17: (1, 0, 0) 20: (1, 0, 3) 23: (1, 2, 2)
3: (0, 0, 2) 6: (0, 1, 1) 9: (0, 2, 0) 12: (0, 2, 3) 15: (0, 3, 2) 18: (1, 0, 1) 21: (1, 2, 0) 24: (1, 2, 3)

Note that there is a break in the sequence of rotation numbers in going from rotation 20 (1, 0, 3) to rotation 21 (1, 2, 0). This is to avoid the non-unique rotations that would occur if we followed the normal sequence. Looking at the rotation numbers it is clear why I ordered there components Z, Y, X; this allows one to count (in base 4) in rotation numbers (except for the break at rotation 20). Thus class rotNumber produces a number that is a member of the list above, with the addition of a number to represent last, for which I use (6, 6, 6) (bad omen?). Decrementing or incrementing a rotation number will produce the next one or the previous one on the list.

In addition, class rotNumber allows the user to take 'differences' between two rotation numbers, in order to tell what rotations are needed to go from one rotation to another. For instance, to go from rotation 5 (0, 1, 0) to rotation 8 (0, 1, 3) one only needs to rotate the piece in question twice more about the X axis, instead of starting with the unrotated piece and rotating in once about Y then thrice about X. For some differences this shortcut is not possible (unless we rotate in the negative direction, which we do not). For example, in going from rotation 12 (0, 2, 3) to rotation 13 (0, 3, 0), we are forced to start with the unrotated piece and rotate it about the Y axis 3 times in order to reach (0, 3, 0). We cannot start with the piece at rotation 12 since rotation 12 involves 3 rotations about X, which we cannot undo. The ability to take the difference between two rotation numbers allows the user to find the most efficient way to rotate a piece in order to attain the next unique rotation of that piece.

Class rotNumber contains the operators ++, --, - and all the Boolean operators. It also contains a public member function setSize, which is used to initialize the class's private data (vector) to a given size (although I only used three in this program). It also contains copy assignment operators which can take, as right-hand side arguments, either other rotation numbers, or integer values. This way I can easily set the value of a rotation number to (0, 0, 0) or to (6, 6, 6) just by assigning it the value 0 or 6.

I made class rotNumber a class template just for practice, it is not vital for this program.

class rotation

This class takes a piece as an argument in its constructor, and uses class rotNumber to rotate the piece about the X, Y, or Z axis (following the right-hand rule). It contains a bi-directional iterator that allows the user to iterate through all unique rotations of the piece. The private data elements of class rotation are a list (the nodes of which hold a structure containing the piece and its corresponding rotation number), and a structure identical to the structure contained in the list nodes, called lastNode, which is used by the iterator to see if we have exhausted all possible rotations. Class rotation also contains a Boolean variable, listOpen, which is set to false if the list contains all possible unique rotations of the piece in question.

The public member functions of class rotation are:

  1. getPiece, which takes as an argument a rotation number and returns the piece from the rotation list corresponding to that rotation number. A precondition for this function is that the piece desired is already on the list.
  2. genNextRotation accepts a rotation number as an argument and generates the next rotation according to the sequence of rotation numbers listed above. This function will only generate unique rotations, so it checks each new rotation it produces against the rotation list, to see if the new rotation is unique or if it is equivalent to one of the previous rotations. If it finds another unique rotation after the one indicated by its argument, it will update its argument to indicate the new rotation it has found. It also stores the new rotation on the rotation list. When it does not find another unique rotation, it sets listOpen to false to indicate that all unique rotations of the piece have been found.
  3. genPrevRotation accepts a rotation number as an argument and generates the previous rotation according to the sequence of rotation numbers. This was done for practice, and to verify that the class worked properly. It is not used by the present program since it only iterates forward through the rotations. If the list of rotations is closed (i.e. listOpen is false) genPrevRotation simply scans the list for the rotation prior to its argument, then updates its argument to reflect the rotation it found. If the list is still open, and the argument to genPrevRotation is greater than the rotation number of the last item on the list, then the function calls genNextRotation to generate all the rotations up to its own argument. It then scans the list of rotations to find the rotation before its argument.
The public member functions listed above use several private member functions, which are listed below:
  1. memberOfList accepts a rotation number as an argument and checks to see if that rotation is on the list of rotations.
  2. normalize accepts a reference to a piece as an argument, and uses the class translation to translate the piece to its minimum position.
  3. rotatePiece90 takes two arguments, a reference to a piece and an axis, which is an enumerated type (X, Y, or Z). It rotates the given piece by 90 degrees about the axis indicated, following the right-hand rule. rotatePiece90 uses rotateSlice in order to accomplish the rotation of the entire piece.
  4. rotateSlice is the workhorse of the class. As arguments is takes a reference to a piece, the axis about which to rotate, the slice number, and two integers, max and min. It rotates a slice that perpendicular to the axis indicated. The slice that is rotated is indicated by slice number, which is between 0 and the size – 1 (where size, recall, is the size of the soma cube). In order to rotate a slice it starts with the outermost ring of cubes on the slice. The coordinates of these are calculated using the arguments max and min. If there are inner rings left to rotate, rotateSlice calls itself recursively, after decrementing max and incrementing min, and rotates all the inner rings of cubes in the slice.
Class rotation also includes a bi-directional iterator (although I only use the increment operator in my driver). This iterator allows the user to iterate through all the unique rotations of an arbitrary piece.

the driver

The driver uses the classes listed above to solve the 3 dimensional soma cube problem for cubes of arbitrary sizes.

The function that does most of the work is called assemble, which uses recursion and backtracking to solve the problem. It takes six arguments: a piece that will serve as the solution. For the initial call this piece is empty (i.e. non of its unit cubes are occupied). The second argument is a piece list, which is a vector containing pointers to pieces. These pieces are those read in from the data file. The third argument is a counter that counts which piece we are currently trying to fit into the final soma cube. The fourth argument is the solution number, which is used to keep track of the number of solutions that have been found. The fifth argument is the maximum number of solutions desired by the user. If this argument is zero, the function assemble will print out all the solutions it finds. The final argument is a list containing all the previous solutions found, so that we may compare new solutions with previous one to ensure that we only keep unique solutions.

A solution is considered unique if it does not match any of the previous solutions under all possible rotations. This is the only criteria I use for uniqueness, I consider all the pieces as distinct, even if they have the same shape.

The function assemble works by first checking to see if the index, which indicates the number of the piece we are trying to fit, is larger than the number of pieces on the piece list. If it is, we have fit all the previous pieces, so we have found a candidate solution (it still must be checked against the piece list to see if it is unique). In this case the function returns true, and the recursion stops.

If there are still pieces on the piece list that assemble must fit into the soma cube, the function proceeds to try to fit the remaining pieces. It does this by iterating through the remaining pieces on the piece list and for each piece it iterates through all the possible rotations of each piece, and all the possible translations for each rotation. To do this it uses the iterators supplied by class translation and rotation.

The first thing done when we enter the loop which iterates through the remaining pieces on the piece list is check to see if the previous piece fit. If it did, we continue. If not, we don't bother attempting to fit the remaining pieces and backtrack instead. Next we check to see if we have already found enough solutions to satisfy the user. If not, we continue searching for further solutions.

The function then iterates through all of the rotations of the current piece, and for each rotation all of the translations, trying to fit the piece into the soma cube solution. If the piece fits the function assemble calls itself recursively, incrementing the index to indicate the it has fit the current piece. At this step, we are attempting to fit the remaining pieces. If this succeeds assemble will return true, in which case we have a solution and we check it against the solution list to see if it is a unique solution. If so, we print it out, then backtrack, removing the most recently fit piece in order to search for further solutions. If the attempt to fit the remaining pieces via the recursive call fails, we backtrack and attempt to fit the current piece in a different position. The process continues until we have found all the solutions requested by the user, or all the unique solutions possible, whichever is fewer.

The function assemble uses other global functions to accomplish its task. These are relatively simple functions and listed here for completeness:

  1. fitTogether is a function that accepts two pieces and returns true if these pieces may be fit together, otherwise it returns false.
  2. isUnique accepts a list of pieces (the solution list) and a piece as arguments. It then rotates the piece through all the unique rotations and compares each rotation against all the pieces on the solution list. If there is a match, the piece does not represent a new solution, and the function returns false. If the piece is a unique solution, the function returns true and the piece is added to the solution list.
  3. prePieceFits accepts a piece identification number and a piece (the solution piece) and checks whether the piece indicated by the piece ID number is contained within the solution piece. If so , it returns true, otherwise it returns false.
  4. putTogether accepts references to two pieces as arguments and does what its name suggests, which is to combine these pieces into one piece. A precondition for this function is that the two pieces fit together (i.e. have no occupied unit cubes in common). This is checked prior to calling this function using the function fitTogether.
  5. takeApart accepts references to two pieces as arguments, and removes the second piece from the first piece (which is the solution piece).


Below are all the source files for the soma cube program.
  1. puzzle.cpp
  2. piece.h
  3. piece.cpp
  4. rotation.h
  5. rotation.cpp
  6. rotNumber.h
  7. rotNumber.cpp
  8. translation.h
  9. translation.cpp