SOMA Crystal
Bundgård & McFarren's SOMA-SOLVE 9 Aug. 1999
E-Mail.



The newest features.
How to operate the program.
__The Function keys.
The SOMA Figure files.
The text file format.
How the solver works.
How did we speed it extra up.
__More speeding up.
__Internal program link to Solve module.
Even more speeding.
Solving Partial figures.

The newest features.

Index.

SOLVE120 Now features:

Support for numeric notation 1,2,3,4,5,6,7 AND letter notation V,L,T,Z,A,B,P. Also a few % faster solving speed.

SOLVE110 Now features:

When starting, or loading a new file, you will be shown the file header at once, and asked for a figure number. If you dont know it, just press [Enter][F7] to get the first figure in the file.

You may now; select 30 or 45 deg viewing angle for the figure graphics. Use the [Up] and [Down] keys.

Rotation; is now done using the [Left] and [Right] keys, as an alternative to the [Home] and [End] keys.

NOTE; in the figure editor, rotation is only done with the [Home] and [End] keys, because [Left][Right] is used for the cursor.

The SOLVER will now allow the finding of more solutions to a figure. Just press [F2] several times.
! Version 1.1.0 will ALSO solve incomplete figures, using less than 7 pieces.!
And it still solves partial puzzles, although sometimes finding solutions by omitting a piece that you thought was needed.
Caution, IF you rotate your figure, be sure to have it back at the start position before doing the next solve, Failing this would have mixed the colors wildly.
Therefore: If you rotate the figure and press solve, it will restart the solve routine, but if you rotate AND bring it back to the same angle then solve will continue finding the next solution.

How to operate the program.

Index.

The program is operated using a single screen layout.

This is the entry area SOMA Solution Finder V1.10
Bundgård / McFarren 1999
   00000000000
   00000000000
   00000000000
   00000000022

   00000000000
   00000000000
   00000000000
   00000000020

   00000000000
   05166000000
   00004477000
   00000007320

   50000000000
   55116000000
   00006447000
   00000003330

SOMA002 in SOMA.HTM
Tilt: [Up] [Down]
Rotate: [Left] [Right]
1
New
Figure
2

Solve
3
Solved
Color
4
Solved
Text
5
Input
Figure
6
Batch
Solve
7
Next
Figure
8
Save
BMP
9
Save
Figure
10
New File
& Exit

The program screen is divided in 3 active areas.
Left side is for commands, data entry and presentation of alfa numeric information.
Right side is for showing the figure, with or without solution colors.
Bottom, is a list of 10 function keys, used for commanding the program.

Once the program is started, or when loading a new file, you will be shown the file header at once, and asked for a figure number.
Do this by pressing the function key [F1] and type in the figure number of your choise. If you dont know the number, just press [Enter][F7] to get the first figure in the file.
When the figure is loaded you may use the rest of the keys to View, Edit or solve the figure.

The Function Keys.

Index.
The available functions are:
[Left]
[Right]
Will rotate the figure 90 deg, at each keypress. The figure data will rotate as well, and solving a figure may give different solutions depending on the current view angle.
Note that you may still use the old rotation keys [Home] and [End] as an alternative.
[Up]
[Down]
Will now select a viewing angle of 30 or 45 deg thus allowing you to better visualize the figures.
[F1] New Figure: Will ask you to enter a figure name that appear in the file [015] for example. The figure will then be loaded and displayed.
[F2] Solve: Will compute your figure, attempting to find a SOMA solution. If one exist it will present it, and allow you to press [F3] to view it.
The SOLVER will now allow the finding of more solutions to a figure. Just press [F2] several times.
And it still solves partial puzzles, although sometimes finding solutions by omitting a piece that you thought was needed.
Caution, IF you rotate your figure, be sure to have it back at the start position before doing the next solve, Failing this would have mixed the colors wildly.
Therefore: If you rotate the figure and press solve, it will restart the solve routine, but if you rotate AND bring it back to the same angle then solve will continue finding the next solution.
[F3] Solved Color: Will toggle the figure between a computed color solution, and a presentation figure.
[F4] Solved Text: Will show the resulting figure in textual form, showing each layer of cubes, starting with the top layer.
[F5] Input Figure: Will allow you to edit a figure.
First you select to Erase figure: [Y]es / [N]o:
If you select Yes, you will have a completely erased array of 16 x 16 x 16 Soma cells.
If you select No, the current figure will be presented in the editing area.
You may now:
[PgUp][PgDn] These keys will move your cursor Up and Down in the editing cube.
The current level of editing is presented on a BAR on the left side.
[Esc] Stop editing and return to the menu.
[Up][Dn][Left][Right] Will move your cursor in the horizontal plane.
[Ins] Will toggle a figure cube ON and OFF at each pressure.
[Del] Clears a cell of cubes

