-2
$\begingroup$

In a 4x4 grid, it is required that each row and each column contains exactly one selected square. Enumerate all the four squares that are selected. And identify the selection that, among those that meet the aforementioned criteria, yields the maximum sum of the four numbers.

4x4 grid as follows:

Grid[{{11, 21, 31, 40}, {12, 22, 33, 42}, {13, 22, 33, 43}, {15, 24, 
   34, 44}}, Frame -> All]

enter image description here

numbers = {{11, 21, 31, 40}, {12, 22, 33, 42}, {13, 22, 33, 43}, {15, 
   24, 34, 44}}
allPermutations = Permutations[Range[1, 4]]
validSelections = 
 Select[allPermutations, 
  Module[{selection}, 
    selection = 
     numbers[[#[[1]]]] + numbers[[#[[2]] + 1]][[#[[2]]]] + 
       numbers[[#[[3]] + 2]][[#[[3]] + 1]] + 
       numbers[[#[[4]]]][[#[[4]]];
        Table[selection[[#]] == numbers[[i, #]], {i, 4}], {#, 
         4}] === {1, 1, 1, 1}] &]

The above code did not produce the correct result.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ There is a resource function in the repositiory that solves this problem exactly using integer linear optimization, and it will even work for very large matrices: ResourceFunction["MinSumPermutation"][-numbers] gives {2, 3, 4, 1}. Try, for example, with numbers = RandomInteger[{-1000, 1000}, {1000, 1000}] to check that this is an amazing resource function! $\endgroup$
    – Roman
    Commented Jul 3 at 6:22
  • 1
    $\begingroup$ (-1) I don't even see your effort in writing a question. The description of the question is simply not understandable, what do you mean by "each row and each column contains exactly one selected square", "four squares", etc? $\endgroup$
    – xzczd ♦
    Commented Jul 5 at 2:43

4 Answers 4

Reset to default
4
$\begingroup$ 
A = {{11, 21, 31, 40}, {12, 22, 33, 42}, {13, 22, 33, 43}, {15, 24, 34, 44}};

MaximalBy[MapThread[Part, {A, #}] & /@ Permutations[Range[4]], Total]
(*    {{21, 33, 43, 15}}    *)

If you want the intermediate list as well:

MapThread[Part, {A, #}] & /@ Permutations[Range[4]]
(*    {{11, 22, 33, 44}, {11, 22, 43, 34}, {11, 33, 22, 44},
       {11, 33, 43, 24}, {11, 42, 22, 34}, {11, 42, 33, 24},
       {21, 12, 33, 44}, {21, 12, 43, 34}, {21, 33, 13, 44},
       {21, 33, 43, 15}, {21, 42, 13, 34}, {21, 42, 33, 15},
       {31, 12, 22, 44}, {31, 12, 43, 24}, {31, 22, 13, 44},
       {31, 22, 43, 15}, {31, 42, 13, 24}, {31, 42, 22, 15},
       {40, 12, 22, 34}, {40, 12, 33, 24}, {40, 22, 13, 34},
       {40, 22, 33, 15}, {40, 33, 13, 24}, {40, 33, 22, 15}}    *)

MaximalBy[%, Total]
(*    {{21, 33, 43, 15}}    *)

For much larger systems, exhaustive searching of all permutations is impossible. But we can do a Metropolis–Hastings "Monte Carlo" stochastic search:

SeedRandom[1234];
n = 30;
m = 9;
A = RandomInteger[{0, m}, {n, n}];

ResourceFunction["MaximizeOverPermutations"][
  Total[MapThread[Part, {A, #}]] &, n,
  Method -> "MonteCarlo"]
(*    {{{12, 5, 2, 8, 3, 18, 23, 24, 30, 16, 13, 28, 25, 15, 10,
         26, 1, 4, 11, 19, 7, 14, 6, 17, 9, 29, 22, 20, 27, 21}}, 260.}

This MaximizeOverPermutations resource function has fine-grained options for controlling the stochastic search.

Improve this answer
$\endgroup$
1
  • $\begingroup$ very neat +1 :) $\endgroup$
    – ubpdqn
    Commented Jul 2 at 8:36
2
$\begingroup$

As far as I understand, all 4! permutation correspond to valid choice. For the permutation {i1,i2,i3,i4}, just take (1,i1), (2,i2), (3,i3) and (4,i4) elements from the 4x4 matrix. This rule is exactly the same as the definition of matrix determinant.

numbers = {{11, 21, 31, 40}, {12, 22, 33, 42}, {13, 22, 33, 43}, {15, 24, 34, 44}};
allPermutations = Permutations[Range[1, 4]];
allchoices = 
 Extract[numbers, Transpose[{Range[4], #}]] & /@ allPermutations

 (* {{11, 22, 33, 44}, {11, 22, 43, 34}, {11, 33, 22, 44}, {11, 
  33, 43, 24}, {11, 42, 22, 34}, {11, 42, 33, 24}, {21, 12, 33, 
  44}, {21, 12, 43, 34}, {21, 33, 13, 44}, {21, 33, 43, 15}, {21, 42, 
  13, 34}, {21, 42, 33, 15}, {31, 12, 22, 44}, {31, 12, 43, 24}, {31, 
  22, 13, 44}, {31, 22, 43, 15}, {31, 42, 13, 24}, {31, 42, 22, 
  15}, {40, 12, 22, 34}, {40, 12, 33, 24}, {40, 22, 13, 34}, {40, 22, 
  33, 15}, {40, 33, 13, 24}, {40, 33, 22, 15}} *)

  MaximalBy[allchoices, Total]

  (* {{21, 33, 43, 15}} *)
Improve this answer
$\endgroup$
2
$\begingroup$ 
m = {{11, 21, 31, 40}, {12, 22, 33, 42}, {13, 22, 33, 43}, {15, 24, 
    34, 44}};
p = Permutations[Range[4]];
cases = Extract[m, #] & /@ Thread[{Range[4], #}] & /@ p;
sums = Total /@ cases;
Extract[cases, Position[sums, Max[sums]]]
mx = MapAt[Style[#, Purple, Background -> Green] &, sums, {10}];
pos = Thread[{Range[4], #}] & /@ p;
gds = Grid[MapAt[Style[#, Red] &, m, #], Frame -> All] & /@ pos;
Partition[Column[#, Alignment -> Center] & /@ Thread[{mx, gds}], 
  4] // Grid

enter image description here

Improve this answer
$\endgroup$
1
$\begingroup$ 
A = {{11, 21, 31, 40}, {12, 22, 33, 42}, {13, 22, 33, 43}, {15, 24, 34, 44}};
MaximalBy[{A #, Total[A #, 2]} & /@ Permutations@IdentityMatrix@4, Last]

{{$\left( \begin{array}{cccc} 0 & 21 & 0 & 0 \\ 0 & 0 & 33 & 0 \\ 0 & 0 & 0 & 43 \\ 15 & 0 & 0 & 0 \\ \end{array} \right)$,112}}

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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