An Almost-Optimal Upper Bound on the Push Number of the Torus Puzzle

arXiv:2601.08989v1 Announce Type: new
Abstract: We study the Torus Puzzle, a solitaire game in which the elements of an input $m times n$ matrix need to be rearranged into a target configuration via a sequence of unit rotations (i.e., circular shifts) of rows and/or columns. Amano et al. proposed a more permissive variant of the above puzzle, where each row and column rotation can shift the involved elements by any amount of positions. The number of rotations needed to solve the puzzle in the original and in the permissive variants of the puzzle are respectively known as the emph{push number} and the emph{drag number}, where the latter is always smaller than or equal to the former and admits an existential lower bound of $Omega(mn)$. While this lower bound is matched by an $O(mn)$ upper bound, the push number is not so well understood. Indeed, to the best of our knowledge, only an $O(mn cdot max{ m, n })$ upper bound is currently known. In this paper, we provide an algorithm that solves the Torus Puzzle using $O(mn cdot log max {m, n})$ unit rotations in a model that is more restricted than that of the original puzzle. This implies a corresponding upper bound on the push number and reduces the gap between the known upper and lower bounds from $Theta(max{m,n})$ to $Theta(log max{m, n})$.