Rubik-sorting a matrix (a.k.a. the torus puzzle)

Question

The idea for this code-challenge is simple: given a matrix of integers, let's sort it by applying Rubik-style movements. This means that you can select a single row or column and rotate its elements in any direction:

[1, 3, 2, 4]  => [3, 2, 4, 1] (rotate left for rows/up for columns)
[1, 3, 2, 4]  => [4, 1, 3, 2] (rotate right for rows/down for columns)

So, given a matrix of integers of any dimension, sort its elements applying only these Rubik-style transformations. A matrix

$$ \begin{bmatrix} a_{11} & a_{12} & a_{13} & a_{14} \\ a_{21} & a_{22} & a_{23} & a_{24} \\ a_{31} & a_{32} & a_{33} & a_{34} \end{bmatrix} $$

will be considered sorted iff its elements comply with the following restriction:

$$ a_{11} \leq a_{12} \leq a_{13} \leq a_{14} \leq a_{21} \leq a_{22} \leq a_{23} \leq a_{24} \leq a_{31} \leq a_{32} \leq a_{33} \leq a_{34} $$

I/O

• Input will be a matrix of positive integers with no repeated values.
• Output will be the movements needed to sort it. As this is not a code golf challenge and you don't need to worry about its length, the proposed format for every movement is #[UDLR] where # is the number of the row or column to move (0-indexed) and [UDLR] is a single character in that range that specifies if the movement is Up/Down (for columns) or Left/Right (for rows). So 1U would mean "move the 1-th column upwards" but 1R would be "move the 1-th row rightwards". Movements will be comma-separated, so a solution will be expressed like this: 1R,1U,0L,2D.

Scoring

Trying to sort a matrix this way can be costly as there are a lot of possible combinations of moves, and there are also a lot of possible lists of moves that can sort it, so the goal is to write some code that sorts the N*N matrices below. The score will be the greatest size N that you can solve in a reasonable amount of time¹ without errors (the greater the size of the matrix solved, the better). In case of a tie, the tie-breaker will be the number of movements in your found path (the shorter the path, the better).

Example: if a user A finds a solution for N=5 and B finds a solution for N=6, B wins regardless of the length of both paths. If they both find solutions for N=6 but the solution found by A has 50 steps and B's solution has 60 steps, A wins.

Explanations on how your code works are highly encouraged and please post the solutions found so we can test them. You can use Pastebin or similar tools if the solutions are too big. Also, an estimation of the time spent by your code to find your solutions will be appreciated.

Test cases

The following matrices (Pastebin link for a more copy-pasteable version) have been created starting from already sorted matrices by scrambling them with 10K random, Rubik-style movements:

