Soma Cube Solver

• Download source - 224 KB

Introduction

This project solves the Soma Cube Puzzle using a backtracking algorithm and allows you to visualize the workings of the algorithm using a 3-D image rendered by WPF.

Background

I recently came across an interesting algorithm by Kazem Jahanbakhsh to solve the Soma Cube. The Soma Cube is the subject of my Soma Cube WPF project. If you are not familiar with the Soma Cube Puzzle, you might want to read that article to get familiar with the piece names, cube labels of the pieces, and how to orient the camera.

The algorithm solves the Soma Cube Puzzle by initially placing the L Tetra Cube, then placing the Branch Tetra Cube so it doesn't intersect the L Tetra Cube, then placing the Right Screw Tetra Cube so it doesn't intersect with the first two pieces, and so on until the puzzle is solved. The algorithm uses a technique called backtracking. By backtracking, I mean when the algorithm is placing the pieces, if a piece will not fit, the current iteration ceases and a new one is started using a different initial condition. I will go into the details of the workings of the algorithm below.

Using the Code

Download and extract the solution, and open SomaCubeSolver.sln with Visual Studio. It consists of the following projects:

1. SomaCubeSolver - the Java code of Kazem Jahanbakhsh, converted to C#. It produces an output file of solutions identical to the Java version (I used Eclipse Kepler Service Release 1 Build id: 20130919-0819 to run the Java code). The name of the output file of solutions is solutions.txt. I made some small improvements over the Java code: added comments; used a Dictionary rather than a HashTable; used const instead of hard-coded numbers; and used integers as the Dictionary key rather than strings.
2. SomaCubeWPF2 - a WPF 3D application to help visualize the running of the algorithm. It uses a file generated by the SomaCubeSolver which the Java version does not generate. Using that file, I'll show you how to animate the algorithm as it runs. The effect is pretty cool. SomaCubeWPF2 also has a UI that makes it easy to visualize how the BitArray class is used by the algorithm.
3. SomaCubeLib - a library shared by SomaCubeWPF2 and SomaCubeSolver.

Build the solution using "Build->Rebuild Solution" from the Visual Studio Main Menu. Since the first two projects depend on the SomaCubeLib project, that project is built first. A nice feature of Visual Studio is the ability to set this build order by right-clicking on the Solution, then selecting "Project Build Order..."

Cube Coordinates and the BitArray

Bit Array

At the heart of the algorithm is the .NET BitArray class. I use this class since it is the closest thing .NET has to the Java BitSet class used in the original Java code. However, there are some methods the Java BitSet has that the .NET BitArray class is missing, for example, the AndNot method. I've included the missing methods using C#'s great extension method feature. They are in the SomaCubeLib project's ExtensionMethods class.

Cube Coordinates

In order to understand the algorithm, we need to first understand the Cube Coordinates. Imagine the 27 smaller cubes assembled into the single Large Soma Cube and centered at the origin. The small cubes are numbered 0 - 26 starting with cube 0 at +1, -1, -1; cube 1 right above cube 0 at +1, 0, -1; cube 2 right above cube 2 at +1, +1, -1; and cube 3 right next to cube 1 at 0, -1, -1, and so on for all 27 small cubes. You might want to take a moment to familiarize yourself with this numbering system as shown in the image below (You might also want to print CubeNet.png, cut out the image and assemble a paper model of the large cube showing the numbered small cubes.) We assume each small cube is a unit cube, that is, it is one unit in height, width and depth.

The Algorithm

I'll go into more details of the algorithm shortly, but as a high level introduction, we first assume we are starting the Soma Cube with all of the small cubes empty. We then place the L Tetra Cube in small cube positions 1, 0, 3, and 6 as shown in the image below. A corresponding BitArray object will have only its 0, 1, 3, and 6 elements set. In other words, within the BitArray object representing the large cube, a cleared bit (0) means the small cube is not occupied, and a set bit (1) means the small cube is occupied. The not-occupied (cleared or 0) small cubes are shown in light green, and the occupied (set or 1) small cubes are shown in gray in the image below. (I'll show you how to set colors other than gray shortly.)

