9
\$\begingroup\$

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.

\$\endgroup\$

closed as too broad by xnor, Moris Zucca, Zach Gates, cat, mbomb007 Jan 19 '16 at 22:39

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\begingroup\$ Is this a puzzle, speed, or golfing problem? \$\endgroup\$ – Michael Klein Jan 18 '16 at 15:39
  • \$\begingroup\$ @MichaelKlein This is a puzzle. \$\endgroup\$ – JCarter Jan 18 '16 at 15:42
  • \$\begingroup\$ Is it scored? What ranges need to be handled? \$\endgroup\$ – Michael Klein Jan 18 '16 at 15:44
  • 1
    \$\begingroup\$ @steveverrill I'm afraid it is quite impossible to solve the n=10 example in less than 100 swaps (or even 1000; but please prove me wrong). Still, the number of swaps is the winning criterion (though computation must be feasible!), the one who comes up with a solution with the lowest number of swaps wins. \$\endgroup\$ – JCarter Jan 18 '16 at 15:53
  • 1
    \$\begingroup\$ @JCarter I think you meant to say that only adjacent numbers may be swapped? \$\endgroup\$ – quintopia Jan 18 '16 at 15:58
3
\$\begingroup\$

Mathematica, not golfed

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

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->76,1->34,1->35,1->88,1->41,11->16,11->69,11->46, ...

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

enter image description here

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.