forked from spencerparkin/SymmetryGroupPuzzle
-
Notifications
You must be signed in to change notification settings - Fork 0
/
SymmetryGroupPuzzle.html
153 lines (153 loc) · 11.3 KB
/
SymmetryGroupPuzzle.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>Symmetry Group Puzzle</title>
<link href="https://fonts.googleapis.com/css?family=Roboto" rel="stylesheet">
<script type="text/javascript" async src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.4/MathJax.js?config=TeX-MML-AM_CHTML" async></script>
<script src="https://code.jquery.com/jquery.js"></script>
<script src="Scripts/gl-matrix.js"></script>
<script src="Scripts/gl-helpers.js"></script>
<script src="SymmetryGroupPuzzle.js"></script>
<link rel="stylesheet" href="SymmetryGroupPuzzle.css">
</head>
<body>
<h1>Symmetry Group Puzzle</h1>
<div class="puzzle_menu" id="puzzle_menu">
</div>
<h3 id="puzzle_name"></h3>
<div id="waiter" class="waiter"></div>
<br>
<canvas id="canvas" onwheel="OnCanvasMouseWheel(event)"></canvas>
<br>
<input id="hover_highlights_check" type="checkbox" checked>Hover Highlights</input>
<input id="animation_check" type="checkbox" onclick="OnAnimationToggleClicked()">Animate</input>
<input id="initial_scramble_check" type="checkbox" checked>Initial Scramble</input>
<button type="button" onclick="OnScrambleButtonClicked()">Scramble!</button>
<button id="solve_button" type="button" onclick="OnSolveButtonClicked()">Solve!</button>
<button type="button" onclick="OnPrevImageButtonClicked()">Prev Image</button>
<button type="button" onclick="OnNextImageButtonClicked()">Next Image</button>
<br>
Animation Speed: <input type="range" min="0" max="100" value="50" step="1" id="animation_range" oninput="OnAnimationSliderMoved(this.value)">
<h2>Introduction</h2>
<p>
Welcome! This page features a kind of twisty puzzle based upon the symmetries of overlapping shapes.
Every shape of the plane has an associated group of symmetries (even if it's just the trivial group!)
A symmetry of a shape is simply any way you can remove it from the plane (leaving a hole in its place),
re-orient the shape in your hand, and then fit the shape back into the hole. If we overlap a bunch of shapes
in the plane, then we can get a larger group of transformations constructed from the individual symmetry groups
of each shape. Your job, given any element of this group, is to find a factorization of that element
in terms of the symmetries of the individual shapes (i.e., the generators of the group.)
</p>
<h2>Usage</h2>
<p>
The puzzle above is completely mouse driven. Hovering over the desired shape, use the mouse wheel to
rotate the shape clock-wise or counter-click-wise, if it has any rotational symmetry; or click on the
shape to reflect it across an axis near the location of the mouse cursor, if it has any reflective symmetry.
That's it! Notice that if you click on or hover over an area
of a shape that overlaps with some other shape, then which shape is manipulated is determined by which
shape has the least amount of area. If both shapes have the same amount of area, then the computer
chooses arbitrarily. This isn't a problem as long as there is always a way to unambiguously choose
the desired shape. Shapes that occupy disjoint regions of the plane present a bit of a problem with
this style of interface that I have yet to resolve.
</p>
<p>
The menu up top lets you choose the puzzle you want to play. A button below
lets you scramble the current puzzle. (Push it a few times to get a good scramble.)
Notice that animation and hover-highlights can be toggled.
The highlights are useful for discovering the generators of a puzzle.
The animation was a fun experiment, but I prefer it off if I'm giving the puzzle any serious effort.
Two buttons let you cycle forward or backward through the possible puzzle background images.
</p>
<h2>Group Theory</h2>
<p>
Group theory is a beautiful subject, and among so many other things, provides a model for explaining
twisty puzzles. In particular, when you're playing with a twisty puzzle, you're working within a
permutation group. (All groups are isomorphic to a group of permutations, but permutations themselves
provide the clearest model of what's going on physically with most twisty puzzles.) Specifically,
a twist of the puzzle permutes the faces, shapes or stickers of that puzzle. Multiple twists do the same,
and this provides us with the property of closure in groups. Every twisty puzzle has a solved state,
the identity of the group. And every configuration of the puzzle can be undone by some sequences of twists,
an inverse.
</p>
<p>
An interesting application of group theory to twisty puzzles is the notion of recognizing and then working
within a homomorphic image of the puzzle's associated permutation group. A classic example of this is
illustrated by the Rubik's Cube. If you've solved all cubie positions before solving their orientations,
then you've first worked in a homomorphic image (or factor group of the overall group), and then worked
in the kernel of that homomorphism. (Try to convince yourself that the set of all move sequences on the
Rubik's Cube that preserve cubie position, but not necessarily cubie orientation, forms a normal subgroup.)
</p>
<h2>Conjugates & Commutators</h2>
<p>
An interesting observation to make is that most of the useful move sequences found for solving a wide veriety
of twisty puzzles come in the form of conjugates and commutators. If \(A\) and \(B\) are any two move
sequences (any two permutations of our group \(G\)), then conjugates and commutators are of the form \(ABA^{-1}\) and \(ABA^{-1}B^{-1}\), respectively.
</p>
<p>
To see why these are so useful, I like to define the notation \(\overline{A}\) to mean the cardinality of the set
\(\{s\in S|A(s)\neq s\}\), where each permutation \(X\in G\) acts on the points in \(S\). (i.e.,
each \(X\in G\) is a bijective map from \(S\) to \(S\).) Let us
call \(\overline{A}\) the damage caused by \(A\). That said, it is not hard to show that conjugation
of \(A\) by some other permutation \(B\) does not increase or decrease the damage of that permutation.
In math symbols, \(\overline{A}=\overline{BAB^{-1}}\). So if the damage remains the same, what effect
does conjugation have? The answer is that it focuses the damage to the twisty puzzle somewhere else!
In other words, if we know how \(A\) damages (changes) a puzzle, then we can focus that change somewhere
else on the puzzle using \(B\), which is commonly referred to as a setup move.
</p>
<p>
It is also not hard to show that the damage of a commutator is less than the minimum damage caused by
either of the two permutations taken in the commutator product. In math symbols, we would write
\(\overline{ABA^{-1}B^{-1}}<\mbox{min}\{\overline{A},\overline{B}\}\). Commutators, therefore, provide
a way to narrow the damage to a puzzle caused by a move sequence, which becomes increasingly important near the end of
a solve. The trick is to find move sequences \(A\) and \(B\) that almost commute, but not quite.
</p>
<h2>Stabilizer Chains</h2>
<p>
One solution to the factorization problem in computational group theory is found in the use of a data-structure
known as a stabilizer chain. Pick any subset \(R\) of \(S\) and consider all \(X\in G\) such that for all \(s\in R\)
we have \(X(s)=s\). This subset of permutations forms a subgroup of \(G\); namely, the stabilizer in \(G\)
of \(R\). A stablizer chain is a sequence of nested subgroups, where each subgroup
stabilizes one more point than its immediately containing group, all the way down to the trivial group. Each of these subgroups
is represented in the computer by a set of generators, and stored along with that is a set of coset representatives
for each left (or right) coset of the subgroup in its immediately containing group. This data-structure is efficiently produced
by the Shreier-Sims algorithm, which is based upon Shreier's Lemma, and the Orbit-Stabilizer Theorem.
</p>
<p>
Now, if we have factorizations for all coset representatives in the entire chain in terms of the generators of
\(G\), then we can easily find a factorization for any \(X\in G\) by descending the chain. At each step,
it is easy to determine which coset we're in, and then use its representative to tack on more factors and get
ourselves into the next sub-group. Once we've reached the trivial group, we have our factorization.
</p>
<p>
This approach works, but it doesn't find optimal factorizations in terms of length, even if each coset representative
had an optimal factorization. A technique known as trembling can sometimes help one produce smaller factorizations
from a stabilizer chain. Also, finding factorizations for the coset representatives is a difficult task.
What I've done in the past is systematically and sometimes randomly generate elements of the group along with their
factorizations, and then try to drop them into the chain where they fit best as new or replacement representatives for cosets.
This process terminates when all representatives have been given factorizations, which can take a very long time.
</p>
<p>
If you've solved a Rubik's Cube, then you've surely used the stabilizer-chain concept, whether you realized it or not.
Whenever you've restricted yourself to a set of move sequences that alter the cube somehow, but preserve a certain
part of it, then you've been working in a stabilizer sub-group.
</p>
<h2>The Puzzle Engine</h2>
<p>
Implementing the above puzzle in Javascript was a challenge. I went through a few different designs before
landing on what I believe is the best solution. The puzzles are pre-built by a Python script that takes
as input the cut-shapes (generators) of the puzzle, and then outputs from that a set of pair-wise disjoint triangle meshes
that fill the canvas. These meshes are the moving parts of the puzzle, much like the cubies of a Rubik's Cube.
An analogy is that the Python script takes as input the cut-planes and then cuts the cube to output the needed cubies.
The client-side Javascript then needs only know how to move these pieces of the puzzle around. It does this
by, in addition to the said meshes, also receiving the original cut-shapes now turned capture-shapes. The capture shapes, when applied, capture all
meshes they cover, and then apply to those meshes a symmetry of the shape. Naturally, the puzzle is in the solved
state whenever all local-to-world transforms of the triangle meshes are identity. The implementation details can
be found <a href="https://github.com/spencerparkin/SymmetryGroupPuzzle" target="_blank">here</a>.
</p>
<h2>Feedback</h2>
<p>
Questions or comments? Please feel free to <a href="mailto:[email protected]?Subject=Symmetry Group Puzzle" target="_top">e-mail</a> me.
</p>
</body>
</html>