Given 2d matrix find minimum sum of elements such that element is chosen one from each row and column?

Find minimum sum of elements of n*n 2D matrix such that I have to choose one and only one element from each row and column ? Eg

4  12 

6  6

If I choose 4 from row 1 I cannot choose 12 from row 1 also from column 1 , I can only choose 6 from row 2 column 2.

So likewise minimum sum would be 4 + 6 = 10 where 6 is from second row second column

and not 6 + 12 = 18 where 6 is from second row first column

also 4 + 12 is not allowed since both are from same row

I thought of brute force where once i pick element from row and column I cannot pick another but this approach is O(n!) .

Theorem: If a number is added to or subtracted from all of the entries of any one row or column of the matrix, then elements selected to get required minimum sum of the resulting matrix are the same elements selected to get required minimum sum of the original matrix.

The Hungarian Algorithm (a special case of min-cost flow problem) uses this theorem to select those elements satisfying the constraints given in your problem :

1. Subtract the smallest entry in each row from all the entries of its row.
2. Subtract the smallest entry in each column from all the entries of its column.
3. Draw lines through appropriate rows and columns so that all the zero entries of the cost matrix are covered and the minimum number of such lines is used.
4. Test for Optimality
   i. If the minimum number of covering lines is n, an optimal assignment of zeros is possible and we are finished.
   ii. If the minimum number of covering lines is less than n, an optimal assignment of zeros is not yet possible. In that case, proceed to Step 5.
5. Determine the smallest entry not covered by any line. Subtract this entry from each uncovered row, and then add it to each covered column. Return to Step 3.

See this example for better understanding.

Both O(n⁴) (easy and fast to implement) and O(n³) (harder to implement) implementations are explained in detail here.