<p>I'm pretty sure that this is some kind of variant of the <a href="http://en.wikipedia.org/wiki/Exact_cover_problem" rel="nofollow">exact cover problem</a>, which is known to be NP-complete. Your proposed algorithm is a simple greedy solution. The problem with greedy solutions is that they often work well enough to convince you that greed is good and then suddenly leave you high and dry looking for a better solution. (Consider the global economy, for example.) Anyway, Knuth's <a href="http://en.wikipedia.org/wiki/Dancing_Links" rel="nofollow">Dancing</a> <a href="http://arxiv.org/pdf/cs/0011047v1.pdf" rel="nofollow">Links</a> technique is a standard way of solving the problem (exact set cover, not global economy).</p>
Iterative Reduction to Null Matrix
<p>Here's the problem: I'm given a matrix like</p>

<p>Input:</p>

<pre><code>1 1 1
1 1 1
1 1 1
</code></pre>

<p>At each step, I need to find a "second" matrix of 1's and 0's with no two 1's on the same row or column. Then, I'll subtract the second matrix from the original matrix. I will repeat the process until I get a matrix with all 0's. Furthermore, I need to take the least possible number of steps.</p>

<p>I need to print all the "second" matrices in O(n) time. In the above example I can get to the null matrix in 3 steps by subtracting these three matrices in order:</p>

<p>Expected output:</p>

<pre><code>1 0 0
0 1 0
0 0 1

0 0 1
1 0 0
0 1 0

0 1 0
0 0 1
1 0 0
</code></pre>

<p>I have coded an attempt, in which I am finding the first maximum value and creating the second matrices based on the index of that value. But for the above input I am getting 4 output matrices, which is wrong:</p>

<p>My output:</p>

<pre><code>1 0 0 
0 1 0 
0 0 1 

0 1 0 
1 0 0 
0 0 0 

0 0 1 
0 0 0 
1 0 0 

0 0 0 
0 0 1 
0 1 0  
</code></pre>

<p>My solution works for most of the test cases but fails for the one given above. Can someone give me some pointers on how to proceed, or find an algorithm that guarantees optimality?</p>

<p>Test case that works:</p>

<p>Input:</p>

<pre><code>0 2 1
0 0 0
3 0 0
</code></pre>

<p>Output</p>

<pre><code>0 1 0
0 0 0
1 0 0

0 1 0
0 0 0
1 0 0 

0 0 1
0 0 0
1 0 0
</code></pre>