S.K. Stein (Transversals of Latin Squares and their Generalizations, Pac. J. Math. 59(2), 1975) introduced the concept of an equi-$n$-square: a square matrix of size $n$ filled with the digits (colors) $0, .., n-1$ in equal amounts. The underlying formal $n$-square of positions (cells) is $\{ 0, 1, .., n-1 \}^2$ and the digit coloring is seen as a state. A horizontal move (H-move) of the square consists in rotating some rows cyclically by some integer amount. Different rows may be given a different rotation amount. Similarly, a vertical move (V-move) rotates some columns cyclically by some integer amount. Any composed move can be reduced to an alternating composition of H-moves and V-moves. An HV-shuffle applies an H-move followed by a V-move and a VH-shuffle applies a V-move followed by an H-move. In contrast with one-dimensional (simple-minded) shuffling --as with a deck of cards -- two-dimensional shuffling can effectively create randomness from order.
Cyclic rotations of rows and columns suggest a physical model of a formal $n$-square as a torus with longitudinal and latitudinal rotating rings. Hence an equi-$n$-square becomes an object with $n^2$ colored faces that may remind one of the Rubik's cube. In my paper "Shuffled equi-$n$-squares" available at
http://arxiv.org/abs/1701.02325
I proved three statements.
1. Every permutation of colored cells in an equi-$n$-square can be achieved by a composition of HV-shuffles. The same goes with VH-shuffles. Note that the corresponding result does not hold for Rubik's cube: if the cube's colors are implemented by removable colored stickers, one can easily produce a permuted state from which the original state cannot be recovered in a legal way.
2. Given $n \geq 2$ and an equi-$n$-square, there exists another equi-$n$-square which is no less than $d_n$ shuffles away, where $$d_n = \lceil\frac{\log_2(s_n)}{2 n \log_2(n)}\rceil.$$ ($s_n$ denotes the number of different equi-$n$-squares.) For $n < 30$ this gives $d_n = \lceil{n/2}\rceil$.
3. If $2 \leq n \leq 34$ or $n = 37$, one never needs more than $6 n \pm 3$ shuffles to transform one state into another one ("-" for $n$ even, "+" otherwise).
The restriction on $n$ is due to a combinatorial key result, which states that in an equi-$n$-square with restricted $n$,
any set of $n$ positions can be mapped with one VH-shuffle onto a set of positions looking like the graph of a function (having one position in each column).
This result combines topics explained in two questions that have been presented earlier on math.stackexchange: Optimal $n$-sets in a formal $n$-square: how many rows? and Determining a “spaghetti boundary” of formal $n$-squares. The shuffle starts with a vertical move optimizing an $n$-set $S$ and the subsequent H-move rotates the rows (rather, the parts of the optimized $S$ inside) apart. Given the restrictions on $n$, the second move is possible because some critical boundary on the number of rows is exceeded by the optimal set.
Question 1. Are the key result and its consequence 3 still valid outside the restriction on $n$?
An equi-$8$-square, which is close in size to a standard Rubik's cube, may need up to $45$ shuffles to restore a given state (result 3). This may run up to $16 * 45$ rotations of individual rings. In contrast, Rubik's cube can always be solved with at most $20$ "moves". The lower bound in result 2 is: $4$ shuffles. Hence sharpness of results 2 and 3 is an issue:
Question 2. Our proof of result 3 uses a part-by-part realization of the given transformation. At the end of each step, some unintentional mess must be cleaned up. This may suggest that the upper bound is prone to improvement. For a challenging proposal: can it be that the lower bound of result 2 is closest to reality, i.e.: is this a small world phenomenon?