As the algorithm runs, the strategy is to keep track of which small cubes are occupied and which are not occupied. If the small cubes are not occupied by a piece, the algorithm will put a piece in the empty small cubes. For example, assume after the algorithm has run for a while, all the small cubes are occupied except for cubes 22, 25, and 26 as shown in the image below (having your paper model is handy for picturing this.) The algorithm can then determine that the L Tri Cube can fit into this shape, and will therefore place it in the unoccupied spaces, thus completing the Large Soma Cube.

Bit Operations - Or, And, AndNot

Before we get into the code of the algorithm, I would like to talk about a tool I developed to help visualize bit operations on BitArray objects. Feel free to skip this section if you are comfortable with bit operations. In the image below, on the left-hand side, the sequence of 27 bits in the blue border represents the Large Soma Cube on the right. The sequence of 27 bits in the purple border represents bits (the auxiliary bits) which can be set with the radio buttons or with a hexadecimal number entered into the text box labeled "Hexadecimal Number". The 3 buttons in the green border represent the operations that can be performed on the bits within the blue border (the Cube) by the bits within the purple border (the auxiliary bits). The buttons and operations are:

1. Or - set bits on in the Large Soma Cube to add a piece
2. And - set bits off in the Large Soma Cube to test if a piece can be added
3. AndNot - clears all of the bits in the Large Soma Cube whose corresponding bit is set in the specified BitArray; this is used to remove a piece

"Or" Operation

To see the "Or" operation in action, for example, to set S Tetra Cube in the +Z face of the Large Soma Cube, click the radio buttons for Bits 19, 21, 22, and 24 to set them to 1. Or enter B4 in the "Hexadecimal Number" text box and press "Enter". The bit string "000 000 000 000 000 000 010 110 100" will be displayed in the auxiliary bits, the bits within the purple border. Now click "Or" in the green bordered area and observe that the bits in the blue bordered area are set the same as the auxiliary bits and the corresponding small cubes in the Large Soma Cube are displayed in gray, meaning they are occupied, as shown in the image below. (This color can be set in app.Config SmallCubeSetColor).

To add another piece, the T Tetra Cube for example, click the radio buttons for Bits 0, 9, 10, and 18 to set them to 1, or enter 40301B4 in the "Hexadecimal Number" text box and press "Enter". The bit string "100 000 000 110 000 000 110 110 100" will be displayed in the auxiliary bits. Next, click Colors on the menu bar and select the T Tetra Cube color, then click "Or" in the green bordered area and observe that bits in the blue bordered area are set the same as the auxiliary bits and the corresponding small cubes in the Large Soma Cube are displayed in the new color, meaning they are occupied, as shown in the image below. As the algorithm progresses, it uses this "Or" method in the code - like this theCube.Or(tempPiece) - to add pieces to the Large Soma Cube as we will examine in more detail shortly.

"And" Operation

To see how the "And" works, set the S and T Tetra Cubes as described above. Click the "Clear" button in the purple bordered area. All the auxiliary bits are cleared. Suppose we want to see if the L Tri Cube will fit into the Large Soma Cube in positions 23, 25 and 26. Click bits 23, 25, and 26, or enter B in the "Hexadecimal Number" text box and press "Enter". Click "And" in the green bordered area and observe how all the small cubes are cleared, making the Large Soma Cube empty. The algorithm uses this "And" method to determine if a piece can be added. We will see this later on in a line of code that says if (tempCube.IsEmpty()) to see if a piece can fit.

"AndNot" Operation