During cube entry or deletion, a small counter will tell the number of cubes, present in the figure. The counter will be 'Red' if the figure is impossible, and 'Green' if it might have a solution.
The color is based on the fact that figures of certain cube counts are impossible, because the pieces have 3 or 4 cubes each.


[Home] and [End] are still active during editing, in order to rotate the figure. Note that the editing field also rotates AND that the figure is normalized when we rotate.
Observe that [Left][Right] DONT rotate because they are used to move the cursor.
If you by accident, rotated and had your figure so much left, that you cannot place some missing blocks at left side, then rotate twice, set a block way outside the figure at right, and rotate twice again.
The block will function as a limit for the normalizing and you may now edit your left side.
Remember to remove the space holder block, before you attempt to solve the figure.
[F6] Batch Solve: Will ask for a filename, and then run through ALL the figures in the file, solving each figure, and writing a solution file to the disk. The resulting filename will be .HTB, this is a text file that you may rename to .HTM to reload into the solver.
OBS: be carefull with your files, if you have many figures in the source file, then the Batch solver may take REALLY long time to finish. But of course you get your intended result so the waiting may be worth it.
[F7] Next Figure: Will load the next figure from the data file. To get other files, you must use the F1 New Figure function.
[F8] Save BMP: Will ask you for a filename, and will then write the Righthand area as a graphic image in .BMP format. Note that there is NO check, to see if a filename is in use.
select A to batch save all pictures from the current one and untill the end of file.
During Save, you may press [Esc] to Abort. But do note that the image being written at abort time, will be incomplete.
[F9] Save Figure: Will save the figure in TEXT format in either a new file, or appended to an existing file. The appended data will be at the end of the file, and you must then edit the file to position the figures at another sequence.
[F10] New File & Exit: Will ask you for a new filename containing more SOMA drawings, in text form. Or allow you to exit the program, by typing [Q][Enter]


The SOMA Figure files.

Index.

The filenames may be of any type, but our files will be named as TBtvvv.HTM
Assuming your name is T???? B????.

The extension is fixed to be .HTM (.HTB for batch output) because I use these same files, to present solutions on the figure pages of the SOMA Web site.
The HTML surroundings however is NOT used by SOLVE, and you may omit the HTML lines if you write your own text files.

't' Indicate the type of figures found in the file using one of the following letters.
'X' is for a file that hold a variation of figures.
'A' for standard types.
'D' for Double set figures.
'N' for figures that DONT use all 7 pieces.
'P' for figures producing pairs of shapes.
'vvv' is simply a sequence number 001, 026, 051 ...


The text file format.

Index.

The text files used by the ANSWER program, is formatted as pure text, with only a few restrictions:

A good practice is that the first lines of the text contain a description of the figures to be found in the file.
The first max. 20 text lines of max 50 characters will be displayed by the program, when the 'Get Figure' key is pressed,
If the text is a real HTML file format, containing the word <HTML> then all lines after <HTML> untill <!/SOMAHEAD> will be ignored.
Lines containing <!-- are also igored.

