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. 
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 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 3digit, 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 baseN number than (1, 0, 0).
Each element of the piece vector contains a nonnegative integer. Zero indicates that the unit cube is not occupied, whereas any nonzero value indicates that the unit cube is occupied. 

Figure 3) The coordinate system used for this program. 
The exact value of the nonnegative 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 nonnegative 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 nonnegative 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 leastsignificant digit and the Z coordinate of the center of mass as being the mostsignificant 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 iterator for the class translation is a bidirectional 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 righthand 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. 
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 righthand rule). It contains a bidirectional 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 listed above use several private member functions, which are listed below:


Class rotation also includes a bidirectional 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.

Below are all the source files for the soma cube program. 