_{^{\begin{bmatrix} 8 & 5 & 6 \\ 11 & 10 & 1 \\ 3 & 15 & 13 \\ \end{bmatrix} \begin{bmatrix} 21 & 10 & 12 & 16 \\ 17 & 6 & 22 & 14 \\ 8 & 5 & 19 & 26 \\ 13 & 24 & 3 & 1 \\ \end{bmatrix} \begin{bmatrix} 1 & 13 & 8 & 16 & 5 \\ 9 & 40 & 21 & 26 & 22 \\ 11 & 24 & 14 & 39 & 28 \\ 32 & 19 & 37 & 3 & 10 \\ 30 & 17 & 36 & 7 & 34 \\ \end{bmatrix} \begin{bmatrix} 34 & 21 & 40 & 22 & 35 & 41 \\ 18 & 33 & 31 & 30 & 12 & 43 \\ 19 & 11 & 39 & 24 & 28 & 23 \\ 44 & 1 & 36 & 5 & 38 & 45 \\ 14 & 17 & 9 & 16 & 13 & 26 \\ 8 & 3 & 47 & 6 & 25 & 4 \\ \end{bmatrix} \begin{bmatrix} 20 & 36 & 17 & 1 & 15 & 50 & 18 \\ 72 & 67 & 34 & 10 & 32 & 3 & 55 \\ 42 & 43 & 9 & 6 & 30 & 61 & 39 \\ 28 & 41 & 54 & 27 & 23 & 5 & 70 \\ 48 & 13 & 25 & 12 & 46 & 58 & 63 \\ 52 & 37 & 8 & 45 & 33 & 14 & 68 \\ 59 & 65 & 56 & 73 & 60 & 64 & 22 \\ \end{bmatrix} \begin{bmatrix} 85 & 56 & 52 & 75 & 89 & 44 & 41 & 68 \\ 27 & 15 & 87 & 91 & 32 & 37 & 39 & 73 \\ 6 & 7 & 64 & 19 & 99 & 78 & 46 & 16 \\ 42 & 21 & 63 & 100 & 4 & 1 & 72 & 13 \\ 11 & 97 & 30 & 93 & 28 & 40 & 3 & 36 \\ 50 & 70 & 25 & 80 & 58 & 9 & 60 & 84 \\ 54 & 96 & 17 & 29 & 43 & 34 & 23 & 35 \\ 77 & 61 & 82 & 48 & 2 & 94 & 38 & 66 \\ \end{bmatrix} \begin{bmatrix} 56 & 79 & 90 & 61 & 71 & 122 & 110 & 31 & 55 \\ 11 & 44 & 28 & 4 & 85 & 1 & 30 & 6 & 18 \\ 84 & 43 & 38 & 66 & 113 & 24 & 96 & 20 & 102 \\ 75 & 68 & 5 & 88 & 80 & 98 & 35 & 100 & 77 \\ 13 & 21 & 64 & 108 & 10 & 60 & 114 & 40 & 23 \\ 47 & 2 & 73 & 106 & 82 & 32 & 120 & 26 & 36 \\ 53 & 93 & 69 & 104 & 54 & 19 & 111 & 117 & 62 \\ 17 & 27 & 8 & 87 & 33 & 49 & 15 & 58 & 116 \\ 95 & 112 & 57 & 118 & 91 & 51 & 42 & 65 & 45 \\ \end{bmatrix}}}

Plaintext Test Cases:

[[8, 5, 6], [11, 10, 1], [3, 15, 13]]

[[21, 10, 12, 16], [17, 6, 22, 14], [8, 5, 19, 26], [13, 24, 3, 1]]

[[1, 13, 8, 16, 5], [9, 40, 21, 26, 22], [11, 24, 14, 39, 28], [32, 19, 37, 3, 10], [30, 17, 36, 7, 34]]

[[34, 21, 40, 22, 35, 41], [18, 33, 31, 30, 12, 43], [19, 11, 39, 24, 28, 23], [44, 1, 36, 5, 38, 45], [14, 17, 9, 16, 13, 26], [8, 3, 47, 6, 25, 4]]

[[20, 36, 17, 1, 15, 50, 18], [72, 67, 34, 10, 32, 3, 55], [42, 43, 9, 6, 30, 61, 39], [28, 41, 54, 27, 23, 5, 70], [48, 13, 25, 12, 46, 58, 63], [52, 37, 8, 45, 33, 14, 68], [59, 65, 56, 73, 60, 64, 22]]

[[85, 56, 52, 75, 89, 44, 41, 68], [27, 15, 87, 91, 32, 37, 39, 73], [6, 7, 64, 19, 99, 78, 46, 16], [42, 21, 63, 100, 4, 1, 72, 13], [11, 97, 30, 93, 28, 40, 3, 36], [50, 70, 25, 80, 58, 9, 60, 84], [54, 96, 17, 29, 43, 34, 23, 35], [77, 61, 82, 48, 2, 94, 38, 66]]

[[56, 79, 90, 61, 71, 122, 110, 31, 55], [11, 44, 28, 4, 85, 1, 30, 6, 18], [84, 43, 38, 66, 113, 24, 96, 20, 102], [75, 68, 5, 88, 80, 98, 35, 100, 77], [13, 21, 64, 108, 10, 60, 114, 40, 23], [47, 2, 73, 106, 82, 32, 120, 26, 36], [53, 93, 69, 104, 54, 19, 111, 117, 62], [17, 27, 8, 87, 33, 49, 15, 58, 116], [95, 112, 57, 118, 91, 51, 42, 65, 45]]

