Sort scrambled two-dimensional array filled with numbers by swapping adjacent numbers A two-dimensional array of size n×n is filled with n*n numbers, starting from number 1. Those numbers are to be sorted per row in ascending order; the first number of a row must be greater than the last number of the previous row (the smallest number of all (1) will be in [0,0]). This is similar to the 15 puzzle.

This is, for example, a sorted array of size n = 3.

1 2 3
4 5 6
7 8 9


Input

The input is a scrambled array. It can be of any size up to n = 10. Example for n = 3:

4 2 3
1 8 5
7 9 6


Output

Output a list of swaps required to sort the array. A swap is defined as following: Two adjacent numbers swap positions, either horizontally or vertically; diagonal swapping is not permitted.

Example output for the example above:


Swap 4 and 1
Swap 8 and 5
Swap 8 and 6
Swap 9 and 8


The less swaps required, the better. Computation time must be feasible.



Here is another example input, with 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


If I'm not mistaken, this would require around 1000-2000 swaps.
Mathematica, not golfed

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




Explanation:

The algorithm is similar to "bubble sort". These 100 numbers are put into correct order one by one, 1, 11, 21, ..., 91; 2, ..., 92; ...; 10, ..., 100. They are first move up/down to the correct rows, and then move left to the correct columns. 

Function towards gives the two position to swap. For example, if {5,2} is moving to {1,1}, towards[{5,2},{1,1}] gives {{5,2},{5,1}} (move up); and  towards[{5,1},{1,1}] gives {{5,1},{4,1}} (move left).



Results:

For the test case, the total number of swaps is 558. The first few swaps are, 

{1-&gt;76,1-&gt;34,1-&gt;35,1-&gt;88,1-&gt;41,11-&gt;16,11-&gt;69,11-&gt;46, ...


For a random configuration, the total number of swaps is 558.5 ± 28.3 (1σ).