## 2 Preliminary
### A Basic Tool: Three Elements Rotations  
In this section, we introduce a basic tool called _three elements rotation_, which plays a fundamental role in the solution.  
Consider the the following eight patterns of four consecutive operations. Figure 2 is used for showing how the eight patterns work. In Figure 2, there are five points: (the \(i\)th row, the \(j\)th column), (the \(i\pm\)\(p\)th row, the \(j\)th column), (the \(j\)th column), (the \(i\)th row, the \(j\)\(\pm\)\(q\)th column), and there are four triangles consistingof three of these points: \(A\), \(B\), \(C\), and \(D\). It is a routine to check that each pattern makes a clockwise or counterclockwise rotation of the three corners of a triangle \(A\), \(B\), \(C\), or \(D\) without other changes of piece positions.  
1. \(W^{q}(\mathbf{r}_{i})\), \(S^{p}(\mathbf{c}_{j})\), \(E^{q}(\mathbf{r}_{i})\), \(N^{p}(\mathbf{c}_{j})\)\(\rightarrow\) clockwise on \(A\),
2. \(S^{p}(\mathbf{c}_{j})\), \(W^{q}(\mathbf{r}_{i})\), \(N^{p}(\mathbf{c}_{j})\), \(E^{q}(\mathbf{r}_{i})\)\(\rightarrow\) counterclockwise on \(A\),
3. \(N^{p}(\mathbf{c}_{j})\), \(W^{q}(\mathbf{r}_{i})\), \(S^{p}(\mathbf{c}_{j})\), \(E^{q}(\mathbf{r}_{i})\)\(\rightarrow\) clockwise on \(B\),
4. \(W^{q}(\mathbf{r}_{i})\), \(N^{p}(\mathbf{c}_{j})\), \(E^{q}(\mathbf{r}_{i})\), \(S^{p}(\mathbf{c}_{j})\)\(\rightarrow\) counterclockwise on \(B\),
5. \(E^{q}(\mathbf{r}_{i})\), \(N^{p}(\mathbf{c}_{j})\), \(W^{q}(\mathbf{r}_{i})\), \(S^{p}(\mathbf{c}_{j})\)\(\rightarrow\) clockwise on \(C\),
6. \(N^{p}(\mathbf{c}_{j})\), \(E^{q}(\mathbf{r}_{i})\), \(S^{p}(\mathbf{c}_{j})\), \(W^{q}(\mathbf{r}_{i})\)\(\rightarrow\) counterclockwise on \(C\),
7. \(S^{p}(\mathbf{c}_{j})\), \(E^{q}(\mathbf{r}_{i})\), \(N^{p}(\mathbf{c}_{j})\), \(W^{q}(\mathbf{r}_{i})\)\(\rightarrow\) clockwise on \(D\),
8. \(E^{q}(\mathbf{r}_{i})\), \(S^{p}(\mathbf{c}_{j})\), \(W^{q}(\mathbf{r}_{i})\), \(N^{p}(\mathbf{c}_{j})\)\(\rightarrow\) counterclockwise on \(D\).  
These patterns are referred to as \"triangle rotations\".  
By combining two triangle rotations, a useful rotation can be built as follows. Let \(\mathbf{X}=(x_{i,j})\) be a configuration in \(\mathscr{M}_{m,n}\). Let \(\mathbf{Y}\) be the configuration obtained from \(\mathbf{X}\) by applying basic operations to the board in the following order: \(S(\mathbf{c}_{j})\), \(E^{q}(\mathbf{r}_{i})\), \(N(\mathbf{c}_{j})\), \(W^{q+p}(\mathbf{r}_{i})\), \(S(\mathbf{c}_{j})\), \(E^{p}(\mathbf{r}_{i})\), \(N(\mathbf{c}_{j})\) for \(p<j\) and \(q\leq n-j\) (see Figure 3).  
Figure 2: The eight rotations.  
It is easy to see that the only difference between \(\mathbf{X}\) and \(\mathbf{Y}\) is the \(i\)th row, and the \(i\)th row in \(\mathbf{Y}\) is:  
\[\underbrace{(x_{i,1},\ldots,x_{i,j-p-1})}_{\text{no change}},x_{i,j},\underbrace{ x_{i,j-p+1},\ldots,x_{i,j-1}}_{\text{no change}},x_{i,j+q},\underbrace{x_{i,j+1},\ldots,x_{i,j+q-1}}_{ \text{no change}},x_{i,j-p},\underbrace{x_{i,j+q+1},\ldots,x_{i,m}}_{\text{no change}}\]  
That is, only the part \((x_{i,j-p},x_{i,j},x_{i,j+q})\) of the \(i\)th row is changed (rotated) into \((x_{i,j},x_{i,j+q},x_{i,j-p})\). We will refer to this change as _three elements rotation_ on (\((i,j)\), \(p\), \(q\), west) (the east version can be defined similarly). Specially, we denote the three elements rotation on (\((i,j)\), \(1\), \(1\), west) by \(T_{W}(i,j)\) (the corresponding east version is denoted by \(T_{E}(i,j)\)). For example, \(T_{W}(i,1)\) results in \((x_{i,2},x_{i,n},x_{i,3},x_{i,4},\ldots,x_{i,n-2},x_{i,n-1},x_{i,1})\).