Title: Discrete configuration spaces of squares and hexagons,
Abstract: We consider generalizations of the familiar fifteen-piece sliding puzzle on
the 4 by 4 square grid. On larger grids with more pieces and more holes,
asymptotically how fast can we move the puzzle into the solved state? We also
give a variation with sliding hexagons. The square puzzles and the hexagon
puzzles are both discrete versions of configuration spaces of disks, which are
of interest in statistical mechanics and topological robotics. The
combinatorial theorems and proofs in this paper suggest followup questions in
both combinatorics and topology, and may turn out to be useful for proving
topological statements about configuration spaces.