Torus Puzzle

The Torus Puzzle can be described as a variant of the Fifteen puzzle in which the empty space is replaced by a sixteenth tile. Moves consist of circular shifts of rows and columns and the goal is rearranging the titles so that all numbers appear in order when read from left to right and from top to bottom. The puzzle generalizes naturally to matrices of arbitrary sizes.

This page provides a playable version puzzle, where all generated instances are guaranteed to be solvable. A solution algorithm requiring $O(mn \log n)$ moves to sort a $m \times n$ matrix with $m \le n$ is also implemented. To see the algorithm in action, simply press the buttons labelled ①, ②, ③, and ④, in order. For a description of the algorithm, and the analysis of the required number of moves, see this paper.