How to Add Numbers in a Matrix to Yield Minimum Result?

Question

This is more of an algorithmic/math problem but I'm hoping to implement a solution in C++.

Suppose I have a matrix like so where the dots represent integers:

   W  X  Y  Z
A  .  .  .  . 
B  .  .  .  .
C  .  .  .  .
D  .  .  .  .

How would I yield the minimum result if I had to pick one number from each column such that there is at most one number from each row?

For instance, I could choose AW BX CY DZ or AZ BX CY DW but NOT AW BW CZ DZ

The brute force approach would seem to take n! calculations. Is there a quicker way? Eventually I would like to add numbers in matrices of size ~60.

Also, all numbers range from 0 to 256.

Answer 1

And if you'd rather not code it yourself, you could always use someone else' hard-work and kind publication. This one in Haskell, solves a 60x60 random matrix in less than two tenths of a second on my old laptop. What a great algorithm!

import Data.Algorithm.Munkres
import Data.Array.Unboxed
import Data.List (transpose)

solve n matrix = 
  hungarianMethodInt (listArray ((1,1),(n,n)) $ concat $ transpose matrix)