Solving Puzzles related to Permutation Groups

for finite permutation groups. The most well-known example of these
is Rubik's "Cube". Although the standard method of stabilizer chains
(Sims, 1970) in principle solves the problem, the sequences of moves
produced are far too large to be useful in practice. Even recent randomized
improvements of this basic method fail in this respect since they still rely
on Schreier's subgroup theorem.

In this talk, it will first be explained how puzzles can relate to permutation
groups and how this algebraic structure helps to find a way in a large graph
(#vertices = #states of the puzzle) in logarithmic time. Then the recent
methods found by us (Markus Pueschel and S.E.) are presented that actually
bring the length of the solution words down to practical size. Finally, there
will be a short guided tour through the zoo of puzzles that we have actually
solved with our implementation of the methods.

** If you have collected mechanical puzzles yourself where you suspect that
permutation group methods might be applicable, please bring them along! ***