Each figure description starts with a line containing /SOMA immediately followed by an identification number like 001. Any descriptive text may follow this figure name.

The following lines MUST hold the figure data. (or explanation text) Each line starts with a '/' character, and the first line encountered WITHOUT this character marks the end of a description. (Space characters are allowed in front of the '/' character.)

Any line in the file are considered a comment UNLESS it comes after the '/SOMA' identifier
Each figure MUST be separated from the next by AT LEAST 1 blank or comment line.
Each Z part of a figure line MUST be preceeded by exactly one '/'

Each description line hold the figure data, with the top slice first, then the middle, and finally the bottom slice.
The two level serpent is described like this:

      /SOMAB031 This is an unseen comment
      ;This is the Serpent
      /*.***../*.***..
      /***.**./***.**.
      /.....*./.....*.
      /....***/....***
      /......./.....*.

These lines hold the figure data, and NO comments are allowed in these lines.
Except that upto 20 explanatory lines of max 50 characters per line. may be placed immediately after the figure name, and before its shape. Each line is preceeded by a ';'.
'/' characters are allowed in explanations.

Here is an example of a SOMA.HTM file.

<HTML><HEAD><TITLE>SOMA</TITLE></HEAD><BODY BgColor=White><pre>
<!/SOMAHEAD>

SOMAFIG.HTM SOMA data file
Contain figures: 078 and 079

/SOMA078 Nessie2 by Thorleif
/-........../-........../-........../5..........
/-----....../-----....../-5166....../55116......
/....----.../....----.../....4477.../....6447...
/.......--22/.......--2-/.......732-/.......333-


/SOMA079 The serpent by Thorleif
;This is a nice figure
/1.677../1.667..
/446.75./144.55.
/.....5./.....3.
/....222/....332
/.....#./.....3.

</pre></BODY></HTML>
Copy these lines to a text file named SOMAFIG.HTM
and you are ready to run SOLVE.


How the solver works.

Index.

The solver is based on FOUR original modules. SOMA, S1234567, ISLAND, and ANSWER.

This description here is set up to solve the 'NESSIE II' structure. I chose this because it is irregular and asymmetrical; a PERFECT candidate.

The data structure in the X, Y and Z axis for Nessie2 is 11 cubes across, 4 cubes deep and 4 cubes high:

The structure looks like layers. The bottom layer of 'Nessie2' looks like:

10000000000
11111000000
00001111000
00000001110

(where 1=cube, 0=space).

Therefore, the data deck (for the first layer) is:

     1,0,0,0,0,0,0,0,0,0,0
     1,1,1,1,1,0,0,0,0,0,0
     0,0,0,0,1,1,1,1,0,0,0
     0,0,0,0,0,0,0,1,1,1,0

Data deck for the third layer is:

     0,0,0,0,0,0,0,0,0,0,0
     0,0,0,0,0,0,0,0,0,0,0
     0,0,0,0,0,0,0,0,0,0,0
     0,0,0,0,0,0,0,0,0,1,1

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

If you were to run the 'SOLVER' alone the screen will show you the solution a in 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):

     1,0,0,0,0,0,0,0,0,0,0
     1,1,1,1,1,0,0,0,0,0,0
     0,0,0,0,1,1,1,1,0,0,0
     0,0,0,0,0,0,0,1,1,1,0

The SOLVER renumbers the cubes as:

     1,0,0,0,0,0,0,0,0,0,0
     2,3,4,5,6,0,0,0,0,0,0
     0,0,0,0,7,8,9,10,0,0,0
     0,0,0,0,0,0,0,11,12,13,0

...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:

SOLUTION EXISTS!

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 this is what the control section does for you.

Here's how the programs work:

First, it numbers each cube of the structure from 1 to 27.

Then, we look 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 (section S1234567). For 'nessie2', The list would look like this:

1  2  3
1  2  14
2  3  14
2  3  15
...etc.

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! (this is done in section ANSWER)

