Parity Property of Hexagonal Sliding Puzzles

Area of Science:

• Combinatorics
• Discrete Mathematics
• Computational Topology

Background:

• The 15 Puzzle, a square sliding puzzle, has known solvability criteria based on parity.
• Puzzle graphs model the solvability and complexity of sequential mechanical puzzles.
• Previous research on square puzzles provides a foundation for studying hexagonal variants.

Purpose of the Study:

• To investigate the puzzle graphs of hexagonal sliding puzzles.
• To determine solvability criteria for hexagonal puzzles with varying shapes and numbers of holes.
• To extend the understanding of puzzle graph properties beyond square configurations.

Main Methods:

• Analysis of puzzle graphs for hexagonal, triangular, and parallelogram-shaped boards.
• Investigation of parity properties specific to hexagonal tiling.
• Development of solvability criteria considering board geometry and hole placement.

Main Results:

• Hexagonal sliding puzzles exhibit more complex parity properties than square puzzles.
• Puzzles on large hexagonal, triangular, or parallelogram boards with three or more holes are generally solvable.
• A solvability criterion for puzzles with two or more holes involves parity and "tight corner" tile placement.

Conclusions:

• The shape of the board and the number of holes significantly influence hexagonal puzzle solvability.
• Understanding hexagonal puzzle graphs offers insights into the configuration spaces of mechanical puzzles.
• This research expands the combinatorial analysis of sliding puzzles to non-square domains.