Hamiltonicity of cylindrical 5-puzzle

2025

Read Hamiltonicity of cylindrical 5-puzzle (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-03926.txt.

Introduction

Taizo Sadahiro wrote this 2025 paper on a sliding tile puzzle played on a cylinder shaped board. The state graph of the puzzle links every layout to the ones reachable by one move. A Hamiltonian cycle in that graph visits each layout exactly once before returning to the start.

For the five tile puzzle on a two by three toroidal grid, the graph holds 720 layouts. Sadahiro gives an explicit cycle as a short string of 48 moves, repeated fifteen times, which readers can check by hand. A shorter 24 move string yields a cover that splices into a full path. The trick lifts cycles from a smaller quotient graph using symmetry.

Catalog record

YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE18 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-03926

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Hamiltonicity of cylindrical 5-puzzle Abstract In this short note, we construct an explicit Hamiltonian cycle in the state graph of the 5-puzzle on a cylindrical 2 × 3 2\times 3 grid, a graph with 720 720 vertices. The cycle is described by a short symbolic sequence of 48 48 moves over the alphabet { 𝙻 , 𝚁 , 𝚅 } \{{\mathtt{L}},{\mathtt{R}},{\mathtt{V}}\} , repeated 15 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. Taizo Sadahiro 1 Introduction The state graph of the classical sliding block puzzle—formed by placing mn-1 numbered tiles and one blank on a m\times n rectangular grid—has long been a natural object of study in combinatorics and algorithmic theory. For m=2 and n=3 , when the grid is modified to arrow the wraparound move (i.e., identifying opposite edges horizontally), we obtain a cylindrical 5 -puzzle, whose state graph becomes a cubic graph on 720 vertices representing all reachable configurations under legal moves. 1 1 1 A previous study of the classical (non-cylindrical) 5-puzzle appered in [ 1 ] , where different geometric structure was uncovered. In this note, we construct an explicit Hamiltonian cycle in this graph, encoded by a short symbolic sequence over the move alphabet \{{\mathtt{L}},{\mathtt{R}},{\mathtt{V}}\} , where {\mathtt{L}},{\mathtt{R}} , and {\mathtt{V}} denote left, right, and vertical shifts of the blank tile. Remarkably, a 48 -move word, repeated 15 times, traces a Hamiltonian cycle through all 720 configurations. We also identify a 24 -move word whose repetition yields a 2 -cycle cover, which can be spliced into a Hamiltonian path by simple edge replacements. As we show later, this symbolic sequence is so simple that one can memorise and verifiable without the help of computers. Our construction emerges from a general technique: we first reduce the state graph by symmetry to a smaller quotient graph , where backtracking search can efficiently find a Hamiltonian cycle. We then lift this cycle to the full state graph. This quotient–lifting method yields compressed symbolic encodings and appears to be effective in a variety of highly symmetric state graphs, suggesting the presence of a combinatorial “Hamiltonian grammar.” Although similar ideas may be implicitly used in related contexts, the author is not aware of previous work that formalizes this quotient-lifting approach in the context of Hamiltonian cycle construction. The question of whether a given highly symmetric graph admits a Hamiltonian cycle is a recurring theme in graph theory, exemplified by the Lovász conjecture on vertex-transitive graphs [ 2 ] . While our focus lies on Cayley graphs arising from a puzzle, these examples continue the exploration of Hamiltonicity in meaningful settings. 2 State graph as a Cayley graph Let \Gamma be a finite undirected simple graph with the vertex set V(\Gamma) of cardinality n+1 and the edge set E(\Gamma) . A position of the sliding block puzzle defined on \Gamma is a bijection f:V(\Gamma)\to\{1,2,\ldots,n,0\} . We say v\in V(\Gamma) is blank or unoccupied in a position f if f(v)=0 , and hence, the vertex f^{-1}(0) is blank. A position f is transformed into another position g by a move if there exist two mutually adjacent vertices v,w in \Gamma , such that, v or w is blank in f , and g=f\circ(v,w), where (v,w) denotes the transposition of v and w . Let {\rm puz}(\Gamma) be the graph whose vertex set consists of the positions of the puzzle. Two vertices (or positions) f and g of {\rm puz}(\Gamma) are connected by an edge \{f,g\} if and only if there is a move transforming f into g . In this note, we consider the sliding block puzzle defined on the 2 -by- 3 cylindrical grid graph \Gamma_{2,3} , which is defined as follows. The vertex set V(\Gamma_{2,3}) is {\mathbb{Z}}/2{\mathbb{Z}}\times{\mathbb{Z}}/3{\mathbb{Z}} , and there is exactly one edge connecting v and w\in{\mathbb{Z}}/2{\mathbb{Z}}\times{\mathbb{Z}}/3{\mathbb{Z}} , if and only if, v-w\in\left\{(1,0),\pm(0,1)\right\}\in{\mathbb{Z}}/2{\mathbb{Z}}\times{\mathbb{Z}}/3{\mathbb{Z}}. We call this sliding block puzzle, the cylindrical 5 -puzzle . Let f be a position in the cylindrical 5 -puzzle, which has blank at b=(x,y)\in{\mathbb{Z}}/2{\mathbb{Z}}\times{\mathbb{Z}}/3{\mathbb{Z}} . Then we obtain a permutation \sigma_{f}=f((0,1)+b)f((0,2)+b)f((1,0)+b)f((1,1)+b)f((1,2)+b)\in S_{5}, where S_{5} denotes the symmetric group of degree five, which we define to be the S_{5} - part of f . Since \Gamma_{2,3} is a non-bipartite graph, by applying the Wilson’s celebrated theorem on general sliding block puzzle [ 4 ] , we see that the state space is G=S_{5}\times{\mathbb{Z}}/2{\mathbb{Z}}\times{\mathbb{Z}}/3{\mathbb{Z}}. The \left({\mathbb{Z}}/2{\mathbb{Z}}\times{\mathbb{Z}}/3{\mathbb{Z}}\right) -part determines the blank position and S_{5} -part the relative configuration. Thus each position f can be uniquely encoded as an element (\sigma_{f},x_{f},y_{f})\in G . We sometimes identify f with its encoding (\sigma_{f},x_{f},y_{f})\in G . Let the right move be the move that exchange the blank vertex b with b+(0,1) . Then, by applying the right move to a position f , we obtain the position f^{\prime} whose S_{5} -part is \sigma_{f^{\prime}}=f((2,0)+b)f((1,0)+b)f((1,1)+b)f((1,2)+b)f((1,0)+b)=\sigma_{f}\mathtt{R}, where {\mathtt{R}}=(1,2)(3,4,5)\in S_{5} . Therefore we have f^{\prime}=f\,\hat{{\mathtt{R}}} where \hat{\mathtt{R}}=({\mathtt{R}},0,1) . Let the left move exchange the blank vertex b with b+(0,2) . Then, by applying the left move to a position f , we obtain a new position f^{\prime} whose S_{5} part is \sigma_{f^{\prime}}=f((2,0)+b)f((1,0)+b)f((1,2)+b)f((1,0)+b)f((1,1)+b)=\sigma_{f}{\mathtt{L}}, where {\mathtt{L}}=(1,2)(3,5,4)\in S_{5} . Thus we have f^{\prime}=f\,\hat{{\mathtt{L}}} , where \hat{{\mathtt{L}}}=({\mathtt{L}},0,2) . Let the vertical move be the move which exchange the blank vertex b with b+(1,0) . Then, we have \sigma_{f^{\prime}}=f((1,1)+b)f((1,2)+b)f((1,0)+b)f((0,1)+b)f((0,2)+b)=\sigma_{f}{\mathtt{V}}, where {\mathtt{V}}=(1,4)(2,5)\in S_{5} . Thus we have f^{\prime}=f\,\hat{{\mathtt{V}}} where \hat{\mathtt{V}}=({\mathtt{V}},1,0) . Thus the state graph {\rm puz}(\Gamma_{2,3}) of the cylindrical 5 -puzzle can be expressed as a Cayley graph {\rm puz}={\rm puz}(\Gamma_{2,3})={\rm Cay}(G,\{\hat{\mathtt{\mathtt{L}}},\hat{\mathtt{\mathtt{R}}},\hat{\mathtt{\mathtt{V}}}\}), where a Cayley graph {\rm Cay}(H,S) for a group H and its generating set S\subset H is defined as follows. The Cayley graph {\rm Cay}(H,S) is a directed graph whose vertex set is H and there is an edge from h_{1}\in H to h_{2}\in H if and only if there is some s\in S such that h_{1}s=h_{2} . 3 Hamiltonian path and cycle In this section, we show a Hamiltonian path and a Hamiltonian cycle in {\rm puz}(\Gamma_{2,3}) explicitly. To prove that the path we will construct is a Hamiltonian path, we first construct a Hamiltonian cycle in the Cayley graph {\rm Cay}(S_{5},\{{\mathtt{R}},{\mathtt{L}},{\mathtt{V}}\}) . Let H be a group. For a word w=(w_{1},w_{2},\ldots,w_{k})\in H^{k} , we denote its product by \phi_{H}(w) , that is, \phi_{H}(w_{1},w_{2},\ldots,w_{k})=w_{1}w_{2}\cdots w_{k}\in H. Lemma 1 . Let s=(s_{1},s_{2},\ldots,s_{12})\in\{\mathtt{L},\mathtt{R},\mathtt{V}\}^{12} be the sequence s=(\mathtt{V},\mathtt{L},\mathtt{V},\mathtt{R},\mathtt{V},\mathtt{L},\mathtt{V},\mathtt{R},\mathtt{V},\mathtt{R},\mathtt{V},\mathtt{L}), (1) and let s^{\prime}=(s_{13},s_{14},\ldots,s_{24}) be its perturbation defined by s_{12+i}=s_{i}\quad\mbox{for }i=1,2,\ldots,11,\qquad s_{24}=\mathtt{R}. (2) Define w as the five-fold repetition of (s_{1},s_{2},\ldots,s_{24}) , that is, w=(s_{1},\ldots,s_{24},s_{1},\ldots,s_{24},s_{1},\ldots,s_{24},s_{1},\ldots,s_{24},s_{1},\ldots,s_{24})\in S_{5}^{120}. (3) Then the sequence C=({\rm id},g_{1},g_{2},\ldots,g_{120})\in S_{5}^{121} is a Hamiltonian cycle in the Cayley graph {\rm Cay}(S_{5},\{{\mathtt{L}},{\mathtt{R}},{\mathtt{V}}\}) , where g_{i}=\phi_{S_{5}}(w_{1},w_{2},\ldots,w_{i}) . Proof. As a first step, we need to verify that the elements g_{i} are distinct for i=0,1,\ldots,24 . This can be done by checking one-by-one. (See Table 1 .) i w_{i} g_{i} \rho_{i} 1 \mathtt{V} 45312 12453 2 \mathtt{L} 54231 13524 3 \mathtt{V} 31254 12435 4 \mathtt{R} 13542

Read the complete text