The ISLAND section 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 also an impossible structure 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". The first entry for piece #1 is 2-3-4. The program takes note of this, and then looks at the first entry for piece #2 which happens to be 1-2-3-4. Right away, the program does not look at pieces #3, #4, 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 for #2.
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 #2 has been tried (and fails), the SECOND entry of #1 is tested, and all the "pointers" for #2, #3. 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 the ISLAND section, and here's how it works:

Look at the structure below:
111111111/111111111
---------/111111111

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

111-11111/111-11111
---------/111-11111

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.


How did we speed it extra up.

Index.

The new algorithm for faster solving, we call "the Golomb algorithm", since Mr. Solomon Goloumb came up with this idea to prove impossible structures decades ago.

Initially the idea was rejected 6 years ago, thinking that the "Golomb" routine would take more time to CHECK than to eliminate impossibilities. Tests however show it in a different light.

PARITY

A 'parity checker' makes the solving time at least twice as fast.

What does parity mean?
Imagine coloring each cube in a structure, checkerboard-style. The parity is the number of black cubes minus the number of white cubes.

Also take a look at "JOTUN'S PROOF" (page 38 of the Parker Bros. Soma booklet).

Now look at each of the 7 pieces.
Pieces # 2, 4 ,5 & 6 all have "0" parity (all pieces have exactly 2 black cubes and 2 white cubes).
Piece # 1 can either have a parity of -1 or +1
Pieces # 3 & 7 can either have a parity of -2 or +2

A soma structure must have the following parities:
-5, -3, -1, +1, +3, +5
...otherwise, there is no solution.

WHAT ? You say that you color the pieces in checkerboard style, and then count How many white and how many black.!!
But how can you be sure that this actually will eliminate solutions ???
Is it not like imposing yet another constraint on the solutions, I mean, couldn't we risk having a figure that maybe will not work if the pieces were checkered, but which would solve when they are all black ???

Our way of looking at it is:
Imagine a large cube of 16 x 16 x 16 small cubes.


Parity

Each level is checkerboarded alternating. This large cube, although colored, is fully transparent. And into this large cube I now move my figures.
Clearly no cell will have a neighbour of the same color, and this is the case for ANY figure.


We find this method better, previously I tried to imagine the figure, and coloring the cubes, that also made me uncertain that they would fit, but the method above shows clearly that the figure assimilates the colors from the large 4096 cell cube.


Color depend on position

The current solve routine will handle figures, both as one unbroken structure as well as the funny 'Multi figures'. What happens if we place a 'Multi figure' in our array, and let it assimilate coloring from the array.

The coloring, and thus the parity, will depend on the position of the individual parts.


However, it is still possible, IN ALL CASES, to use parity, because only the figures having #1,#3,#7 will change parity as they are moved around. Giving +/-1, +/-2, +/-2 respectively, again a total of max 5. when being solvable.


All pieces with a color.

The parity table for the pieces 1, 3 and 7 look like this:

   #1:  +1 -1 +1 -1 +1 -1 +1 -1
   #3:  +2 +2 -2 -2 +2 +2 -2 -2
   #7:  +2 +2 +2 +2 -2 -2 -2 -2
   
   P:=  +5 +3 +1 -1 +1 -1 -3 -5

Parity +1, -3, +5 Then Piece 1 has Parity +1
Parity -1, +3, -5 Then Piece 1 has Parity -1
Parity +3, +5 Then Pieces 3 AND 7 have Parity +2
Parity -3, -5 Then Pieces 3 AND 7 have Parity -2
Parity +/-1 Then Pieces 3 AND 7 have Opposite Parity

This saves even more time.
The parity checking of piece #1 alone eliminates HALF of the possible positions piece #1 is allowed to have. Cutting the list for this piece is important, as it is the first piece examined in the program.
Every time a possible position of piece #1 is eliminated, a potential 1,000,000,000,000 combinations of the other piece positions are eliminated as well.

NOTE: That the #1 position list is still just as long as it used to be. The ANSWER module knows what entries to skip over.

