Torus Puzzle (16-puzzle)

Description

The game consists of an $m \times n$ matrix containing all integers from $1$ to $mn$. A move consists of cyclically shifting a row left or right, or a column up or down ny one position.

The goal is to rearrange the scrambled integers into the sorted configuration, where the numbers are in increasing order reading from left to right, top to bottom (i.e., the element at row $i$ and column $j$ is $(i-1)n + j$).

The puzzle is also known as Sliders, TwoBik, RotSquare, Loopover, or Sixteen Puzzle.

Computational complexity

A configuration is sortable if and only if at least one of $m$, $n$, or the permutation of the elements is even [1] [2] [3], hence the problem of determining whether a given configuration can be sorted is in P.

The number of moves needed to solve a sortable instance is known as the push number and is upper bounded by $O(mn \cdot \log\max\{m, n\})$ [4].

The number of moves needed to solve a sortable instance when multiple consecutive rotations of the same row or column count as a single move is known as the drag number and is a lower bound to the push number. For any $m,n$ with $mn > 1$ there exists some $m \times n$ instance with a drag number of $\varepsilon mn$ [3], for some absolute positive constant $\varepsilon$. All sortable instances have a drag number of $O(mn)$ [3].

The variant in which the elements are colored with one of two colors and the goal is to determine whether a specific color pattern can be reached is NP-hard [3].

In a $n \times n$ instance, the number of random (unit) rotations needed to shuffle the position of one element is $O(n^3)$ [5]. It is known that $O(n^3 \log^3 n)$ rotations suffice to shuffle all elements [6] and it was conjectured that the such upper bound bound can be improved to $O(n^3 \log n)$ [5].

Notes

A playable version of the puzzle and an implementation of the sorting algorithm of [4] is available here.

References

[1] A. Bogomolny, “Cut the Knot! - Slider Puzzles”, Webpage, 1997.

[2] D. L. Greenwell, “Cut the Knot! - Sliders, puzzles on graphs”, Webpage, 1999.

[3] K. Amano, Y. Kojima, T. Kurabayashi, K. Kurihara, M. Nakamura, A. Omi, T. Tanaka, and K. Yamazaki, “How to solve the torus puzzle”, Algorithms, 2012.

[4] M. Caporrella, S. Leucci, “An Almost-Optimal Upper Bound on the Push Number of the Torus Puzzle”, arXiv preprint, 2026.

[5] P. Diaconis, “Group representations in probability and statistics”, 1998.

[6]: O. Blumberg, B. Morris, A. Senda, “Mixing time of the torus shuffle”, arXiv preprint, 2024.

@misc{cog:torus-puzzle,
    author = "{CoG contributors}",
    title  = "{Torus Puzzle (16-puzzle)}",
    year   = "2026",
    url    = "https://www.isnphard.com/i/torus-puzzle/",
    note   = "[Online; accessed 2026-01-15]"
}