## 2 Preliminary
### Solution  
In this section, we show how to solve the torus puzzle by considering the two cases where \(mn\) is even and \(mn\) is odd. Not surprisingly, there is a difference between the even case and the odd case. In the even case, for _any_\(\mathbf{X}\in\mathscr{M}_{m,n}\), \(\mathbf{X}\) can be changed into the initial configuration \(\mathbf{A}\) by applying a sequence of the basic operations. But this is not true for the odd case. (A similar thing happened for the 15 puzzle [4].) To describe our solution of the torus puzzle, we need the following lemmas. **Lemma 1**. : _Suppose that \(n\geq 2\) is an even integer. For any two consecutive pieces \(x_{p,q-1}\) and \(x_{p,q}\) in a row of a configuration \(\mathbf{X}=(x_{i,j})\in\mathscr{M}_{m,n}\), we can swap the positions of two pieces without causing any other change of position by applying a sequence of basic operations. More precisely, it holds that \(\mathbf{X}\equiv\mathbf{Y}(=(y_{i,j}))\), where \(y_{p,q}=x_{p,q+1}\), \(y_{p,q+1}=x_{p,q}\), and \(y_{i,j}=x_{i,j}\) for \((i,j)\
ot\in\{(p,q+1),(p,q)\}\)._  
Proof. : Suppose \(n\geq 4\) (the case of \(n=2\) is trivial). It is sufficient to show that there is a sequence of basic operations which changes the first row \((x_{1,1},x_{1,2},x_{1,3},\ldots,x_{1,n})\) into \((x_{1,2},x_{1,1},x_{1,3},\ldots,x_{1,n})\). Apply \(T_{W}(1,2)\), \(T_{W}(1,4)\), \(T_{W}(1,6)\),..., \(T_{W}(1,n)\) in this order, then the first row becomes \((x_{1,1},x_{1,3},\ldots,x_{1,n},x_{1,2})\). Finally, execute \(E(\text{the 1 st row})\), then we have the desired result. The next lemma is inspired by an argument on the parity of permutations in [4]. **Lemma 2**. : _Suppose that \(mn\) is an odd integer. For any two consecutive pieces \(x_{p,q-1}\) and \(x_{p,q}\) in a row of a configuration \(\mathbf{X}=(x_{i,j})\in\mathscr{M}_{m,n}\), we cannot swap the positions of two pieces without causing any other change of position. More precisely, it holds that \(\mathbf{X}\
ot\equiv\mathbf{Y}(=(y_{i,j}))\), where \(y_{p,q}=x_{p,q+1}\), \(y_{p,q+1}=x_{p,q}\), and \(y_{i,j}=x_{i,j}\) for \((i,j)\
ot\in\{(p,q+1),(p,q)\}\)._  
Figure 3: Three elements rotation. Proof. : Suppose not, then there is a sequence \(\mathcal{S}\) of basic operations which swaps the positions. Let \(h\) (respectively, \(v\)) be the number of row (respectively, column) operations in \(\mathcal{S}\), Then, \(\mathcal{S}\) has \(h\) permutations of \(n\) elements and \(v\) permutations of \(m\) elements (_i.e._, \(h\) cycles of length \(n\) and \(v\) cycles of length \(m\)). As any permutation of \(k\geq 2\) elements can be represented by the production of \(k-1\) transpositions, \(\mathcal{S}\) can be represented with \(h\cdot(n-1)+v\cdot(m-1)\) transpositions. This, however, means that \(\mathcal{S}\) is even permutation, since both \(m-1\) and \(n-1\) are even. However, \(\mathcal{S}\) should be odd permutation, a contradiction. We are now ready to demonstrate our solution. Let \(\mathbf{A}=(a_{i,j})\) be the initial configuration. We first show how to obtain a configuration \(\mathbf{Y}=(y_{i,j})\) from any configuration \(\mathbf{X}=(x_{i,j})\in\mathscr{M}_{m,n}\) such that \(y_{i,j}=a_{i,j}\) for \(1\leq i\leq m-1\), \(1\leq j\leq n\), _i.e._, \(\mathbf{Y}\) achieves the initial configuration except for the bottom row. Suppose that the pieces numbered \(1\),..., \(r-1\) are already at their right positions. Let \(p\) and \(q\) be the integers such that \(p=\lceil r/n\rceil\) and \(r\equiv q\pmod{n}\). We now wish to have a configuration in which the pieces numbered \(1\),..., \(r\) are at their right positions. Let \((s,t)\) be the position of the piece numbered \(r\) in the current configuration. We will refer to the outside of the region placed the pieces numbered \(1\),..., \(r-1\) as _work space_. By proper choice of a third corner \((u,v)\) (from work space) and executing a proper triangle rotation on the three corners \((p,q)\), \((s,t)\), and \((u,v)\), we can have the desired configuration.