In your Parker Bros. SOMA booklet on page 28. It shows piece #1 in 9 positions, but A, C, F, I have never been proved. Why?

Piece 1 positions ?

Let's set the 8 corners to black, the 3x3x3 cube now has a parity of +1.
In the 4 positions A, C, F, I piece #1 has 2 white cubes and one black cube, or a parity of -1, this is impossible! because piece #1 ALWAYS have the same parity sign as the figure itself.

WHY? you ask. - Well from the parity table above, there are only two positions giving a total parity of -1, and they have piece #1 at parity -1!


A few quick notes more about soma structure parity.

First of all, NO structure (Using one SOMA set of 7 pieces) have an even parity. (Double set figures however have even parity)

Proof:
Parity is the number of black cubes minus the number of white cubes. Let's say that a structure is assumed to have the EVEN parity of 2. Then:

B - W = 2

No matter what the parity is, the number of black cubes and white cubes added together is always 27 (of course):

B + W = 27

Now, add the two equations together:

B - W = 2 => W = B - 2
B + W = 27 => B + B - 2 = 27 => 2B = 29 => B=14.5

14.5 Black cubes. This doesn't make sense! we don't have half cubes.

If you try any other even-number for parity, you will always get a non-integer for the number of black or white squares.

MORE SPEEDING UP

Index.

We also tested the #3/#7 parity check, which we will call the "EXTRA-PARITY-CHECK" (the first parity check was for piece #1).

First of all, The pieces are not ordered in the simple order of 1-2-3-4-5-6-7, but instead we use 1-3-7-4-5-6-2 so that pieces #3 and #7 are near the top of the list. The only reason #2 is at the bottom was so we wouldn't have to rearrange pieces #4, #5 & #6.
Do remember that the numbers 1 - 7 were chosen by Piet Hein quite arbitrarily, and had nothing to do with piece parity.

At first we predicted that every piece was equally hard, but it turned out to improve speed 3 times, if we arranged the pieces after a degree of difficulty! And the TRULY AMAZING part was that the extra-parity-check was still OFF.

What we are saying is that the order of solving is very important.

This is stunning... if the extra-parity-check is off, why is the program then running so much faster? It don't seem logical that any piece is harder for the computer than any other piece. But if there are pieces that are "harder" in the computer mind, I guess they would be pieces #3 and #7!

After a lot of speed tests, Courtney selected the sequence (1-3-7-5-6-2-4) because it has the most consistent results: and it speeds up the program at least by 300%.

The reason for the sequence is.
Parity bits first 1-3-7.
5. do the last ODD numbered piece.
6. use this piece right after his twin brother.
2-4. At this point, it doesn't matter. But if we use #4 last, then the solving screen will show a nice symmetrical 1-2-3-BLANK-5-6-7 display.
It's not TOO random; we use all ODD pieces first, then all even pieces.

Another way of looking at it is: two flat pieces, three 3-D pieces, 2 flat pieces.
But the most important of all: Piece #1 is used first, then pieces #3 & #7. That's what really matters!

Courtney have done ALL of these tests with the EXTRA-PARITY-CHECK (EPC) subroutine ON and OFF.
Results: the timings were almost always the SAME; on one test the EPC sped up the process by 1 second, and on 2 tests it sped up the process by 2 seconds. It seems that the EPC is only useful for structures that are extremely convoluted (parities of +/-5) structures. But here's how it works:

After piece #1 is removed, the remaining structure has a parity of either 0 or +/-4.

After piece #3 is removed, then the remaining structure should have a parity of +/-2.

After piece #7 is removed, then the remaining structure should have a parity of 0, and will always remain 0 after any other piece is removed.

The EPC subroutine then tell the ANSWER program what entries to skip! Therefore, if piece #3 and piece #7 each had 100 possible positions, then the ANSWER routine would know which 50 entries of #3 and #7 to match-up before comparing.

