## Soma Solving Algorithms (How Solve101 Works)

### The Main Routine

A regular Soma structure is always made up of 27 little cubes. The first thing the program does is assign a number (from 1 to 27) to each of those cubes. Example: for the 3x3x3 Big Cube itself, it will label each of those little cubes as:

• 1-2-3
• 4-5-6
• 7-8-9 ...for the bottom layer,
• 10-11-12
• 13-14-15
• 16-17-18 ...for the "equator", or middle layer, and
• 19-20-21
• 22-23-24
• 25-26-27 ...for the top layer.

### Intersection Check

Let's go back to the 3x3x3 big cube. Looking at the seven lists, you can see that the first set of numbers for list #1 is:

• 1-2-4

Now the program looks at the first set of numbers for list #2:

• 1-2-3-4

Normally, the next step would be to look at list #3; -but wait! Pieces #1 and #2 already INTERSECTING, as they share the same numbers. There is no sense going down this alley anymore! The program must find a set (in list #2) that does not have the numbers 1, 2 or 4 in it before even thinking about the other five lists.

So, the program continues to scan through list #2. It peeks at the next set and the next set after that... until it can find a set that does not use the numbers 1, 2 or 4 (which happens to be the eighth set, or 6-7-8-9).

For each abort, the program has saved itself from about 1005 combinations to sift through. Now that the program is happy with its selection (for Piece nos. 1 and 2), it scans through list #3 until it can find a set in that list that does NOT have 1, 2, 4, 6, 7, 8 or 9; as these numbers are already reserved.

After all the combinations have been exhausted for Piece #2, the program says, "Oh well, back to the ol' drawing board." Realizing the shame of defeat, it drops down to the next position for Piece #1, resets all the pointers of the remaining six lists, and proceeds to do the big grind again and again.

### Island Check

Look at the Soma structure below (1 = cube, 0 = no cube):

• 111111111
• 000000000 ... top layer
• 111111111
• 111111111 ... bottom layer

It sort of looks like a big, long sofa. Now, let's remove Piece #1 somewhere in the MIDDLE, so that the "sofa" looks like this:

• 111011111
• 000000000 ... top layer
• 111011111
• 111011111 ... bottom layer

Now it kind of looks like a pair of love seats. The structure is broken into two separate ISLANDS. One ISLAND has 9 little cubes, while the other has 15. Is it possible to build these two ISLANDS with the six remaining Soma pieces? NO!

The other Soma pieces are made out of 4 cubelets each, so an ISLAND must have either 4, 8, 12, 16, 20 or 24 little cubes. That's what this routine checks for - if a structure is split into two or more ISLANDS, then each ISLAND must have a multiple of 4 cubelets total.

### Parity Check

Let's look at the 3x3x3 big cube again. Suppose we color each little cube, either black or white, in a CHECKER-BOARD pattern. If we make the corners black, the 3x3x3 big cube would look like this: (B=black, W=white)

• BWB
• WBW
• BWB - bottom layer
• WBW
• BWB
• WBW - middle layer
• BWB
• WBW
• BWB - top layer

The PARITY of any Soma structure is equal to the Black Cubes minus the White Cubes. In this case, there are 14 black and 13 white. So the parity is (14 - 13) = +1.

Now I will go one step further, and look at the possible ways to checker-baord each of the 7 Soma pieces:

Piece #1: there are two ways to do this:

• B
• WB ... parity = (# Black - # White) = 2 - 1 = +1
• W
• BW ... parity = (# Black - # White) = 1 - 2 = -1

Therefore, Piece #1 can either have a parity of +1 or -1. (Does anyone know how to do the "therefore" symbol in HTML? You know, the one that looks like a tiny stack of cannonballs?)

Now let's look at the other pieces:
• Piece #2: parity = 0 (always)
• Piece #3: parity = +2 or -2
• Piece #4: parity = 0
• Piece #5: parity = 0
• Piece #6: parity = 0
• Piece # 7: parity = +2 or -2

As it turns out, ONLY pieces #1, 3 and 7 have a parity NOT equal to ZERO. Because of this, an entire Soma structure can only have a parity of:

Piece #1: +1 +1 +1 +1 -1 -1 -1 -1
Piece #3: +2 +2 -2 -2 +2 +2 -2 -2
Piece #7: +2 -2 +2 -2 +2 -2 +2 -2
Total
Parity:
+5 +1 +1 -3 +3 -1 -1 -5

So now we see that if a Soma structure has a PARITY of +1, -3 or +5; then Piece #1 must have a parity of +1 (with 2 black cubelets and 1 white cubelet). Otherwise, if a Soma structure has a PARITY of -1, +3 or -5; then Piece #1 must have a parity of -1 (with 1 black cubelet and 2 white cubelets). Piece #1 fits inside the big 3x3x3 cube 144 ways. The PARITY check eliminates half (72) of them!

### Order of Pieces

Remember how I said that are about 100 sets for each list? Well, I sort of kind of lied. But only a little! It seems that Piece #2 always has much more than 100, and that Piece #7 has much less. For the 3x3x3 BIG cube:

• Piece #1 fits 144 ways
• Piece #2 fits 144 ways
• Piece #3 fits 72 ways
• Piece #4 fits 72 ways
• Piece #5 fits 96 ways
• Piece #6 fits 96 ways
• Piece #7 fits 64 ways

The program has a tendency to BOMB OUT after trying to fit the first four pieces together. If it's going to bomb out so early in the game, why not place the the piece that has the least amount of recursion near the TOP of the list? Would it speed up the process? YES!

By changing the order from (Piece #) 1-2-3-4-5-6-7 to (Piece #) 1-7-3-4-5-6-2. By merely swapping Pieces no. 2 and 7, the program runs 3 times faster! Why? Because instead of going through 144 x144 x72 x72 iterations, it only has to go through 144 x64 x72 x72 instead, about 2/3 less.

Other tests show that by moving the EVIL TWINS (Pieces nos. 5 & 6) up in rank also quickens the pace, since they wreak so much havoc early in the process. This may be food for thought for a double-set solver.

Note: Piece #1 ALWAYS has to be the first selected, in order for the ISLAND and PARITY checks to work.

If this does not shine any light, don't blame yourself. I never could explain anything clearly. Einstein wrote a book called "The Theory of Relativity" that anyone should be able to understand. I doubt I could clearly teach someone how to play tic-tac-toe.