|
|
Square 1 Puzzle | -- Fred Curtis |
[Puzzle Geometry] [What is an arrangement?] [How many arrangements are there?] [Grouping similar arrangements] [Canonical Shapes] [Program Sources] [Chronology] |
"Square 1" is a combinatorial puzzle (similar to "Rubik's Cube") which appeared around 1992. You can see some pictures of Square 1 on the following pages:
You can play with the Virtual Square 1 Puzzle on this site.
This page is a collection of notes on writing a computer program to solve the Square 1 puzzle.
Despite admitting some very strange-looking shapes, the Square 1 is essentially two outer layers -- each like a pie made of 60° and 30° segments -- separated by a middle layer of 2 large pieces. The outer layers can be rotated around the "pie" axis, and when the outer layers are lined up correctly the middle layer can be flipped, a move which transfers some pieces between the outer layers. For example:
3D View: | Flip -> | Rotate
top
90° (as viewed from above) -> | Flip | ||||
Symbolic View: |
How many of these arrangements are there? The most straightforward way to count them is to consider a "blank" version of the puzzle where all the labels/colours have been removed from the 60° and 30° pieces, list all the possible arrangements using these "blank" pieces, then for each "blank" arrangement count the number of ways it can be "coloured" by putting the labels/colours back.
Table 2 below shows all the ways that the blank pieces can be arranged in the top or bottom layer.
60°
pieces 'A' in layer | 30°
pieces 'a' in layer | ID | Layer shape | Reflection Symmetry | Rotation Symmetries | Permutation Multiplier | Permutation Sum |
---|---|---|---|---|---|---|---|
6 | 0 | 6-1 | AAAAAA | Y | 6 | 1/6 | 1/6 |
5 | 2 | 5-1 | AAAAAaa | Y | 1 | 1 | 3 |
5-2 | AAAAaAa | Y | 1 | 1 | |||
5-3 | AAAaAAa | Y | 1 | 1 | |||
4 | 4 | 4-1 | AAAAaaaa | Y | 1 | 1 | 35/4 = 8 3/4 |
4-2 | AAAaAaaa | N | 1 | 1 | |||
4-3 | AAAaaAaa | Y | 1 | 1 | |||
4-4 | AAAaaaAa | N | 1 | 1 | |||
4-5 | AAaAAaaa | Y | 1 | 1 | |||
4-6 | AAaAaAaa | N | 1 | 1 | |||
4-7 | AAaAaaAa | Y | 1 | 1 | |||
4-8 | AAaaAAaa | Y | 2 | 1/2 | |||
4-9 | AAaaAaAa | N | 1 | 1 | |||
4-10 | AaAaAaAa | Y | 4 | 1/4 | |||
3 | 6 | 3-1 | AAAaaaaaa | Y | 1 | 1 | 28/3 = 9 1/3 |
3-2 | AAaAaaaaa | N | 1 | 1 | |||
3-3 | AAaaAaaaa | N | 1 | 1 | |||
3-4 | AAaaaAaaa | Y | 1 | 1 | |||
3-5 | AAaaaaAaa | N | 1 | 1 | |||
3-6 | AAaaaaaAa | N | 1 | 1 | |||
3-7 | AaAaAaaaa | Y | 1 | 1 | |||
3-8 | AaAaaAaaa | N | 1 | 1 | |||
3-9 | AaAaaaAaa | N | 1 | 1 | |||
3-10 | AaaAaaAaa | Y | 3 | 1/3 | |||
2 | 8 | 2-1 | AAaaaaaaaa | Y | 1 | 1 | 9/2 = 4 1/2 |
2-2 | AaAaaaaaaa | Y | 1 | 1 | |||
2-3 | AaaAaaaaaa | Y | 1 | 1 | |||
2-4 | AaaaAaaaaa | Y | 1 | 1 | |||
2-5 | AaaaaAaaaa | Y | 2 | 1/2 |
No.
of
60°
pieces in top layer | No.
of
60°
pieces in bottom layer | Product
of permutation multipliers |
---|---|---|
6 | 2 | 1/6 * 9/2 = 3/4 |
5 | 3 | 3 * 28/3 = 28 |
4 | 4 | 35/4 * 35/4 = 1225/16 = 76 9/16 |
3 | 5 | 3 * 28/3 = 28 |
2 | 6 | 1/6 * 9/2 = 3/4 |
Total: | 2145/16 = 134 1/16 |
Each of the blank arrangements formed using the layers from Table 2 can be coloured in 8!·8! ways, but care has to be taken to avoid duplicates. For example, a blank shape with a layer 6-1 on top and layer 2-1 on the bottom can be coloured 8!·8! ways, but this must be divided by 6 to take into account the rotation symmetry of the top layer.
Each of the 2145/16 shapes (factoring out rotations - see Table 3) can be 'coloured' in 8!·8! = 1625702400 ways, and the middle pieces may or may not form a square (another factor of 2), so there is a total of 435891456000 arrangements (about 2^39). A web search on this number yielded one other calculation of the number of Square 1 states (by Michael C. Masonjones, dated 28 May 1996) which agrees!
To understand some ways of drastically reducing the number of arrangements to consider, it is convenient to have labels for the 60° and 30° pieces in the puzzle, and a description of what constitutes a solution for an arrangement:
Suppose we have an arrangement A and a solution S that returns A to the solved state.
Make a copy of A, but permute the pieces T0→T1→T2→T3→T0 and t0→t1→t2→t3→t0 and call the resulting copy A2. Make a copy of S, apply the same label permutation and call the resulting solution S2. Apply S2 to A2 and the result will be a solved puzzle with the top rotated by 90°.
That is (apart from a final rotation of the top layer), the same solution pattern suffices to solve both A and A2. Similarly if the permutation is applied again, and if a similar permutation is applied to the Bi/bi pieces.
Again, consider an arrangement A and a solution S which take A to the solved state. Make a copy of A but exchange each Ti<=>Bi and each ti<=>bi and call the copy A2. Apply the same permutation to S and call the result S2. Apply S2 to A2 and the result will be an arrangement with all the top pieces in the solved order (but location in the bottom layer) and all the bottom pieces in the solved order (but location in the top layer), or equivalently (by flipping the result upside down), the top and bottom layers in their correctly solved state but the middle layer of the puzzle inverted.
Make a copy of A2 but with the middle layer inverted and call this copy A3. Apply S2 to A3 and the result will be a solved puzzle (but inverted).
The same solution pattern S suffices to solve both A and A3. A3 is obtained from A by swapping the top and bottom layers and exchanging Ti<=>Bi and ti<=>bi (and then inverting the result, which doesn't change the relative positions of the pieces).
This grouping implies that if we consider arrangements with different Table 2 layer patterns (e.g. top layer 6-1 and bottom layer 2-2) then we can ignore arrangements with the layer patterns exchanged (e.g. top layer 2-2 and bottom layer 6-1).
For arrangements with the same layer patterns (i.e. top and bottom layers both 4-something) the grouping gathers arrangements such as [solved apart from swapping two top corners] and [solved apart from swapping two corresponding bottom corners].
Again, consider an arrangement A and a solution S which take A to the solved state. Make a copy of A reflected in a (vertical) mirror and call the copy A2. Apply S to A2. The result will be a puzzle with all the ti on the top layer (but ordered T0,t3,T3,t2,T2,t1,T1,t0 viewed clockwise from the top) and all the bi on the bottom layer (but ordered B0,b3,B3,b2,B2,b1,B1,b0 viewed clockwise from the bottom).
Make a copy of A2 but swap t0 <=> t3, T1 <=> T3, t1 <=> t2, b0 <=> b3, B1 <=> B3, b1 <=> b2. Call this copy A3. Make a copy of S applying the same permutation and call the result S2. Apply S2 to A3 and the result will be a solved puzzle.
The same solution pattern suffices to solve both A and A3. A3 is obtained from A by forming an image in a (vertical) mirror and swapping t0 <=> t3, T1 <=> T3, t1 <=> t2, b0 <=> b3, B1 <=> B3, b1 <=> b2.
This grouping implies that if we consider arrangements where at least one of the top or bottom layer pattern (see Table 2) lacks reflection symmetry (e.g., pattern 4-2 on top and 4-10 on bottom) then we can ignore arrangements with the mirror image patterns (e.g., pattern 4-4 on top and 4-10 on bottom).
For arrangements where both top and bottom layer patterns have reflection symmetry, the grouping gathers arrangements such as [solved apart from switching three top pieces clockwise] and [solved apart from switching corresponding pieces anticlockwise].
Shape ID | Top Layer | Top Rotsym | Bottom Layer | Bottom Rotsym | Sym2 | Sym3 | Sym4 | Symmetry Group Size | Unique
TtBb Templates |
---|---|---|---|---|---|---|---|---|---|
1 | AAAAAA | 6 | AAaaaaaaaa | 1 | N | Y | N | 32 | ? |
2 | AAAAAA | 6 | AaAaaaaaaa | 1 | N | Y | N | 32 | ? |
3 | AAAAAA | 6 | AaaAaaaaaa | 1 | N | Y | N | 32 | ? |
4 | AAAAAA | 6 | AaaaAaaaaa | 1 | N | Y | N | 32 | ? |
5 | AAAAAA | 6 | AaaaaAaaaa | 2 | N | Y | N | 32 | ? |
6 | AAAAAaa | 1 | AAAaaaaaa | 1 | N | Y | N | 32 | ? |
7 | AAAAAaa | 1 | AAaAaaaaa | 1 | N | N | N | 16 | ? |
8 | AAAAAaa | 1 | AAaaAaaaa | 1 | N | N | N | 16 | ? |
9 | AAAAAaa | 1 | AAaaaAaaa | 1 | N | Y | N | 32 | ? |
10 | AAAAAaa | 1 | AaAaAaaaa | 1 | N | Y | N | 32 | ? |
11 | AAAAAaa | 1 | AaAaaAaaa | 1 | N | N | N | 16 | ? |
12 | AAAAAaa | 1 | AaaAaaAaa | 3 | N | Y | N | 32 | ? |
13 | AAAAaAa | 1 | AAAaaaaaa | 1 | N | Y | N | 32 | ? |
14 | AAAAaAa | 1 | AAaAaaaaa | 1 | N | N | N | 16 | ? |
15 | AAAAaAa | 1 | AAaaAaaaa | 1 | N | N | N | 16 | ? |
16 | AAAAaAa | 1 | AAaaaAaaa | 1 | N | Y | N | 32 | ? |
17 | AAAAaAa | 1 | AaAaAaaaa | 1 | N | Y | N | 32 | ? |
18 | AAAAaAa | 1 | AaAaaAaaa | 1 | N | N | N | 16 | ? |
19 | AAAAaAa | 1 | AaaAaaAaa | 3 | N | Y | N | 32 | ? |
20 | AAAaAAa | 1 | AAAaaaaaa | 1 | N | Y | N | 32 | ? |
21 | AAAaAAa | 1 | AAaAaaaaa | 1 | N | N | N | 16 | ? |
22 | AAAaAAa | 1 | AAaaAaaaa | 1 | N | N | N | 16 | ? |
23 | AAAaAAa | 1 | AAaaaAaaa | 1 | N | Y | N | 32 | ? |
24 | AAAaAAa | 1 | AaAaAaaaa | 1 | N | Y | N | 32 | ? |
25 | AAAaAAa | 1 | AaAaaAaaa | 1 | N | N | N | 16 | ? |
26 | AAAaAAa | 1 | AaaAaaAaa | 3 | N | Y | N | 32 | ? |
27 | AAAAaaaa | 1 | AAAAaaaa | 1 | Y | Y | Y | 64 | ? |
28 | AAAAaaaa | 1 | AAAaAaaa | 1 | N | N | N | 16 | ? |
29 | AAAAaaaa | 1 | AAAaaAaa | 1 | N | Y | N | 32 | ? |
30 | AAAAaaaa | 1 | AAaAAaaa | 1 | N | Y | N | 32 | ? |
31 | AAAAaaaa | 1 | AAaAaAaa | 1 | N | N | N | 16 | ? |
32 | AAAAaaaa | 1 | AAaAaaAa | 1 | N | Y | N | 32 | ? |
33 | AAAAaaaa | 1 | AAaaAAaa | 2 | N | Y | N | 32 | ? |
34 | AAAAaaaa | 1 | AaAaAaAa | 4 | N | Y | N | 32 | ? |
35 | AAAaAaaa | 1 | AAAaAaaa | 1 | Y | N | N | 32 | ? |
36 | AAAaAaaa | 1 | AAAaaAaa | 1 | N | N | N | 16 | ? |
37 | AAAaAaaa | 1 | AAAaaaAa | 1 | N | N | Y | 32 | ? |
38 | AAAaAaaa | 1 | AAaAAaaa | 1 | N | N | N | 16 | ? |
39 | AAAaAaaa | 1 | AAaAaAaa | 1 | N | N | N | 16 | ? |
40 | AAAaAaaa | 1 | AAaAaaAa | 1 | N | N | N | 16 | ? |
41 | AAAaAaaa | 1 | AAaaAAaa | 2 | N | N | N | 16 | ? |
42 | AAAaAaaa | 1 | AAaaAaAa | 1 | N | N | N | 16 | ? |
43 | AAAaAaaa | 1 | AaAaAaAa | 4 | N | N | N | 16 | ? |
44 | AAAaaAaa | 1 | AAAaaAaa | 1 | Y | Y | Y | 64 | ? |
45 | AAAaaAaa | 1 | AAaAAaaa | 1 | N | Y | N | 32 | ? |
46 | AAAaaAaa | 1 | AAaAaAaa | 1 | N | N | N | 16 | ? |
47 | AAAaaAaa | 1 | AAaAaaAa | 1 | N | Y | N | 32 | ? |
48 | AAAaaAaa | 1 | AAaaAAaa | 2 | N | Y | N | 32 | ? |
49 | AAAaaAaa | 1 | AaAaAaAa | 4 | N | Y | N | 32 | ? |
50 | AAaAAaaa | 1 | AAaAAaaa | 1 | Y | Y | Y | 64 | ? |
51 | AAaAAaaa | 1 | AAaAaAaa | 1 | N | N | N | 16 | ? |
52 | AAaAAaaa | 1 | AAaAaaAa | 1 | N | Y | N | 32 | ? |
53 | AAaAAaaa | 1 | AAaaAAaa | 2 | N | Y | N | 32 | ? |
54 | AAaAAaaa | 1 | AaAaAaAa | 4 | N | Y | N | 32 | ? |
55 | AAaAaAaa | 1 | AAaAaAaa | 1 | Y | N | N | 32 | ? |
56 | AAaAaAaa | 1 | AAaAaaAa | 1 | N | N | N | 16 | ? |
57 | AAaAaAaa | 1 | AAaaAAaa | 2 | N | N | N | 16 | ? |
58 | AAaAaAaa | 1 | AAaaAaAa | 1 | N | N | Y | 32 | ? |
59 | AAaAaAaa | 1 | AaAaAaAa | 4 | N | N | N | 16 | ? |
60 | AAaAaaAa | 1 | AAaAaaAa | 1 | Y | Y | Y | 64 | ? |
61 | AAaAaaAa | 1 | AAaaAAaa | 2 | N | Y | N | 32 | ? |
62 | AAaAaaAa | 1 | AaAaAaAa | 4 | N | Y | N | 32 | ? |
63 | AAaaAAaa | 2 | AAaaAAaa | 2 | Y | Y | Y | 64 | ? |
64 | AAaaAAaa | 2 | AaAaAaAa | 4 | N | Y | N | 32 | ? |
65 | AaAaAaAa | 4 | AaAaAaAa | 4 | Y | Y | Y | 64 | ? |
Total of reciprocals of symmetry group sizes: | 2.65625 |
Selected CGI script sources for the Virtual Square 1 Puzzle on this site:
|
|
|