To see how the "AndNot" works, set the S and T Tetra Cubes as described above. Click the "Clear" button in the purple bordered area. All the auxiliary bits are cleared. Set bits 19, 21, 22, and 24 to 1, or enter B4 in the "Hexadecimal Number" text box and press "Enter". These bits represent the S Tetra Cube. Click "AndNot" in the green bordered area. Note how the S Tetra Cube is removed from the Large Soma Cube. The algorithm uses this "AndNot" method to remove a piece. We will see this later on in a line of code that says theCube.AndNot(tempPiece).

Menu Bar "View"

You can use View from the Menu Bar and turn off parts of the Large Soma Cube. For example, to see small cube #13 - at the very center, click "View"->"+Z Layer Hidden". To restore that layer click "+Z Layer Visible".

Non-Isomorphic Orientations

Now that we've covered the Cube Coordinates and the Bit Operations, the next thing to understand is the non-isomorphic orientations of the parts. Since isomorphic means "the same shape", the T Tetra Cube, for example, is the "same shape" after rotating it 180° about its Y axis as shown in the figure below (note how the face labels and axes are different, showing that it was actually rotated!) This is an example of an isomorphic orientation.

In contrast, a non-isomorphic rotation means the part has a "different shape" after rotating it 180° about its Y axis as shown by the L Tri Cube in the figure below.

The non-isomorphic orientations for each piece are stored in a 3 dimensional array. Each orientation (indicated by case 1, case 2, etc. in the code snippet below) consists of 4 3D points. For the T Tetra Cube, I've annotated the code with a diagram of the axes and the piece, using the cube labels to show the orientation. So for case 1 for example, the piece is along the -Z axis (because Z is -1 for all 4 points) and the T Tetra Cube is oriented as shown in the image below.

The upper case letters - D, B, A, and C - refer to the piece's cube labels described in Part 1. The cube labels are shown in a comment above the line of code with the 4 points. Here is an snippet of code for the T Tetra Cube's non-isomorphic orientations:

