SOMA News 30 Nov 1999 E-Mail.

The 48 Symmetries of SOMA
by Bob Nungester.

Nungester, Bob bnungest@tycoelectronics.com
30. november 1999 20:55

I recently began analyzing symmetry in Soma figures in order to speed up performance of the Double Set Soma Solver program. I read Bob Allen's newsletter article with great interest, and recommend you read it first before continuing. The number and variety of symmetry classes in the article indicated it would be difficult to define every possible symmetry, especially since any given figure may start in an unusual rotation or placement in the model space.

Any transformation maps a set of points from an original figure, called the domain, into another figure called the range. Any symmetrical transformation must by definition retain distance, angle, shape and size attributes. The symmetries of Soma figures must meet an additional criteria that we can refer to as self-similarity. Self-similarity implies a symmetrical transformation exists where every element of the range is an element of the domain.
In other words, any Soma figure supporting a particular symmetrical transformation will look exactly the same after the transformation as it did before. There is nothing really new here, but these requirements make it possible to mathematically analyze Soma symmetries and calculate that there are exactly 48 elements in the symmetry group.

Understanding the rest of this article requires a little math. The main concept involved is the use of matrices to describe transformations. We're only going to deal with transformations of figures centered on the origin so we won't need to discuss translations. The Double Soma program actually checks symmetries by translating the figure so it's centered on the origin, performing one of the various symmetrical transformations and then translating the result back to the original position for comparison, but the transformation of the centered figure is the interesting part.

Any rotational or mirror transformation about the origin can be described by a 3x3 matrix. This matrix is applied to each X,Y,Z point in a Soma figure to give a new X',Y',Z' point. If you are not familiar with matrices or how to multiply a 1x3 matrix (X,Y,Z) by a 3x3 matrix, see http://learn.lboro.ac.uk/olmp/book.html and go to the "Matrices" section for a good explanation of matrix math.

The various properties noted above for all symmetries, and particularly self-similar symmetries, impose many constraints on the permissible values in the 3x3 symmetry matrices for Soma figures. I won't go into a detailed derivation, but a few thought experiments lead to the following conclusions regarding the values in the matrix:

1. The only permissible values are -1, 0 and 1.
2. Each row and each column of the matrix must have one and only one non-zero value.

With these two rules we can calculate all possible symmetries. The first row of the matrix can have any one of the three column entries be non-zero.
The second row can then have either of the two remaining column entries as non-zero. The third row then only has one possible non-zero entry. This gives six possible patterns of non-zero values. Since there are three non-zero entries in a matrix and each can be +1 or -1, there are eight combinations of +1 and -1 values possible in each of the six patterns.
Therefore, there are exactly 48 possible symmetries. The easiest way to visualize this is to just look at the 48 matrices, so they are listed below.
The numbers assigned to them are arbitrary, but some form of numbering is needed in order to reference each matrix in the following discussion.

