E-Mail.
|
|
SOMA News |
30 Nov 1999
E-Mail. |
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.
Addition 7. dec 1999
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../.....
|
|
/SOMA8aSymmetry
/...../1..11/.....
/..1../1111./..1..
/.111./.111./.111.
/..1../.1111/..1..
/...../11..1/.....
|
|
/SOMA16symmetry
/.1./.1./111/.1./.1.
/1.1/111/111/111/1.1
/.1./.1./111/.1./.1.
|
|
/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.