title: Algorithm X to Solve the Exact Cover: Fat Matrices
body: <p>As I was reading about Knuth's Algorithm X to solve the exact cover problem, I thought of an edge case that I wanted some clarification on.</p>
  
  <p>Here are my assumptions:</p>
  
  <ol>
  <li>Given a matrix A, Algorithm X's "goal is to select a subset of the rows so that the digit 1 appears in each column <strong>exactly once</strong>."</li>
  <li>If the matrix is empty, the algorithm terminates successfully and the solution is then the subset of rows logged in the partial solution up to that point.</li>
  <li>If there is a column of 0's, the algorithm terminates unsuccessfully.</li>
  </ol>
  
  <p>For reference: <a href="http://en.wikipedia.org/wiki/Algorithm_X" rel="nofollow">http://en.wikipedia.org/wiki/Algorithm_X</a></p>
  
  <p>Consider the matrix A:
  [[1 1 0]
   [0 1 1]]</p>
  
  <p>Steps I took:</p>
  
  <p>Given Matrix A:</p>
  
  <pre><code>1. Choose a column, c, with the least number of 1's. I choose: column 1
  
  2. Choose a row, r, that contains to a 1 in column c. I choose: row 1
  
  3. Add r to the partial solution.
  
  4. For each column j such that A(r, j) = 1:
  
         For each row i such that A(i, j) = 1:
  
             delete row i
  
         delete column j
  
  5. Matrix A is empty. Algorithm terminates successfully and solution is allegedly: {row 1}.
  </code></pre>
  
  <p>However, this is clearly not the case as row 1 only consists of [1 1 0] and clearly does not cover the 3rd column.</p>
  
  <p>I would assume that the algorithm should at some point reduce the matrix to the point where there is only a single 0 and terminate unsuccessfully.</p>
  
  <p>Could someone please explain this?</p>