``` 1       2       3       4       5       6       7       8

1 0 0   1 0 0   1 0 0   1 0 0  -1 0 0  -1 0 0  -1 0 0  -1 0 0
0 1 0   0 1 0   0-1 0   0-1 0   0 1 0   0 1 0   0-1 0   0-1 0
0 0 1   0 0-1   0 0 1   0 0-1   0 0 1   0 0-1   0 0 1   0 0-1

9       10      11      12      13      14      15      16

1 0 0   1 0 0   1 0 0   1 0 0  -1 0 0  -1 0 0  -1 0 0  -1 0 0
0 0 1   0 0-1   0 0 1   0 0-1   0 0 1   0 0-1   0 0 1   0 0-1
0 1 0   0 1 0   0-1 0   0-1 0   0 1 0   0 1 0   0-1 0   0-1 0

17      18      19      20      21      22      23      24

0 1 0   0 1 0   0-1 0   0-1 0   0 1 0   0 1 0   0-1 0   0-1 0
1 0 0   1 0 0   1 0 0   1 0 0  -1 0 0  -1 0 0  -1 0 0  -1 0 0
0 0 1   0 0-1   0 0 1   0 0-1   0 0 1   0 0-1   0 0 1   0 0-1

25      26      27      28      29      30      31      32

0 0 1   0 0-1   0 0 1   0 0-1   0 0 1   0 0-1   0 0 1   0 0-1
1 0 0   1 0 0   1 0 0   1 0 0  -1 0 0  -1 0 0  -1 0 0  -1 0 0
0 1 0   0 1 0   0-1 0   0-1 0   0 1 0   0 1 0   0-1 0   0-1 0

33      34      35      36      37      38      39      40

0 1 0   0 1 0   0-1 0   0-1 0   0 1 0   0 1 0   0-1 0   0-1 0
0 0 1   0 0-1   0 0 1   0 0-1   0 0 1   0 0-1   0 0 1   0 0-1
1 0 0   1 0 0   1 0 0   1 0 0  -1 0 0  -1 0 0  -1 0 0  -1 0 0

41      42      43      44      45      46      47      48

0 0 1   0 0-1   0 0 1   0 0-1   0 0 1   0 0-1   0 0 1   0 0-1
0 1 0   0 1 0   0-1 0   0-1 0   0 1 0   0 1 0   0-1 0   0-1 0
1 0 0   1 0 0   1 0 0   1 0 0  -1 0 0  -1 0 0  -1 0 0  -1 0 0
```

This set of matrices is known in group theory as a symmetry group with 48 elements. Let's look at a few of these matrices to see how they relate to each other. I'll refer to each transformation by the letter "T" followed by it's number.

T1 is the identity matrix, which simply means every point in the figure maps to itself 1-fold N symmetry (No Reflections or Rotations) in Bob Allen's article. T19 is a 90 degree counterclockwise rotation about the Z axis (X,Y,Z transforms to Y,-X,Z). T21 is a 90 degree clockwise rotation about Z (X,Y,Z goes to -Y,X,Z) and T7 is a 180 degree rotation about Z (X,Y,Z goes to -X,-Y,Z).

A general property of symmetry groups is the existence of cyclic groups of symmetries. Any symmetry applied to a figure multiple times must eventually return it to its original form (the identity matrix). In addition, any combination of symmetrical transformations must be an element of the symmetry group. This is the mathematical way of saying that a 90 degree counterclockwise rotation followed by another one is equivalent to another basic symmetry (180 degree rotation in this example).
Applying it a third time gives the same result as one 90 degree clockwise rotation, and a fourth application returns to the original figure (the identity matrix). In other words, applying T19 multiple times results in a cycle of four symmetries; T19, T7, T21, T1. This is known as a cyclic group of order 4, or a 4-fold symmetry.

Bob Allen's article addressed most of these symmetries, but now that we have a mathematical method of categorizing all the symmetries we can determine all the cyclic groups in the set. The list below shows the result when each symmetry is repetitively applied until it returns to the identity matrix.
The number of entries, N, on each line indicates the N-fold symmetry of each transformation:

```T1
T2, T1
T3, T1
T4, T1
T5, T1
T6, T1
T7, T1
T8, T1
T9, T1
T10, T4, T11, T1
T11, T4, T10, T1
T12, T1
T13, T1
T14, T4, T15, T1
T15, T4, T14, T1
T16, T1
T17, T1
T18, T1
T19, T7, T21, T1
T20, T7, T22, T1
T21, T7, 19, T1
T22, T7, T20, T1
T23, T1
T24, T1
T25, T33, T1
T26, T36, T8, T31, T37, T1
T27, T39, T8, T30, T34, T1
T28, T38, T1
T29, T38, T8, T28, T35, T1
T30, T39, T1
T31, T36, T1
T32, T33, T8, T25, T40, T1
T33, T25, T1
T34, T30, T8, T39, T27, T1
T35, T28, T8, T38, T29, T1
T36, T31, T1
T37, T31, T8, T36, T26, T1
T38, T28, T1
T39, T30, T1
T40, T25, T8, T33, T32, T1
T41, T1
T42, T6, T45, T1
T43, T1
T44, T6, T47, T1
T45, T6, T42, T1
T46, T1
T47, T6, T44, T1
T48, T1
```

