SOMA Crystal
SOMA News 18 Jan 1999

Courtney McFarren's solution program

Made by: Courtney McFarren
Date: 16. januar 1999
Re: Soma cube solution finder

Get the 4 small BASIC program's N990116.ZIP here.

The program described is being jointly developed further. Contact either Courtney or Me, If you want the newest information.
Courtney made the original finder program presented here, and in the Email correspondence between Courtney and me, the following description was made.

Question: "Should I present your programs on my SOMA page, for others to see.?"

Answer: I broke down and decided to give the free world my SOMA program, for these reasons:

1. I will never become a millionaire because I wrote this.
2. I've down-loaded freeware that was always helpful to me, and now it's MY TURN to return the favor.
3. Anyone who is interested in the SOMA cube deserves something like this.

Attached is THE PROGRAM. Well, actually, itís FOUR Q-Basic programs. You only need to run SOMA.BAS, which automatically runs S1234567.BAS, which runs ISLAND.BAS, which runs ANSWER.BAS and it finally ends.

If youíre familiar with Q-BASIC, then you should know how to edit a *.BAS program. The only program you have to edit is SOMA.BAS, and you HAVE TO EDIT it every time you want to solve a different structure. And the only thing you have to edit is the DATA deck. I couldíve made the program read a text file, but I just didnít want to get in the ins-and-outs of every 'INPUT#' error that could possibly happen at the time.

The SOMA.BAS file is set up to solve the 'NESSIE II' structure. I chose this because it is irregular and asymmetrical; a PERFECT candidate.

The first data deck entry (line 1000) is the lengths of the structure in the X, Y and Z axis. The Nessie2 is 11 cubes across, 4 cubes deep and 4 cubes high; so line 1000 should read:

1000 DATA 11, 4, 4

The next data decks depict what your structure looks like in layers. The bottom layer of 'Nessie2' looks like:


(where 1=cube, 0=space).

Therefore, the next data decks (for the first layer) are:

1001 DATA 1,0,0,0,0,0,0,0,0,0,0
1002 DATA 1,1,1,1,1,0,0,0,0,0,0
1003 DATA 0,0,0,0,1,1,1,1,0,0,0
1004 DATA 0,0,0,0,0,0,0,1,1,1,0

Data decks 1005,6,7 & 8 are for the second layer. Data decks 1009,10,11,12 are for the third layer. And finally:

1013 DATA 0,0,0,0,0,0,0,0,0,0,0
1014 DATA 0,0,0,0,0,0,0,0,0,0,0
1015 DATA 0,0,0,0,0,0,0,0,0,0,0
1016 DATA 0,0,0,0,0,0,0,0,0,1,1

- is the top layer, which is the 'head' of the Nessie2 structure.

RUN the SOMA.BAS program, and the screen will show you the solution a in very cryptic form.

I wonít explain more at this point. Change the data deck to solve another structure. Experiment with the program yourself and see if you can figure it out by yourself. But donít be shy to ask questions right away Iím here to help!

All 4 programs have to be in the SAME DIRECTORY as 'QBASIC.EXE' and all the QBASIC help file, etc. This was another simple fix I couldíve avoided, but was too lazy at the time. Also, about 10 ASCII files will be created when you run the program. Don't worry, they are small and harmless.

Another note... I just quickly modified my programs so that they could accommodate the Nessie2 structure (the original programs could only handle 10x10x10 structures). Not big deal to change, but just in case something goes awry, Iíll have to investigate.
By the way, It took my computer about 3 seconds to solve NESSIE2.

More on the SOMA program (DOS QBASIC)...

Like I said above, the program writes out the answer in a very cryptic form. Hereís how to decipher it.

Once again, weíll use the 'nessie2' structure as an example. Letís look at the data deck for the first layer
(1=cube, 0=space):

1001 DATA 1,0,0,0,0,0,0,0,0,0,0
1002 DATA 1,1,1,1,1,0,0,0,0,0,0
1003 DATA 0,0,0,0,1,1,1,1,0,0,0
1004 DATA 0,0,0,0,0,0,0,1,1,1,0