Please ask for more if you solve them all. :-) And many thanks to the people who helped me refine this challenge while in the sandbox.

---

¹ A reasonable amount of time: any amount of time that doesn't undermine our patience while testing your solution. Note that TIO only runs code for 60 seconds, any amount of time over that limit will make us test the code in our machines. Example: my rather inefficient algorithm takes a few milliseconds to solve matrices of order 3x3 and 4x4, but I have just tested it with a 5x5 matrix and it took 317 seconds to solve it (in over 5 million movements, very funny if we consider that the matrix to solve was scrambled only 10K times). I tried to reduce the number of movements to less than 10K but I surrendered after 30 minutes executing the code.

Answer 1

Nim

import algorithm, math, sequtils, strutils

let l = split(stdin.readLine())
var m = map(l, parseInt)
let n = int(sqrt(float(len(m))))
let o = sorted(m, system.cmp[int])

proc rotations(P, Q: int): tuple[D, L, R, U: string, P, Q: int]=
  result = (D: "D", L: "L", R: "R", U: "U", P: P, Q: Q)
  if P > n - P:
    result.D = "U"
    result.U = "D"
    result.P = n - P
  if Q > n - Q:
    result.L = "R"
    result.R = "L"
    result.Q = n - Q

proc triangle(r: int): string=
  let p = r div n
  let q = r mod n
  let i = find(m, o[r])
  let s = i div n
  let t = i mod n
  var u = s
  var v = q
  if s == p and t == q:
    return ""
  var patt = 0
  if p == s: 
    u = s + 1
    patt = 4
  elif q == t:
    if q == n - 1:
      v = t - 1
      patt = 8
    else:
      u = p
      v = t + 1
      patt = 3
  elif t > q:
    patt = 2
  else:
    patt = 7
  var Q = abs(max([q, t, v]) - min([q, t, v]))
  var P = abs(max([p, s, u]) - min([p, s, u]))
  let x = p*n + q
  let y = s*n + t
  let z = u*n + v
  let w = m[x]
  m[x] = m[y]
  m[y] = m[z]
  m[z] = w
  let R = rotations(P, Q)

  result = case patt:
    of 2:
      repeat("$#$#," % [$v, R.D], R.P) & 
        repeat("$#$#," % [$u, R.L], R.Q) &
        repeat("$#$#," % [$v, R.U], R.P) & 
        repeat("$#$#," % [$u, R.R], R.Q)
    of 3:
      repeat("$#$#," % [$q, R.U], R.P) & 
        repeat("$#$#," % [$p, R.L], R.Q) &
        repeat("$#$#," % [$q, R.D], R.P) & 
        repeat("$#$#," % [$p, R.R], R.Q)
    of 4:
      repeat("$#$#," % [$p, R.L], R.Q) & 
        repeat("$#$#," % [$q, R.U], R.P) &
        repeat("$#$#," % [$p, R.R], R.Q) & 
        repeat("$#$#," % [$q, R.D], R.P)
    of 7:
      repeat("$#$#," % [$v, R.D], R.P) & 
        repeat("$#$#," % [$u, R.R], R.Q) &
        repeat("$#$#," % [$v, R.U], R.P) & 
        repeat("$#$#," % [$u, R.L], R.Q)
    of 8:
      repeat("$#$#," % [$s, R.R], R.Q) & 
        repeat("$#$#," % [$t, R.D], R.P) &
        repeat("$#$#," % [$s, R.L], R.Q) & 
        repeat("$#$#," % [$t, R.U], R.P)
    else: ""

proc Tw(p, t, P, Q: int): string =
  let S = P + Q
  result = "$#D,$#$#U,$#$#D,$#$#U," % [
    $t, if P > n - P: repeat("$#L," % $p, n - P) else: repeat("$#R," % $p, P),
    $t, if S > n - S: repeat("$#R," % $p, n - S) else: repeat("$#L," % $p, S), 
    $t, if Q > n - Q: repeat("$#L," % $p, n - Q) else: repeat("$#R," % $p, Q), 
    $t]

