## 1 Introduction  
In this paper, we address \(m\) by \(n\) torus puzzle which is similar to sliding puzzles such as the 15 puzzle. The \(m\times n\) torus puzzle consists of \(mn\) pieces numbered from 1 to \(mn\), and the pieces are placed on a _board_ of \(m\) rows by \(n\) columns. Initially, for each \(r\in\{1,\ldots,mn\}\), the piece numbered \(r\) is placed at the \(p\)th row and \(q\)th column, where \(p=\lceil r/n\rceil\) and \(r\equiv q\pmod{n}\). In the puzzle, there are four _basic operations_, \(N\), \(S\), \(E\), and \(W\) (these stand for north, south, east and west). The \(N\) (respectively, \(S\)) operation shifts the pieces in a column upward (respectively, downward). That is,by applying the \(N\) (respectively, \(S\)) operation to a column \(\mathbf{r}=(p_{1},p_{2},\ldots,p_{m-1},p_{m})^{tr}\), \(\mathbf{r}\) is changed into \((p_{2},p_{3},\ldots,p_{m},p_{1})^{tr}\) (respectively, \((p_{m},p_{1},\ldots,p_{m-2},p_{m-1})^{tr}\)), where \(\mathbf{A}^{tr}\) denotes the transpose of a matrix \(\mathbf{A}\). Similarly, the \(E\) (respectively, \(W\)) operation rotates a row \((p_{2},p_{3},\ldots,p_{n},p_{1})\) into \((p_{1},p_{2},\ldots,p_{n-1},p_{n})\) (respectively, \((p_{n},p_{1},\ldots,p_{n-2},p_{n-1})\)). After performing a sequence of the basic operations, the configuration of the board would differ considerably from the initial configuration. The objective of the torus puzzle is to restore the initial configuration from the scrambled configuration (see Figure 1).  
Although the 15 puzzle can be intuitively modified into the torus puzzle, the torus puzzle is relatively less popular. This is possibly because it is not easy to implement the torus puzzle on a board, unlike the 15 puzzle. However, the torus puzzle is now gaining popularity owing to the proliferation of touch-panel devices. In fact, the torus puzzle has already been implemented as an application called _RotSquare_ on Mac OS (and is now an iPhone app).  
The torus puzzle has not been investigated extensively thus far. In Section 4 in [1], the number of steps for randomizing the configurations of an \(n\) by \(n\) board is discussed. In [2], it is shown that an \(n\) by \(n\) board for every even number \(n\), any configuration can be obtained from the initial configuration by showing that any two adjacent pieces can be reversed without disturbing the positions of the others. In this paper, we study the complexity of solving the torus puzzle (and its variant). The remainder of this paper is organised as follows. Section 2 is devoted to a solution of the torus puzzle. After introducing some definitions and notations, we provide the basic tools for solving the torus puzzle, and then we show how the torus puzzle is solved with the basic tools. In Section 3, we discuss the upper and lower bounds on the number of \"steps\" for obtaining the initial configuration from a scrambled configuration, where successive identical operations applied to a row/column, such as \(E(\mathbf{r})\cdot\ldots\cdot E(\mathbf{r})\) for some row \(\mathbf{r}\), are counted as one step. This form of counting is intuitive when the torus puzzle is implemented on a touch-panel device. The lower bound can be obtained by a standard argument. In Section 4, we consider a variant of the torus puzzle in which the pieces are colored white or black. For the variant, we address the hardness in estimating the minimum number of steps for reaching a given _goal configuration_ from a given _start configuration_. Unfortunately, we have not determined the hardness for the torus puzzle thus far (it is known that finding the shortest solution for an \(N\times N\) extension of the 15 puzzle is NP-hard [3]).