title: Maximise sum of "non-overlapping" numbers from matrix
body: <p>Just looking for a bit of direction, I realise that the example given is possible to solve using brute force iteration, but I am looking for a more elegant (ie. mathematical?) solution which could potentially solve significantly larger examples (say 20x20 or 30x30). It is entirely possible that this cannot be done, and I have had very little success in coming up with an approach which does not rely on brute force...</p>
  
  <p>I have a matrix (call it A) which is nxn. I wish to select a subset (call it B) of points from matrix A. The subset will consist of n elements, where one and only one element is taken from each row and from each column of A. The output should provide a solution (B) such that the sum of the elements that make up B is the maximum possible value, given these constraints (eg. 25 in the example below). If multiple instances of B are found (ie. different solutions which give the same maximum sum) the solution for B which has the largest minimum element should be selected. </p>
  
  <p>B could also be a selection matrix which is nxn, but where only the n desired elements are non-zero.</p>
  
  <p>For example:
  if A =</p>
  
  <pre><code>|5 4 3 2 1|
  |4 3 2 1 5|
  |3 2 1 5 4|
  |2 1 5 4 3|
  |1 5 4 3 2|
  </code></pre>
  
  <p>=> B would be</p>
  
  <pre><code>|5 5 5 5 5|
  </code></pre>
  
  <p>However, if A = </p>
  
  <pre><code>|5 4 3|
  |4 3 2|
  |3 2 1|
  </code></pre>
  
  <p>B =</p>
  
  <pre><code>|3 3 3|
  </code></pre>
  
  <p>As the minimum element of B is 3 which is larger than for </p>
  
  <pre><code>|5 3 1|
  </code></pre>
  
  <p>or</p>
  
  <pre><code>|4 4 1|
  </code></pre>
  
  <p>which also both sum to 9</p>