An examination of the solvability of a sliding puzzle on a hexagonal grid.

Abstract

Puzzles in which pieces have to be moved to a specific place or configuration have existed for decades. From the 15-puzzle to the Rubik’s cube and more recently Rush Hour and similar mobile games, these puzzles provide great experiences, but also interesting research topics. Questions about solvability and optimal solutions have come up and some of those questions have been solved for those famous puzzles. This paper takes a look at some of these puzzles and the previous research on them, before describing a new sliding puzzle on a hexagonal grid where pieces connect two hexagons of the grid. This puzzle explores possibilities of a puzzle on a hexagonal grid, which is rare in puzzles. From a design perspective, whether the puzzle is solvable and how fast are logical questions. A proof is given to show that any configuration can be transformed into any other configuration on all but one hole-free 2-connected boards. Furthermore the proof shows that it is possible in polynomial number of moves. Other results are shown for other boards as well as different pieces.