int[,,] TTetraCubeNonIsoOrient =
{
	//     D             B             A             C
	//  cube 4        cube 1        cube 2        cube 0
	{{ 0,  0, -1}, {+1,  0, -1}, {+1, +1, -1}, {+1, -1, -1}}, // case 1  Z=-1
	#region doc
	//          +Y
	//           |
	//         A |
	//         B D---  -X
	//         C
	// Freedom of movement will be {-1,  0, +2}
	#endregion

	//     A             B             C             D
	// cube 5          cube 4        cube 3       cube 1
	{{-1, -1, -1}, { 0, -1, -1}, {+1, -1, -1}, { 0,  0, -1}}, // case 2  Z=-1
	#region doc
	//          +Y
	//           |
	//           D---  +X
	//         A B C
	// Freedom of movement will be { 0, +1, +2}
	#endregion
...

Case 1 is shown in the image below in the Z=-1 plane:

There are 3 other orientations in the Z=-1 plane, 4 in the -X plane, and 4 in the -Y plane for a total of 12 orientations.

In addition to each of the 12 non-isomorph orientations, there is also a 3 dimensional array of integers indicating how much a piece can be moved (you can think of this as the piece's "Freedom Of Movement"). So for case 1 with the T Tetra Cube oriented vertically in the Z=-1 plane and X=+1 plane, the freedom of movement is {-1, 0, +2} meaning the piece can be moved 1 unit in the -X direction, 2 units in the Z direction and it is not free to move in the Y direction (because the T Tetra Cube is 3 units in height, the same as the Large Soma Cube.) The 12 freedom of movement arrays are stored in a two dimensional array int[][] TTetraCubeFreedomOfMovement, in this example, the two dimensional array is a 12 x 3 array since there are 12 orientations.

Permutations of Non-Isomorphic Orientations

Given the orientations and freedom of movement for each of the seven Soma Pieces, the next challenge is to determine all of the possibilities for a specific orientation. The key data structure to store the various non-isomorphic orientations of the parts is a List of BitArray objects: List<BitArray>. It is worth repeating that each BitArray object has 27 bits, each one corresponding to a small cube in the numbering scheme shown above. A cleared bit (0) means the small cube is not occupied, and a set bit (1) means the small cube is occupied. Since we have a list for each of the seven Soma pieces, we will use an array of seven lists to keep track of the orientations: pieceOrientationList = new List<BitArray>[NumPieces].

The FillPieceOrientationList() method takes the non-isomorphic and freedom of movement arrays and builds a list of the orientations. For example, for the T Tetra Cube, the TTetraCubeNonIsoOrient and TTetraCubeFreedomOfMovement arrays are passed to FillPieceOrientationList() which in turn creates the sixth list of the orientations, pieceOrientationList[5], for the T Tetra Cube. In all total, there are 96 permutations for the T Tetra Cube. The following image shows the first 3 permutations, in the Z=-1, Z=0, and Z=+1 planes:

Algorithm in Depth

Now that we've covered the strategy, the BitArray and operations that can be performed on it, and obtained the permutations of the orientation of the pieces, it's time to put it all together. The BackTrack(int pieceNdx) method in the SomaCubeSolver project is what does the magic here. The key data structure is public BitArray theCube { get; set; } as it represents the current Large Soma Cube being built from the seven pieces. The BackTrack(int pieceNdx) method is started by calling it with a pieceNdx of 0. This starts the Large Soma Cube with the L Tetra Cube as shown here in positions 0, 1, 3, 6. The L Tetra Cube remains in this location as the algorithm runs, and the pieces are placed in this order:

1. L Tetra Cube (remains at 0, 1, 3, 6 during entire run)
2. Branch Tetra Cube
3. Right Screw Tetra Cube
4. Left Screw Tetra Cube
5. S Tetra Cube
6. T Tetra Cube
7. L Tri Cube

The BackTrack(int pieceNdx) method is then called recursively with a pieceIndex of 1 (the second piece, the Branch Tetra Cube). As BackTrack(int pieceNdx) is operating on the Branch Tetra Cube, its list of orientations is iterated over using a foreach loop:

foreach (BitArray ba in pieceOrientationList[pieceNdx])

As the foreach loop iterates, a DeepCopy of theCube is "And'ed" with the current orientation. If the current orientation does not intersect with the L Tetra Cube, tempCube.IsEmpty() will be true (as explained above), and the current Large Soma Cube is "Or'ed" with the current orientation of the Branch Tetra Cube (at 12, 15, 16, 24) to add the Branch Tetra Cube (in pink) to the Large Soma Cube (as explained above). Here is the snippet of code just described:

tempPiece = ba;
tempCube = (BitArray) theCube.DeepCopy();
tempCube.And(tempPiece);

if (tempCube.IsEmpty())
{
    theCube.Or(tempPiece);
...

At this point, this is what theCube looks like with the gray L Tetra Cube (at 0, 1, 3, and 6) and the pink Branch Tetra Cube at 12, 15, 16 and 24. (I've moved the camera to theta = 225, phi = -30, and R = 12 in order to view the Large Soma Cube from below.)

We then recursively call BackTrack(pieceNdx + 1) for the next piece, the Right Screw Tetra Cube. The Right Screw Tetra cube's list of orientations is iterated over using the foreach loop and it is determined that tempCube.IsEmpty() is true for one of the orientations (the seventh), and therefore the Right Screw Tetracube will fit in small cubes 4, 7, 8 and 17. The current cube theCube is Or'ed with the current orientation of the Right Screw Tetra Cube. At this point, this is what theCube looks like with the L Tetra Cube (in gray), Branch Tetra Cube (in pink) and Right Screw Tetra Cube (in yellow) is placed at 4, 7, 8 and 17 as shown below:

We then recursively call BackTrack(pieceNdx + 1) for the next piece, the Left Screw Tetra Cube. After 17 iterations of the foreach loop above, the Left Screw Tetra Cube (in blue) is placed at 11, 13, 14 and 22, and the Large Soma Cube is starting to take shape with 4 pieces as shown below:

The algorithm is recursively called again as BackTrack(pieceNdx + 1) for the next (fifth) piece, the S Tetra Cube. It initially places the S Tetra Cube at 9, 10, 19 and 20 as shown below:

If after iterating through the entire foreach loop, an orientation of that piece cannot be found that fits, the current stack frame of BackTrack() returns, and it starts again with a different orientation of the piece. This is what happens when the algorithm is recursively called as BackTrack(pieceNdx + 1) for the next piece, the T Tetra Cube. In other words, in the configuration of pieces in the above image, there is no way to place the T Tetra Cube (if you have a Soma model, you might want to assemble it like the image above to convince yourself this is true.) The S Tetra Cube is removed using theCube.AndNot(tempPiece) as described above, BackTrack() returns, the S Tetra Cube is placed in a different position, and BackTrack(pieceNdx + 1) is called once again for the next piece, the T Tetra Cube. Ultimately, the no solutions can be found with the Left Screw Tetra Cube in that position, so the Left Screw Tetra Cube is removed, placed in a different location, and this process is repeated until a solution is found. It takes nearly 6,000 iterations, but an orientation of the Branch, Right Screw, Left Screw and S Tetra Cubes (the second, third, fourth and fifth pieces) is found that allows the T Tetra Cube (the sixth piece) to be placed at 2, 4, 5, 8 as shown below:

A solution is found when the BackTrack() method has successfully placed all 7 pieces as indicated by this expression being true: if (pieceNdx == (NumPieces - 1)). This occurs when the L Tri Cube (the seventh and final piece) is placed at 10, 18, and 19 after over 100 iterations of the foreach loop for the L Tri Cube.

Solution Animation

To see the algorithm in action, SomaCubeWPF2 has a feature that allows you to step through the iterations not unlike you would step through code with a debugger. On the menu bar, click Solve to display the Solution Steps Dialog. It reads the file named by the variable SolutionFileName (from the SomaCubeLib) generated by the SomaCubeSolver project and displays the iterations in a List Box. This file represents just one of the 240 solutions generated by the SomaCubeSolver project.

As you click the "Next" button, the state of the Large Soma Cube is displayed. Initially, the first line in the List Box, "0. L Tetra Cube", is selected. When you click "Next", the L Tetra Cube is placed at 0, 1, 3, and 6. In the image below, the "Next" button has been clicked three times, and the Large Soma Cube now consists of the L Tetra Cube (in dark green, the first piece placed), the Branch Tetra Cube (in pink), and the Right Screw Tetra Cube (in yellow).

The selected line in the Solution Steps Dialog now says "Left Screw Tetra Cube". Clicking the "Next" button again will cause that piece to be placed. As this solution has nearly six thousand iterations, stepping through all of them is not practical nor instructive. Instead, simply type 5675 into the text box next to the "Go to line" button and click the "Go to line" button. The Progress Bar in the lower right-hand side of the Solution Steps Dialog will indicate the progress as it iterates over each line in the dialog to get the current state of the Large Soma Cube. (The code that updates the Progress Bar uses a BackgroundWorker object and is described in my WPF Clipping Plane project.) Line 5675 - the line that says "5675. T Tetra Cube" - will be selected as illustrated in the image above. Clicking the "Next" button once will cause the T Tetra Cube to be placed. As you click the "Next" button 10 more times, you can see the pieces being removed and added and arriving at the state as described above. Clicking the "Next" button a twelfth and final time will cause the L Tri Cube to be placed, solving the Large Soma Cube. You can also click on the line you want, and use the "Previous" and "Next" buttons. The MessageReceived() message handler is the method that processes the messages sent from the Solutions Steps Dialog when you click on a line or use the "Next", "Previous" or "Go to line" buttons.

Conclusion

Kazem Jahanbakhsh's algorithm is very clever and due to the fact that it uses bit operations, also very fast. WPF is great for 3-D graphics and I believe this project uses WPF to a great effect to visualize the algorithm.

History

• 23^rd March, 2019: 1.0.0.0