The SOMA.BAS program renumbers the cubes as:


...for the first layer, and assigns a number for every cube for the remaining layers, up to #27 (see the pattern?). When the program is done, it will list seven rows of numbers:
(On the DOS screen):


4  5  15  0
24  25  26  27
7  8  9  19
12  13  22  23
1  2  3  14
10  11  20  21
6  16  17  18

The first row is for piece #1; piece #1 uses cubes #4, 5 & 15 of the structure (ignore the zero). The second row is for piece #2, the third for piece #3, etc. , and the last (seventh) row is for piece #7.

I know itís painful to decipher by pencil and paper, but at the time I didnít care what the solution was; but only if one existed (or not) so I could compile my book of structures.

Hereís how the programs work:

First, it numbers each cube of the structure from 1 to 27 (SOMA.BAS)

Then, looks at piece #1 and figures out every possible way each it can fit in the structure, and compiles a list. The list seems to end up with about 100 entries, and each entry has 3 numbers (which are the numbers assigned to each cube of the structure (S1234567.BAS). For 'nessie2', The list would look like this:

1  2  3
1  2  14
2  3  14
2  3  15

The program does the same for the remaining 6 pieces, except that each entry has 4 numbers instead of 3 (since pieces #2 through 7 occupy 4 cubes)

Now there are 7 lists. All the program has to do now is pick an entry from each list where no two numbers match! (ANSWER.BAS)

The ISLAND.BAS program is an algorithm used to speed up the process. Without the algorithm, it would take my computer 30 minutes to solve a structure. With the algorithm, the average time is only 2 minutes, about 15 times faster!

Question: "It wont solve the W-WALL which is proven possible in SOMA-Addict. Is the position test exhaustive?"

Answer: I guess what you're REALLY asking is: "Is it possible for the program to overlook a solution?"
Well, the program is SOMEWHAT exhaustive, but it can NEVER overlook a possible solution.

On the average, there are about 100 entries (possible positions) for each of the 7 pieces per structure. For the program to test every one would take 100^7 combinations (10^14, or 100,000,000,000,000), which would take more than a lifetime.
So I had to make the program smart enough to know when to quit. For example:

I ran the W-WALL structure and looked at the 7 "position files" (s1.cub, s2.cub, etc...). The first entry for piece #1 (s1.cub) is 2-3-4. The program takes note of this, and then looks at the first entry for piece #2 (s2.cub) which happens to be 1-2-3-4. Right away, the program does not look at s3.cub, s4.cub, etc., because the first two pieces are already intersecting, and there's no use "going down that alley" anymore.
So it advances to the next entry in s2.cub.
Because of the abort, the computer saved itself 100^5 (10^10) unnecessary combinations to check.
The program's abort sensor is always on the alert.
When the last entry of s2.cub has been tried (and fails), the SECOND entry of s1.cub is tested, and all the "pointers" for s2.cub, s3.cub. etc, are reset to the FIRST entry again.

I thought this would be enough for the program to run quickly, but it still took about 1/2 hour for the program to come up with a solution (or at least an HOUR to realize that there WAS NO SOLUTION). Another algorithm was needed, so I devised ISLAND.BAS, and here's how it works:

Look at the structure below:

Now, let's remove piece #1 somewhere in the middle, so the remaining structure looks like this:


The structure is now broken up into two ISLANDS.
The first island contains 9 cubes, and the second island contains 15 cubes. Because the remaining six SOMA pieces have 4 cubes each, then each island HAS TO HAVE a multiple of 4 cubes in order to be solvable.
This is what the ISLAND program checks for; if a structure is broken into 2 (or more) sub-structures, then the remaining sub-structures HAVE to contain 4,8,12,16, 20 or 24 cubes.
Believe it or not, this algorithm speed up the process 2000%, even though it wastes a few milli-seconds each time while checking.

So yes; even though the program takes shortcuts, the POSITION TEST IS EXHAUSTIVE, once the obvious impossibilities are eliminated.

BACK to news index