Before, the computer had to go through 100x100 (10000) combinations of both lists. Now it only has to go through (50x50)+(50x50) = 5000 combinations. So why doesn't this algorithm double the speed?

Our guess is that if the wrong parities of pieces #3 and/or #7 are used, the remaining structure is left in such an awful mess, that the ISLAND sub-routine catches it long before the EPC does. As a matter of fact, it seems to always do. So no time is saved, except for a second or two. So the EPC test is NOT DONE.

INTERNAL PROGRAM LINK TO SOLVE MODULE

Only for programmers.!

Index.

The interfacing is done like this:
The user program operates data in an array Fld(X,Y,Z) using various variables for X,Y,Z.
When the Solve function is called upon, I call 'PreSolve' first and this will move the data as they are at this point from Fld(,,,) into A(,,,). The figure will always be normalized to be starting at 1,1,1 and the size moved from FigX,FigY,FigZ into the three variables X,Y,Z.
Then the 'FindSolve' is called (This is your solver program)
After solving, I call 'PostSolve' that will reformat the AA(,) and A(,,,) array data from the cell number system into the viewable Fld(,,,) array.
Then we return to the interface program.


Even more speeding.

Index.

How about symmetry.
A lot of the SOMA figures that exist, distinguish themselves by the fact that they carry a degree of symmetry. Now if we find the symmetry element, We have a way to cut our searches in halves for some figures. for example the bathtub.

/SOMA010
/*****/*****
/*...*/*****
/*****/*****

has X and Y symmetry, so when we have tested this


/*****/*****
/*...*/*****
/***11/****1

We dont have to test this

/*****/*****
/*...*/*****
/11***/1****

or this

/***11/****1
/*...*/*****
/*****/*****

or this

/11***/1****
/*...*/*****
/*****/*****

Cutting the test to 1/4
Well not quite, because ODD numbers of cubes on a mirror side will add the center cells.
The reduction in this case is not 3/4 because even though it is symmetric, it is also of an ODD number in both X and Y therefore giving us 10 of 27 cubes to test.

Again we limit our interest to piece #1, because it is the first and most exhaustive piece.

We find out if it has symmetry and eliminate possibilities, on the S1 data.

The figure description in SOMA is

  1  2  3  4  5
  6  7  8  9 10
 11 12 13 14 15

 16 17 18 19 20
 21  0  0  0 22
 23 24 25 26 27

And the piece 1 position data S1 is

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

Now sorting SOMA in the 4 symmetric groups we get

Group NW: 1  2  3  6  7  8 16 17 18 21
Group NE: 3  4  5  8  9 10 18 19 20 22
Group SW: 6  7  8 11 12 13 21 23 24 25
Group SE: 8  9 10 13 14 15 22 25 26 27

Then we eliminate all S1 elements that do NOT exist in the NW group.

This reduction gives 49 positions to test, and 43 eliminated tests.

S1 to be tested.
  1  2  6,  1  2  7,  1  6  7,  2  6  7,  2  3  7,  2  3  8
  2  7  8,  3  7  8,  3  4  8,  3  4  9,  3  8  9,  4  8  9
  6  7 11,  6  7 12,  6 11 12,  7 11 12,  7  8 12,  7  8 13,
  7 12 13,  8 12 13,  8  9 13,  8  9 14,  8 13 14, 16 17 21,
 21 23 24,  1  2 16,  1  2 17,  1 16 17,  2 16 17,  2  3 17,
  2  3 18,  2 17 18,  3 17 18,  3  4 18,  3  4 19,  3 18 19,
  6  7 21,  1  6 16,  1  6 21,  1 16 21,  6 16 21,  2  7 17,
  3  8 18,  6 11 21,  6 11 23,  6 21 23, 11 21 23,  7 12 24,
  8 13 25

