SOMA News 3 Dec 2000 E-Mail.

# The parity Proof. (Jotun's proof)

Many have asked me for help in proving figures, and I have often quoted "Jotuns Proof".

BUT Where is it !
And I must admit that it was rather much hidden, inside the operators manual for the SOLVE program.
Well, now I have cut it out of there, and present it as a separate newsletter, more easy to find.

Note: In some parts of the text, you will see reference to our SOLVE program.

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.

Written by Thorleif Bundgaard.

BACK to news index