A quotient-lifting approach to the Hamiltonicity of the cylindrical 5-puzzle graph
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915616169918464 |
|---|---|
| author | Sadahiro, Taizo |
| author_facet | Sadahiro, Taizo |
| contents | We construct an explicit Hamiltonian cycle in the state graph of the 5-puzzle on a toroidal 2x 3 grid, a graph with 720 vertices. The cycle is described by a short symbolic sequence of 48 moves over the alphabet {L,R,V}, repeated $15$ times, which can be verified directly. We also find a shorter 24-move sequence whose repetition yields a 2-cycle cover, which can be spliced into a Hamiltonian path. These constructions arise naturally from a general method: lifting Hamiltonian cycles from a quotient graph under the action of the puzzle's symmetry group.
The method produces compact, human-readable cycle encodings and appears effective in broader settings, suggesting a combinatorial grammar underlying Hamiltonian paths in symmetric configuration spaces. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_03926 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A quotient-lifting approach to the Hamiltonicity of the cylindrical 5-puzzle graph Sadahiro, Taizo Combinatorics We construct an explicit Hamiltonian cycle in the state graph of the 5-puzzle on a toroidal 2x 3 grid, a graph with 720 vertices. The cycle is described by a short symbolic sequence of 48 moves over the alphabet {L,R,V}, repeated $15$ times, which can be verified directly. We also find a shorter 24-move sequence whose repetition yields a 2-cycle cover, which can be spliced into a Hamiltonian path. These constructions arise naturally from a general method: lifting Hamiltonian cycles from a quotient graph under the action of the puzzle's symmetry group. The method produces compact, human-readable cycle encodings and appears effective in broader settings, suggesting a combinatorial grammar underlying Hamiltonian paths in symmetric configuration spaces. |
| title | A quotient-lifting approach to the Hamiltonicity of the cylindrical 5-puzzle graph |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2507.03926 |