Symmetry of Assemblies
The outside of the 6-piece burr has considerable symmetry. There
are 23 different ways to rotate and/or reflect the shape which end up
looking the same. To these 23 symmetries add the 'identity' symmetry,
which does not move the object at all, and the result is a
mathematical group of order 24.
When a 6-piece burr assembly is analyzed, one can ask whether the
internal cube arrangements have any symmetry. There are 11 possible
answers to this question, which are listed below. The syntax of the
symmetry designations should become clear.
Possible symmetries:
1 |
no symmetry of assembly |
2MA
| reflective symmetry through some plane |
2MB
| reflective symmetry through the center of the burr |
2R
| 180-degree rotational symmetry about some axis |
3R
| 3-way rotational symmetry which interchanges the axes |
4MA
| 4-fold symmetry including 2 reflective symmetries through
different planes and 1 180-degree rotational symmetry. |
4MB
| 4-fold symmetry including 1 reflective symmetry through
a plane, 1 180-degree rotational symmetry, and reflective
symmetry through the center. |
4R
| 180-degree rotational symmetry about all 3 axes |
6M
| 3-way rotational symmetry and reflective symmetry through
the center, giving 6 symmetries. |
8M
| reflective symmetry through each orthogonal plane,
resulting in 8 symmetries total, 4 of which are
reflective. |
24M
| all symmetries. This is possessed by only one assembly,
which is constructed from 6 piece #2's (JRM numbers).
This assembly has 8 internal cube voids in the center and
cannot be taken apart. |
For those interested in the mathematics, these symmetry types
represent all subgroups of the order-24 group of external symmetries
except the subgroup which would be designated as 12R. Using the
standard cubic-cut pieces, the only assembly with these symmetries is
the assembly which has symmetry type 24M.
Examples of assemblies with each of these symmetry types are in
the Appendix in Table 6.
Choice of Construction Method
There are two options for constructing all the 6-piece burr
assemblies with a computer program:
- Have the program determine all different sets of 6 physical
pieces (including duplicates), and for each of these determine all
possible assemblies that can be constructed from them. Then analyze
each of these assemblies to see if it is a solution, and how
interesting it is.
- Have the program construct the assemblies individually,
analyzing each one after it has been constructed.
The advantage to 1) is that the uniqueness of solutions will be
immediately known, as all other assemblies using the same pieces will
be done at the same time.
The advantage to 2) is that the program logic for constructing
assemblies will be executed essentially once, rather than being
re-executed for each new set of pieces.
Approach 2) was chosen because of the huge savings in computer
time for constructing the assemblies. This then required that all
"interesting" assemblies be reexamined to check for uniqueness.
The Basic Logic
The goal of the program logic is to do the following:
- Determine all possible ways in which the 32 cubes in the
interior of a 6-piece burr can be assigned to one of the 6 pieces, or
to empty space, so that all 6 pieces are connected pieces formed by
removing cubes from Figure 1.
- Rotations and/or reflections of the internal cube construction
should not be duplicated - that is, of the 24 possible rotations and
reflections, one should be recognized as the "first" one, which is
analyzed; and all the others should be recognized as not being the
"first", and so should be discarded.
- If some of the 24 rotations/reflections are the same as the
original, record this information so that assemblies can be counted by
symmetry type.
This section describes how the above requirements were carried
out. The logic was used for the NOTC and HB6 analysis programs. The
early general, holey programs, called GB6, which were used to analyze
1, 2, 3, 4 and 5-hole assemblies used a more complicated logic which
will not be described here.
The first task is to order the 2225 piece orientations. The
following operations can be applied to each piece orientation:
- Side-to-side reflection (SIDM)
- End-for-end rotation (FLIP)
- End-for-end reflection (EFEM)
These operations correspond to cube switchings as follows (numbers as
in Figure 1):
- SIDM: 1-5, 2-6, 3-7, 4-8, 9-11, 10-12.
- FLIP: 1-8, 2-7, 3-6, 4-5, 9-12, 10-11.
- EFEM: 1-4, 2-3, 5-8, 6-7, 9-10, 11-12.
When rotating or reflecting an assembly, each piece orientation
may change. The 3 permutations above, plus the original orientation,
are the only ways a piece orientation may be changed when an assembly
is rotated and/or reflected. Rotations about the long axis for
ambiguous pieces cannot occur during R&R of an assembly.
Each of the 2225 piece orientations is grouped with the 3 (or
fewer) piece orientations resulting from applying SIDM, FLIP, and
EFEM. The result is as follows:
- 534 groups of 4 piece orientations
- 42 groups of 2 piece orientations
- 5 groups of 1 piece orientation.
Each group is represented by the piece orientation of the group
which has the smallest MATR. MATR is computed with the following
formula:
MATR = 4096 - X(1) - 2*X(2) - 4*X(3) ... - 2048*X(12)
where X(i) = 1 if cube #i (Figure 1) is present, and
0 if cube #i is missing.
For example, the solid piece has piece orientation number:
MATR = 4096 - 1 - 2 - 4 - ... - 2048 = 1
and the piece which has 10 cubes cut out (number 3 in the JRM
notchable list) has two piece orientations with MATR values 1024 and
3328.
The sorting of the 2225 piece orientations is done as follows:
- The solid piece is placed first
- The groups of 4 are placed next, so that the group
representative has an order number of the form 2 + 4*N , and the
remaining members of the group have the next 3 positions in the order
SIDM, FLIP and EFEM. Those groups whose pieces have the fewest
removed cubes come first, and within groups where this number is the
same, the group containing the lowest MATR number comes first. The
sort numbers for these groups are from 2-2137.
- Next are placed the groups of 2 piece orientations each, with
the same rules as 2) for sorting these groups with each other. These
sort numbers are from 2138-2221.
- Finally, the remaining 4 piece orientations which are in
groups by themselves are placed in positions 2222-2225.
A listing of the 2225 piece orientations in this order is in
Table 3.
The 534 Cases
The vast majority of the assemblies can now be constructed in 534
different groups as follows:
- Let N be a number from 1 to 534.
- In piece position 1 from Figure 2
place the representative of
the Nth group of 4 piece orientations. The sort order for this piece
orientation will be 2 + 4*(N-1).
- Construct all assemblies in which the other 5 pieces are
occupied by piece orientations with numbers from 2 + 4*N to 2225.
This is easily done with a computer program with 5 nested loops, with
the loop indices taking all values from 2+4*N to 2225. Each time a
loop index is changed, the piece orientation specified by the loop
value is checked to see if it can fit with the pieces already placed.
If there is interference with another piece, the next value is tried
without executing the inner loops. The program places pieces in
Figure 2
in the order 1-3-5-2-4-6. This is so that as much interference as
possible occurs early on to save loop overhead.
It is easy to see that all assemblies constructed by this
procedure have no internal symmetry, and that no 2 such assemblies are
equivalent to each other by rotation and/or reflection. In addition,
the only assemblies which are not constructed by this method are those
in which either:
- One piece is solid
- None of the 6 piece orientations belongs to one of the 534
groups of 4, or
- Two or more of the 6 piece orientations belong to the same
group of 4, and the others belong to groups higher in the sort order.
Table 9
contains information on each of these cases and who ran
the program for this case.
The Remaining Cases
Eight more specialized programs were written and run to handle
the small number of assemblies not handled by the 534 cases. These
results are summarized as cases 535-542. The eight cases are listed
below:
- One solid piece. The solid piece (MATR = 1) is assigned to
piece #1 in Figure 2.
The other pieces may take on any of the other
piece orientations, but comparisons of pieces 3 & 4 and pieces 5 & 6
are made so two assemblies which are rotations or reflections of each
other are not both analyzed. Some assemblies have symmetry of order 2
or 4, and these are counted separately. No disassembly analysis is
run as all these assemblies have a partial solution of level-1. The
results are recorded as case #535.
- Two pieces are from the same group-of-4 and the other four
pieces have higher sort numbers. In addition, these two pieces are
not parallel in the assembly. This is handled as follows: For each N
from 1 to 534, piece #1 in Figure 2
is assigned number 2+4*(N-1) and
piece #3 is allowed to have all values from the group, that is
2+4*(N-1) through 5+4*(N-1). The other four pieces may take on any
values greater than 5+4*(N-1). The program is then also run with
piece #1 given value 4+4*(N-1). All the resulting assemblies are
different and have no symmetry. The results are stored as case #536.
- Two pieces are from the same group-of-4 and the other four
pieces have higher sort numbers. In addition, these two pieces are
parallel and have the same piece orientation number. The program
handles this by assigning 2+4*(N-1) to both piece #1 and piece #2.
About half of the assemblies are skipped, and a small number have
rotational symmetry about the long axis of pieces 1 and 2. The
results are stored as case #537.
- Same as 3), except that piece #2 is assigned number 3+4*(N-1),
or SIDM of piece #1. Some of the assemblies have reflective symmetry
through the plane between pieces 1 & 2. The results are stored as
case #538.
- Same as 3), except that piece #2 is assigned number 4+4*(N-1),
or FLIP of piece #1. Some of the assemblies have rotational symmetry
about a third axis. The results are stored as case #539.
- Same as 3), except that piece #2 is assigned number 5+4*(N-1),
or EFEM of piece #1. Some of the assemblies have reflective symmetry
about the center. The results are stored as case #540.
- Three or more pieces are from the same group-of-4 and the
other pieces (if any) have higher sort numbers. The program has
elaborate symmetry-checking code to eliminate assemblies which are R&R
equivalent to previously analyzed assemblies. The assemblies can have
a variety of symmetries which are recorded separately by the program.
The results are stored as case #541.
- No piece is from a group-of-4, and no piece is solid. All
pieces have sort orders 2138 or higher. This program also includes
elaborate symmetry checking and recording. The results are stored as
case #542.
Copyright 2000-2002 Bill Cutler Puzzles, Inc.