 Hover Highlights

Animate

Animation Slaving

Initial Scramble

Move History:

## Introduction

This page features a kind of twisty puzzle based upon the symmetries of overlapping shapes. Every shape (subset) 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.)

## Usage

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 all there is to 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 can present a bit of a problem with this style of interface that I have yet to resolve.

Aside from the puzzle itself, a menu of puzzles and puzzle options are presented. Choose which puzzle you want to try from the puzzle menu. Most of the puzzle options become self evident with some experimentation. Notice that you can save and restore puzzle state for any of the puzzles. These states persist as long as you don't clear your browser cache.

## Group Theory

Group theory is a beautiful subject, and among so many other things, provides a model for twisty puzzles. In particular, when you're playing with a twisty puzzle, you're working within a permutation group. 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; 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.

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.)

## Conjugates & Commutators

An interesting observation to make is that most of the useful move sequences found for solving a wide variety 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.

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.

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. You might say that the damage of a commutator is a measure of how much $$A$$ and $$B$$ commute.

## Stabilizer Chains

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.

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.

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. Nevertheless, once you have the stabilizer chain fully worded, it's ready to be used to quickly solve any state of the associated puzzle.

## The Puzzle Engine

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, although I can conceive of a puzzle where, potentially, the picture may be restored and not all meshes have the identity transform, but for most puzzles, a solved picture must require all meshes have identity. In any case, the implementation details can be found here, if anyone cares.