Discrete configuration spaces of squares and hexagons
This work addresses theoretical problems in combinatorics and topology, with potential applications in statistical mechanics and topological robotics, but it appears incremental as it builds on known puzzle generalizations.
The paper investigates the asymptotic speed of solving sliding puzzles on larger grids with more pieces and holes, including a hexagonal variant, by analyzing them as discrete versions of configuration spaces of disks. It presents combinatorial theorems and proofs that could aid in proving topological statements about configuration spaces.
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.