Pomysł na to wyzwanie kodu jest prosty: biorąc pod uwagę macierz liczb całkowitych, posortujmy je stosując ruchy w stylu Rubika. Oznacza to, że możesz wybrać pojedynczy wiersz lub kolumnę i obrócić jej elementy w dowolnym kierunku:

[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)

Tak więc, biorąc pod uwagę macierz liczb całkowitych o dowolnym wymiarze, posortuj jej elementy stosując tylko te transformacje w stylu Rubika. Matryca

$$\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}$$

będą uważane za posortowane, jeśli jego elementy są zgodne z następującym ograniczeniem:

$$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

• Wejście będzie macierzą dodatnich liczb całkowitych bez powtarzanych wartości.
• Wyjściowe będą ruchy potrzebne do posortowania. Ponieważ nie jest to wyzwanie dla golfa kodowego i nie musisz się martwić o jego długość, proponowany format każdego ruchu to miejsce, w #[UDLR]którym #znajduje się numer wiersza lub kolumny do przesunięcia (indeksowany 0) i [UDLR]jest to pojedynczy znak zakres określający, czy ruch jest w górę / w dół (dla kolumn) czy w lewo / w prawo (dla wierszy). 1UOznaczałoby to zatem „przesunięcie pierwszej kolumny w górę”, ale 1Roznaczałoby „przesunięcie pierwszego rzędu w prawo”. Zmiany będą rozdzielone przecinkami więc rozwiązanie będzie wyrażona w następujący sposób: 1R,1U,0L,2D.

Punktacja

Próba posortowania macierzy w ten sposób może być kosztowna, ponieważ istnieje wiele możliwych kombinacji ruchów, a także istnieje wiele możliwych list ruchów, które mogą ją posortować, więc celem jest napisanie kodu, który sortuje N * N macierzy poniżej. Wynik będzie największym rozmiarem N, który można rozwiązać w rozsądnym czasie ¹ bez błędów (im większy rozmiar rozwiązanej macierzy, tym lepiej). W przypadku remisu rozstrzygającym będzie liczba ruchów na znalezionej ścieżce (im krótsza ścieżka, tym lepiej).

Przykład: jeśli użytkownik A znajdzie rozwiązanie dla N = 5, a B znajdzie rozwiązanie dla N = 6, B wygrywa niezależnie od długości obu ścieżek. Jeśli oboje znajdą rozwiązania dla N = 6, ale rozwiązanie znalezione przez A ma 50 kroków, a rozwiązanie B ma 60 kroków, A wygrywa.

Zachęcamy do wyjaśnienia, w jaki sposób działa Twój kod i opublikuj znalezione rozwiązania, abyśmy mogli je przetestować . Możesz użyć Pastebin lub podobnych narzędzi, jeśli rozwiązania są zbyt duże. Doceniony zostanie również szacunkowy czas poświęcony przez kod na znalezienie rozwiązań.

Przypadki testowe

Utworzono następujące macierze ( łącze Pastebin dla wersji bardziej wklejalnej), zaczynając od już posortowanych macierzy, mieszając je losowymi ruchami w stylu Rubika o wielkości 10K:

$$\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.

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

Wypróbuj online!

Szybka próba zaimplementowania algorytmu rozwiązania łamigłówki Torus z artykułu opublikowanego w Algorytmach 2012, 5, 18–29, o którym wspomniałem w komentarzach.

Akceptuje macierz wejściową w spłaszczonej formie, jako linię liczb rozdzielanych spacjami.

Tutaj także znajduje się walidator w Python 2 . Dane wejściowe wymagają dwóch wierszy: oryginalnej zaszyfrowanej matrycy w tej samej formie co kod główny i proponowanej sekwencji ruchów. Wyjściem walidatora jest macierz wynikająca z zastosowania tych ruchów.

Wyjaśnienie

W pierwszej części algorytmu porządkujemy wszystkie wiersze z wyjątkiem ostatniego.

Robimy to, wykonując serię „rotacji trójkątów” ( proc triangle) - sekwencje ruchów, w wyniku których tylko trzy komórki zamieniają się miejscami, a cała reszta pozostaje niezmieniona. Bierzemy każdą kolejną „działającą” komórkę ze współrzędnymi$[p, q]$, a następnie znajdź komórkę $[s, t]$ która obecnie zawiera numer, na który należy przejść $[p, q]$i ukończ właściwy trójkąt, wybierając trzeci punkt $[u, v]$ zgodnie z pewnym wzorem, jak pokazano na ryc. 4 połączonego artykułu.

Na ryc. 2 autorzy przedstawiają 8 możliwych wzorców i odpowiadające im sekwencje ruchów, ale w moim kodzie wszystkie przypadki zostały objęte jedynie 5 wzorami, więc nie. 1, 5 i 6 nie są używane.

W drugiej części ostatni rząd, z wyjątkiem dwóch ostatnich elementów, jest uporządkowany poprzez wykonanie „trzech rotacji elementów” na linii ( proc line), która składa się z dwóch rotacji trójkątów każdy (patrz ryc. 3 artykułu).