proc line(r: int): string=
  let p = n - 1
  let q = r mod n
  let i = find(m, o[r])
  var t = i mod n
  if t == q: 
    return ""
  let j = t == n - 1
  var P = t - q
  let x = p*n + q
  let y = x + P
  let z = y + (if j: -1 else: 1)
  let w = m[x]
  m[x] = m[y]
  m[y] = m[z]
  m[z] = w
  if j:
    let R = rotations(1, P)
    result = "$#D,$#$#U,$#$#R,$#D,$#L,$#U," % [
      $t, repeat("$#$#," % [$p, R.R], R.Q), 
      $t, repeat("$#$#," % [$p, R.L], R.Q), 
      $p, $t, $p, $t]
  else:
    result = Tw(p, t, P, 1)  
  
proc swap: string=
  result = ""
  if m[^1] != o[^1]:
    m = o
    for i in 0..(n div 2-1):
      result &= Tw(n - 1, n - 2*i - 1, 1, 1)
    result &= "$#R," % $(n - 1)
  
var moves = ""
for r in 0..(n^2 - n - 1):
  moves &= triangle(r)
if n == 2 and m[^1] != o[^1]:
  m = o
  moves &= "1R"
else:
  for r in (n^2 - n)..(n^2 - 3):
    moves &= line(r)
  if n mod 2 == 0:
    moves &= swap()
  if len(moves) > 0:
    moves = moves[0..^2]
  
echo moves

Try it online!

A quick attempt to implement the Torus puzzle solution algorithm from an article published in Algorithms 2012, 5, 18-29 that I mentioned in comments.

Accepts the input matrix in flattened form, as a line of space-delimited numbers.

Here also is a validator in Python 2. It takes two lines as input: the original scrambled matrix in the same form as the main code, and the proposed sequence of moves. The output of the validator is the matrix resulting from applying these moves.

Explanation

In the first part of the algorithm, we order all rows except the last one.

We do this by performing series of "triangle rotations" (proc triangle) - the sequences of moves that result in only three cells swapping places, and all the rest staying unchanged. We take each consecutive "working" cell with coordinates \$[p, q]\$, then find the cell \$[s, t]\$ that currently contains the number that should go to \$[p, q]\$, and complete the right triangle by selecting a third point \$[u, v]\$ according to some pattern, as shown in Fig. 4 of the linked article.

In Fig. 2, the authors present 8 possible patterns and the corresponding sequences of moves, but in my code all cases have actually been covered by only 5 patterns, so that no. 1, 5, and 6 are not used.

In the second part, the last row except the two last elements is ordered by performing "three elements rotations" on a line (proc line), which consist of two triangle rotations each (see Fig. 3 of the article).

We select our current working cell \$[p, q]\$ as the left point, cell containing the target value \$[s, t]\$ as the central point, and \$[s, t+1]\$ as the right point. This westbound movement is named \$T_W\$ in the article, and so is my string forming proc for this. If \$t\$ is already the last column, so that \$t+1\$ does not exist, we take \$[s, t-1]\$ as the third point, and modify the action accordingly: two triangle rotations are performed by patterns 7 and 8 (instead of 7 and 1 in the original \$T_W\$ sequence).

Finally, if \$n\$ is odd, the remaining two elements must be already in place, as we are guaranteed that a solution exists. If \$n\$ is even, and the two remaining elements are not in place, then according to Lemma 1 (page 22), they can be swapped by a series of \$T_W\$ moves, followed by one shift east (\$=R\$). Since the provided example swaps the first two entries, and we need to swap the last two, our proc swap performs \$T_W\$ moves in reverse order.

In the edge case of \$n = 2\$ we don't need all these complex procedures at all - if the last row elements are not in place after part 1, a single \$1R\$ move is sufficient to make the matrix fully ordered.

Update: Added new proc rotations that reverses the direction of moves if that would result in less steps.

Answer 2

Python 2, size 100 in <30 seconds on TIO

