(How Solve101 Works)

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.

Next, it takes Piece #1 (the one made out of 3 cubes), and moves and rotates it around inside the structure, and figures out *every possible way* that the piece can fit inside the structure. As it does this, it records the number assigned to each of those little cubes (that the Piece occupied) and makes a LIST:

- 1-2-4
- 1-2-5
- 1-4-5
- 2-4-5
- 2-3-5
- 2-3-6
- ...
- ...
- etc.
- etc.
- etc.
- ...
- ...
- 15-24-27
- 18-24-27

Then the program does the same thing for the OTHER Soma pieces (#2 thru #7); it creates a separate LIST for each piece. In the end we have seven lists:

Piece #1 | Piece #2 | Piece #3 | Piece #4 | Piece #5 | Piece #6 | Piece #7 |
---|---|---|---|---|---|---|

1-2-4 | 1-2-3-4 | 1-2-3-5 | 2-3-4-5 | 1-2-5-10 | 1-4-5-10 | 1-2-4-10 |

1-2-5 | 1-2-3-6 | 2-4-5-6 | 1-2-5-6 | 2-4-5-11 | 1-2-4-11 | 1-2-5-11 |

1-4-5 | 1-4-5-6 | 4-5-6-8 | 5-6-7-8 | 1-2-4-11 | 2-5-10-11 | 1-4-5-13 |

2-4-5 | 3-4-5-6 | 5-7-8-9 | 4-5-8-9 | 1-2-4-13 | 2-4-5-13 | 1-10-11-13 |

2-3-5 | 4-5-6-7 | 10-11-12-14 | 11-12-13-14 | 4-5-10-13 | 1-2-10-13 | 2-4-5-14 |

2-3-6 | 4-5-6-9 | 11-13-14-15 | 10-11-14-15 | 2-10-11-13 | 4-10-11-13 | 2-10-11-14 |

2-5-6 | 4-7-8-9 | etc. | etc. | ... | ... | ... |

3-5-6 | 6-7-8-9 | etc. | etc. | ... | ... | ... |

... | ... | ... | ... | ... | ... | ... |

... | ... | ... | ... | ... | ... | ... |

15-24-27 | 6-9-18-27 | 6-15-18-24 | 9-15-18-24 | 14-23-26-27 | 18-23-26-27 | 17-23-26-27 |

18-24-27 | 9-18-24-27 | 9-15-18-27 | 6-15-18-27 | 17-24-26-27 | 15-24-26-27 | 18-24-26-27 |

... each LIST has about 100 SETS of numbers. Now all the program has to do is pick a set from each list *where no two numbers match*! (get it?) If it CANNOT, then the structure is IMPOSSIBLE to solve with the seven Soma pieces (like the infamous W-WALL).

Each of the seven lists have about 100 sets. Multiply them all together, and you have 100^{7} combinations to check! Wow! Even the speediest computers can't handle that. So more algorithms were needed, ones that would eliminate the *obvious impossibilities...*

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 100^{5} 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.

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.

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?)*

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

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.

Solve101 Tutorial The Making of Solve 101 Solve101 Algorithms