Wybieramy naszą obecną działającą komórkę $[p, q]$ jako lewy punkt komórka zawierająca wartość docelową $[s, t]$ jako punkt centralny, oraz $[s, t+1]$jako właściwy punkt. Ten ruch na zachód nazywa się$T_W$w artykule, podobnie jak mój proces formowania łańcucha w tym celu. Gdyby$t$ jest już ostatnią kolumną, więc $t+1$ nie istnieje, bierzemy $[s, t-1]$ jako trzeci punkt i odpowiednio zmodyfikuj akcję: dwa obroty trójkątów są wykonywane według wzorów 7 i 8 (zamiast 7 i 1 w oryginale $T_W$ sekwencja).

Wreszcie, jeśli $n$jest dziwny, pozostałe dwa elementy muszą już być na miejscu, ponieważ gwarantujemy, że istnieje rozwiązanie. Gdyby$n$ jest parzysty, a dwa pozostałe elementy nie są na swoim miejscu, więc zgodnie z Lematem 1 (strona 22) można je zamienić serią $T_W$ ruchy, a następnie jedna zmiana na wschód ($=R$). Ponieważ podany przykład zamienia pierwsze dwa wpisy, a my musimy zamienić ostatnie dwa, nasze proc swapwykonanie$T_W$ porusza się w odwrotnej kolejności.

W przypadku krawędzi $n = 2$ w ogóle nie potrzebujemy tych wszystkich skomplikowanych procedur - jeśli elementy ostatniego rzędu nie są na miejscu po części 1, pojedynczym $1R$ ruch jest wystarczający, aby matryca była w pełni uporządkowana.

Aktualizacja: Dodano nowy, proc rotationsktóry odwraca kierunek ruchów, jeśli spowodowałoby to mniej kroków.

Python 2 , rozmiar 100 w <30 sekund na 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

Wypróbuj online! Link zawiera trzy małe przypadki testowe z pełnym wyjściem ruchu oraz plus cichy test 100 x 100, aby pokazać, że kod działa (wyjście ruchu przekroczyłoby granice TIO). Objaśnienie: Kod próbuje wykonać sortowanie wstawiania na tablicy, budując go w porządku rosnącym w miarę upływu czasu. Dla wszystkich wierszy z wyjątkiem ostatniego wiersza istnieje wiele przypadków:

• Element znajduje się we właściwym wierszu, ale należy do kolumny 0. W takim przypadku jest on po prostu obracany, aż osiągnie kolumnę 0.
• Element znajduje się we właściwym miejscu. W tym przypadku nic się nie dzieje. (Jest to również prawdą, jeśli element należy do kolumny 0, po prostu w tym przypadku ma miejsce 0 obrotów).
• Element znajduje się w górnym rzędzie, ale w niewłaściwej kolumnie. W takim przypadku jest on obracany w dół, a następnie poziomo, aż element znajdzie się we właściwej kolumnie, a następnie ponownie obracany w górę.
• Element znajduje się we właściwym wierszu, ale w niewłaściwej kolumnie. W takim przypadku jest on obracany w górę, następnie rząd jest obracany do swojej kolumny, następnie jest obracany w dół, a następnie rząd jest obracany z powrotem. (W rzeczywistości jest to rotacja następnego przypadku.)
• Element znajduje się we właściwej kolumnie, ale w niewłaściwym wierszu. W takim przypadku wiersz zostanie obrócony w prawo, aby zredukować go do ostatniego przypadku.
• Element znajduje się w niewłaściwym wierszu i niewłaściwej kolumnie. W takim przypadku poprawna kolumna jest obracana do niewłaściwego wiersza (pomijana dla górnego wiersza), wiersz ten jest następnie obracany do właściwej kolumny, a następnie kolumna jest obracana z powrotem.

Powyższe obroty są wykonywane w dowolnym kierunku, co minimalizuje liczbę kroków; kwadrat 2 zawsze rozwiązuje się za pomocą ruchów w lewo iw górę, niezależnie od powyższego opisu.

Przed zakończeniem dolnego rzędu jest on obracany, aby zminimalizować całkowitą odległość poza miejscem, ale także w celu zapewnienia, że ​​parzystość dolnego rzędu jest równa, ponieważ nie można go zmienić w końcowej części algorytmu. Jeśli istnieje więcej niż jeden obrót przy tej samej minimalnej odległości, wybierany jest obrót z najmniejszą liczbą ruchów.

Algorytm dla dolnego rzędu opiera się na 7-operacyjnej sekwencji, która wymienia elementy w trzech kolumnach. Sekwencja jest stosowana do każdej z pozostałych liczb dolnego rzędu po kolei, aby doprowadzić je do pożądanego miejsca; jeśli to możliwe, element w tej lokalizacji jest przenoszony do pożądanej lokalizacji, ale jeśli potrzebna jest prosta zamiana, element jest po prostu przenoszony do najbliższej dostępnej kolumny, co ma nadzieję, że można go naprawić następnym razem.