Unsolvable(?) Assignment Problem I've recently been trying to implement the Hungarian Method in C++, and I've been using 5x5 matrices to test my program. Last night I came across a matrix which neither I nor my program can solve. Is it truly unsolvable, or am I missing something?
It starts like this:
\begin{bmatrix}2&3&7&4&8\\5&0&8&8&7\\1&5&0&5&3\\7&1&8&7&7\\4&9&3&8&6\end{bmatrix}
and after row and column reduction I get this:
\begin{bmatrix}0&1&5&0&3\\5&0&8&6&4\\1&5&0&3&0\\6&0&7&4&3\\1&6&0&3&0\end{bmatrix}
Assignments are made and lines are drawn:
\begin{bmatrix}A&1&5&0&3\\5&A&8&6&4\\1&5&0&3&0\\6&0&7&4&3\\1&6&0&3&0\end{bmatrix}\begin{bmatrix}-&+&+&-&-\\5&|&|&6&|\\1&|&|&3&|\\6&|&|&4&|\\1&|&|&3&|\end{bmatrix}
and I get this matrix:
\begin{bmatrix}0&2&6&0&4\\4&0&8&5&4\\0&5&0&2&0\\5&0&7&3&3\\0&6&0&2&0\end{bmatrix}
After another round of assigning and line-drawing I get this:
\begin{bmatrix}2&4&8&0&6\\4&0&8&3&4\\0&5&0&0&0\\5&0&7&1&3\\0&6&0&0&0\end{bmatrix}
and can't go any further. The only assignments that can be made are in the first two rows, and when the lines are drawn every column is covered. I had thought this meant that multiple solutions exist, but I can't find them.
edit: I have brute-forced this to find the correct answers. With (0,0) being the top left, and (4,4) being the bottom right, the solutions are as follows:
(0,0)(1,1)(2,2)(3,3)(4,4) = 2, 0, 0, 7, 6 = 15
(3,0)(1,1)(2,2)(4,3)(0,4) = 4, 0, 0, 7, 4 = 15  
Brute force is not going to work on larger matrices though, so I need a better solution.  
edit 2: I missed one. Credit to sanjab.
(0,0)(1,1)(4,2)(3,3)(2,4) = 2, 0, 3, 7, 3 = 15
 A: Thanks to WimC's comment on my question, I have gotten my code working. While all implementations of the Hungarian Method I have seen only assign zeroes if they are unique in their row and column, assigning random zeroes from those remaining seems to help with the line-drawing step. Doing so before drawing the lines has allowed my program to find an answer to this problem (it chose the first solution I posted at the bottom of my question). My program has been quite happily running on randomly generated matrices for three hours now, so this seems like a valid tactic to add to the Hungarian Method.
A: I don't know much about it. But I just calculated it with R. Using your matrix I get the result: $(5, 2, 3, 1, 4)$
R code I used:

library("GraphAlignment")
m <- matrix(c(2,5,1,7,4,3,0,5,1,9,7,8,0,8,3,4,8,5,7,8,8,7,3,7,6),5)
px <- LinearAssignment(m)
px

I used this method http://www.thp.uni-koeln.de/~berg/GraphAlignment/R-docs/LinearAssignment.html from this package http://www.thp.uni-koeln.de/~berg/GraphAlignment/ to do the calculation
EDIT: This looks like it is wrong. I calculated it again with a different package:

library("lpSolve")
assign.costs <- matrix(c(2,5,1,7,4,3,0,5,1,9,7,8,0,8,3,4,8,5,7,8,8,7,3,7,6),5)
lp.assign (assign.costs)
lp.assign (assign.costs)$solution

This outputs:
     [,1] [,2] [,3] [,4] [,5]
     [1,]    1    0    0    0    0
     [2,]    0    1    0    0    0
     [3,]    0    0    0    0    1
     [4,]    0    0    0    1    0
     [5,]    0    0    1    0    0