Each of the figures in Bob Allen's article corresponds directly to one or more of these symmetries. For example T2, T3, and T5 are the three planar reflections, representing 2-fold A symmetry (Planar Reflection, No Rotations). T9, T12, T17, T23, T41, and T46 represent diagonal reflections, or 2-fold B symmetry (Diagonal Reflection, No Rotations). T25 and T33 are one example of rotation about a corner, or 3-fold T symmetry (No Reflections, Three Corner Rotations).

The most interesting cyclic groups are the previously unknown 6-fold symmetries. For example, T26 transforms X,Y,Z to Y,Z,-X. After applying this transformation six times it finally returns to the original figure. I haven't constructed a figure that demonstrates this symmetry group (other than the cube, of course), but a visually-interesting one should be possible with a double set.

The reason I pursued this derivation was to make it possible to test any Soma figure for symmetry in the computer program. The way this works is as follows:

When a solution attempt is started on a figure, it is first analyzed to see which of the 47 symmetries (other than T1) apply. A symmetry applies to the figure if the transform of each small cube in the figure is part of the original figure. The 47 symmetries can be generated in code (the same code used to create the list above) and then the program can loop through each of the symmetries.

The program solves figures by using an iterative subroutine that places a piece and then calls itself to place the next piece in order. It continues placing successive pieces until no further ones fit, in which case it backs up through the tree and moves the previous piece to the next place where it fits. In this way it cycles through the entire figure until a solution is found or until the first piece steps through the entire figure, indicating it's impossible.

Symmetry checking is incorporated by checking each placement of the first piece to see if a symmetrical placement has already been tried without success. If so, there is no need to try the new placement because it will simply lead to another symmetrical non-solution. This checking is done by keeping track of the location of each placement of the first piece that has been analyzed so far. For each new placement of this piece, the program uses each symmetrical transformation that applies to the figure and applies it to the new placement. If the transformed coordinates are in the list of placements that have already been tried, then this placement can be ignored.
Using this method allows any Soma figure with any orientation placed anywhere in the model space to be analyzed for all possible symmetries. I haven't written the code to implement this logic yet, but it's fairly straightforward and will be included in the next version of the Double Soma Solver program.

OK, I looked at the four-fold symmetries in the Mystery Mirror Matrices (14, 15, 20, 22, 44 and 47) and they each can be described by a 90 degree rotation about one of the three axes and then a reflection in the plane perpendicular to the same axis (such as Z rotation and Z reflection). I can construct 3 single-set figures and one double set figure that have these symmetries. There's almost certainly more double set figures, but the single set ones are probably the only ones there are except for obvious impossibilities.
The bad news is I couldn't find a single set figure that's possible to solve. The good news is that one of the single set figures is solvable with a double set as a partial figure, and the double set figure is solvable!

Here are three single set figures

"8 Symmetry"
 ``` /SOMA8symmetry /...../..22./..... /..7../6772./..3.. /.333./66722/.633. /..3../.1222/..3.. /...../.11../.....```

"8 symmetry" (solvable as a 2-set partial figure)
 ``` /SOMA8aSymmetry /...../1..11/..... /..1../1111./..1.. /.111./.111./.111. /..1../.1111/..1.. /...../11..1/.....```

"16symmetry"
 ``` /SOMA16symmetry /.1./.1./111/.1./.1. /1.1/111/111/111/1.1 /.1./.1./111/.1./.1.```

The last figure;
"16 Symmetry Double" is solvable with a double set.
 ``` /SOMA16aSymmetryDouble /...../...../...../22255/...../...../..... /...../..4../.445./24153/.117./..7../..... /..3../.333./.446./44.33/.677./.777./..7.. /...../..6../.166./21153/.665./..6../..... /...../...../...../22255/...../...../.....```

The figures with 16 symmetries have symmetries 1-8 and 17-24 (hmmm ... , even some symmetry in the symmetries). The same figures if reoriented along the X axis have 1-8 and 9-16. Along the Y axis 1-8 and 41-48. The ones with 8 symmetries have symmetries 1, 2, 7, 8 and 19-22 as drawn.

- submitted by Bob Nungester.

BACK to news index