S1 deleted.
  4  5  9,  4  5 10,  4  9 10,  5  9 10,  9 13 14,  9 10 14,
  9 10 15,  9 14 15, 10 14 15, 19 20 22, 22 26 27,  4 18 19,
  4  5 19,  4  5 20,  4 19 20,  5 19 20,  9 10 22, 11 12 23,
 11 12 24, 11 23 24, 12 23 24, 12 13 24, 12 13 25, 12 24 25,
 13 24 25, 13 14 25, 13 14 26, 13 25 26, 14 25 26, 14 15 26,
 14 15 27, 14 26 27, 15 26 27,  4  9 19,  5 10 20,  5 10 22,
  5 20 22, 10 20 22,  9 14 26, 10 15 22, 10 15 27, 10 22 27,
 15 22 27

Elimination do not check for mirror cases in the middle cells, It would give a slight extra benefit, but testing would not be worth it.

The method is that we inserte a preprocessing routine, just after the production of the S1 file. This routine scan through the S1 to eliminate symmetric items. Thereafter we continue the SOLVE program as usual. This way we dont include the eliminating function in the solve routine itself, (keeping solve fast) and we can concentrate on making an effective symmetry finder/eliminator.

We check for the following symmetries.
X Width symmetry
Y Depth symmetry
Diagonal symmetry when seen from the top. (Not yet)
Rotation symmetry when rotating 180 deg. (Not yet)


Solving Partial figures.

Index.

What then if my figure is NOT using ALL 7 pieces.?
SOLVE V1.0.0 seems to be working fine. We've tested & re-tested it, and so far so good. Not a single bug (yet). Version 1.0.0 will solve Partial figures too.

Technically speaking.
It seems that redefining XYZ (for the A-lattice) and FigXYZ (for the Symmetry routine) was the answer to our problem.
The MoveBack routine is copied at the beginning of FindSolve, and now the program behaves normally.

First of all, the program looks at how many cubes there are in the structure (F7) and divides that number by 4. The quotient (F4) reveals how many 4-cubed pieces there are. The remainder (F3) determines the following:

If F3 = ...
0, then piece #1 is not used.
1 or 2, there is no solution.
3, then piece #1 is used.

The program still treats the structure as if it had 27 cubes. For example, when it encounters a 16-piece structure, 11 phantom cubes, numbered from 17 to 27, are included in the S-array.
Rows of phantom cubes are inserted at the top of each column in the S-array, which is altered after the SArray module has already executed.

If piece #1 is used, then the #1 column (in the S-array) is untouched. If piece #1 is not used (as in the case of the 16-cubed structure), then the entire column is cleared, except for the first row, which will contain the first three phantom cubes available (27-26-25).

For pieces #2 thru 7, the number of phantom rows inserted depends on how many 4-cubed pieces are to be used. For example, a 16-piece structure has four 4-cubed pieces.
Two will not be used, so two phantom rows (24-23-22-21, 20-19-18-17) will be inserted in columns 2 thru 7 of the S-array.

The parity theory does not work for partial structures, so the parity check is deactivated. It is only activated for 7-piece structures.

The Island routine will not work properly while testing a phantom piece.
Phantom cubes do not have an X-Y-Z coordinate attached to them, and the Island routine heavily depends on coordinates.
Therefore, the Island routine is used only when testing real (non-phantom) pieces.
The Island routine is always ON for 7-piece structures, of course.

OTHER CHANGES:

CMcF edited the 1st three modules in structured-BASIC format.
The 4th module (Answer) has too many GOTO conditions that bounce around in a haphazard manner. S1234567 and Island are new and improved now.
For now, it is better to leave Answer alone.
It is possible to re-write a FEW lines in structured format, but why hybrid the module at this stage?

This has also been done
Added the MoveBack routine at the beginning of FindSolve to remind the program what the values of X-Y-Z and FldX-Y-Z are.

Cleared G(), E0(), and other arrays before solving any structure.

Slightly changed the output screen (Solution Exists!) so that the program will only list the "real" pieces used to solve a partial structure, and omitting the phantom pieces.


BACK to SOLVE index