import random
def f(a):
 d = len(a)
 r = []
 def V(j, b = -1):
  b %= d
  if d - b < b:
   for k in range(d - b):
    if r and r[-1] == "U%d" % j:r.pop()
    else:r.append("D%d" % j)
    b = a[-1][j]
    for i in range(len(a) - 1):
     a[-1 - i][j] = a[-2 - i][j]
    a[0][j] = b
  else:
   for k in range(b):
    if r and r[-1] == "D%d" % j:r.pop()
    else:r.append("U%d" % j)
    b = a[0][j]
    for i in range(len(a) - 1):
     a[i][j] = a[i + 1][j]
    a[-1][j] = b
 def H(i, b = -1):
  b %= d
  if d - b < b:
   for k in range(d - b):
    if r and r[-1] == "L%d" % i:r.pop()
    else:r.append("R%d" % i)
    a[i] = a[i][-1:] + a[i][:-1]
  else:
   for k in range(b):
    if r and r[-1] == "R%d" % i:r.pop()
    else:r.append("L%d" % i)
    a[i] = a[i][1:] + a[i][:1]
 b = sorted(sum(a, []))
 for i in range(d - 1):
  for j in range(d):
   c = b.pop(0)
   e = sum(a, []).index(c)
   if e / d == i:
    if j == 0:H(i, e - j)
    elif j < e % d:
     if i:
      V(e % d, 1)
      H(i, j - e)
      V(e % d)
      H(i, e - j)
     else:
      V(e)
      H(1, e - j)
      V(j, 1)
   else:
    if j == e % d:
     H(e / d)
     e += 1
     if e % d == 0:e -= d
    if i:
     V(j, i - e / d)
    H(e / d, e - j)
    V(j, e / d - i)
 c = [b.index(e) for e in a[-1]]
 c = [sum(c[(i + j) % d] < c[(i + k) % d] for j in range(d) for k in range(j)) % 2 and d * d or sum(abs(c[(i + j) % d] - j) for j in range(d)) for i in range(d)]
 e = min(~c[::-1].index(min(c)), c.index(min(c)), key = abs)
 H(d - 1, e)
 for j in range(d - 2):
  e = a[-1].index(b[j])
  if e > j:
   c = b.index(a[-1][j])
   if c == e:
    if e - j == 1:c = j + 2
    else:c = j + 1
   V(e)
   H(d - 1, j - e)
   V(e, 1)
   H(d - 1, c - j)
   V(e)
   H(d - 1, e - c)
   V(e, 1)
 return r

Try it online! Link includes three small test cases with full move output, plus a silent test of 100x100 to show that the code works (the move output would exceed TIO's limits). Explanation: The code attempts to perform an insertion sort on the array, building it up in ascending order as it goes. For all the rows except the last row, there are a number of cases:

• The element is in the correct row, but belongs in column 0. In this case, it is simply rotated until it reaches column 0.
• The element is in the correct place. In this case, nothing happens. (This is also true if the element belongs in column 0, it's just that 0 rotations happen in that case.)
• The element is in the top row but in the wrong column. In that case, it is rotated down, then horizontally until the element is in the correct column, then rotated up again.
• The element is in the correct row but in the wrong column. In that case, it is rotated up, then the row is rotated to its column, then it is rotated down, then the row is rotated back. (Effectively this is a rotation of the next case.)
• The element is in the correct column but in the wrong row. In that case, the row is rotated right, to reduce it to the last case.
• The element is in the wrong row and the wrong column. In this case, the correct column is rotated to the wrong row (skipped for the top row), that row is then rotated to the correct column, and the column is then rotated back.

The above rotations are performed in whichever direction minimises the number of steps; a size 2 square is always solved using left and up moves, regardless of the description above.

Before the bottom row is completed, it is rotated to minimise the total distance out of place, but also to ensure that the parity of the bottom row is even, as it can't be changed by the final part of the algorithm. If there is more than one rotation with the same minimal distance, the rotation with the smallest number of moves is chosen.

The algorithm for the bottom row relies on a 7-operation sequence which exchanges the elements in three columns. The sequence is applied to each of the remaining numbers of the bottom row in order in turn to bring them to their desired location; if possible the element in that location is moved to its desired location, but if a straight swap is needed the element is simply moved to the nearest available column, hopefully allowing it to be fixed up next time.