Dwuwymiarowa tablica o rozmiarze n × n jest wypełniona liczbami n * n, zaczynając od liczby 1. Liczby te należy posortować według rzędów w porządku rosnącym; pierwsza liczba rzędu musi być większa niż ostatnia liczba poprzedniego rzędu (najmniejsza liczba wszystkich (1) będzie w [0,0]). Jest to podobne do układanki 15 .

Jest to na przykład posortowana tablica o rozmiarze n = 3 .

1 2 3
4 5 6
7 8 9

Wejście

Dane wejściowe to zaszyfrowana tablica. Może mieć dowolny rozmiar do n = 10. Przykład dla n = 3:

4 2 3
1 8 5
7 9 6

Wynik

Wyjście lista swapów wymagane do sortowania tablicy. Wymiany jest zdefiniowany w następujący sposób: Dwa sąsiednie numery zamiany pozycji albo poziomej albo pionowej; zamiana po przekątnej jest niedozwolona.

Przykładowe dane wyjściowe dla powyższego przykładu:

• Zamień 4 i 1
• Zamień 8 i 5
• Zamień 8 i 6
• Zamień 9 i 8

Im mniej wymaganych swapów, tym lepiej. Czas obliczeń musi być wykonalny.

Oto kolejny przykładowy wpis, gdzie n = 10:

41 88 35 34 76 44 66 36 58 28
6 71 24 89 1 49 9 14 74 2
80 31 95 62 81 63 5 40 29 39
17 86 47 59 67 18 42 61 53 100
73 30 43 12 99 51 54 68 98 85
13 46 57 96 70 20 82 97 22 8
10 69 50 65 83 32 93 45 78 92
56 16 27 55 84 15 38 19 75 72
33 11 94 48 4 79 87 90 25 37
77 26 3 52 60 64 91 21 23 7

Jeśli się nie mylę, wymagałoby to około 1000-2000 zamian.

Mathematica, nie grał w golfa

towards[a_,b_]:={a,a+If[#==0,{0,Sign@Last[b-a]},{#,0}]&@Sign@First[b-a]};
f[m_]:=Block[{m2=Map[QuotientRemainder[#-1,10]+1&,m,{2}]},
  Rule@@@Apply[10(#1-1)+#2&,#,{2}]&@
    Reap[Table[
      m2=NestWhile[
        Function[{x},x/.(Sow[#];Thread[#->Reverse@#])&[x[[##]]&@@@towards[First@Position[x,i,{2}],i]]]
        ,m2,#~Extract~i!=i&];
      ,{i,Reverse/@Tuples[Range[10],2]}];][[2,1]]]

Objaśnienie :

Algorytm jest podobny do „sortowania bąbelkowego”. Te 100 liczb ułożonych jest we właściwej kolejności, jedna po drugiej 1, 11, 21, ..., 91; 2, ..., 92; ...; 10, ..., 100,. Są one najpierw przesuwane w górę / w dół do właściwych wierszy, a następnie w lewo do właściwych kolumn.

Funkcja towardspodaje dwie pozycje do zamiany. Na przykład, jeśli {5,2}się przenosi {1,1}, towards[{5,2},{1,1}]daje {{5,2},{5,1}}(przejście w górę); i towards[{5,1},{1,1}]daje {{5,1},{4,1}}(przesuń w lewo).

Wyniki :

W przypadku testowym całkowita liczba swapów wynosi 558. Kilka pierwszych swapów to:

{1->76,1->34,1->35,1->88,1->41,11->16,11->69,11->46, ...

W przypadku konfiguracji losowej całkowita liczba zamian wynosi 558,5 ± 28,3 (1σ).