title: Exact cover using Dancing Links
body: <p>After going through <a href="https://stackoverflow.com/questions/1518335/the-dancing-links-algorithm-an-explanation-that-is-less-explanatory-but-more-o">this question</a> I tried to implement Dancing Links to solve only the exact cover problem, following is the code taken from <a href="http://uaa.wtf.im/?page_id=27" rel="nofollow noreferrer">here</a> and modified (It is Column-Row structure, I needed Row-Column strucuture). It works fine except that it never reaches the successful termination block in the <code>Search</code> function, I tried to trace and found that this</p>
  
  <pre><code>RowNode = Column-&gt;Down ; RowNode!=Column ; RowNode = RowNode-&gt;Down
  </code></pre>
  
  <p>is causing it. Example : for the following matrix</p>
  
  <pre><code>1 2 3 4
  1 1 x x
  x 1 1 x
  x x 1 1
  </code></pre>
  
  <p>my code fails to <code>cover</code> the last column with <code>Header=4</code></p>
  
  <p>How can I overcome this? Here is the complete code</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;vector&gt;
  #include &lt;cstdio&gt;
  #include &lt;stdbool.h&gt;
  
  #define MAX_ROW 50L
  #define MAX_COL 100L
  
  using namespace std;
  
  struct str_node {
      struct str_node * Header;
      struct str_node * Left;
      struct str_node * Right;
      struct str_node * Up;
      struct str_node * Down;
      int HeaderID,RowIndex,ColIndex;
  };
  
  
  int nCol;
  int nRow;
  struct str_node Matrix[MAX_ROW][MAX_COL];
  vector&lt;struct str_node*&gt;ResultRow;
  struct str_node Root;
  struct str_node *RootNode = &amp;Root;
  bool Data[MAX_ROW][MAX_COL];
  int maxResult;
  
  //functions to get the neighbours (are circular)
  inline int dataLeft(int i) { return (i-1 &lt; 0) ? nCol-1 : i-1 ; }
  inline int dataRight(int i) { return (i+1) % nCol ; }
  inline int dataUp(int i) { return (i-1 &lt; 0) ? nRow-1 : i-1 ; }
  inline int dataDown(int i) { return (i+1) % nRow ; }
  
  void CreateToroidalMatrix(void) {
  
      int a,b, i, j;
  
      for(a = 0 ; a &lt;= nRow ; a++) {
  
          for(b=0 ; b &lt; nCol ; b++) {
  
              if(Data[a][b]) {
  
                  Matrix[a][b].RowIndex = a;
                  Matrix[a][b].ColIndex = b;
  
                  // Left pointer
                  i = a; j = b; do {j = dataLeft(j); } while (!Data[i][j]);
                  Matrix[a][b].Left = &amp;Matrix[i][j];
  
                  // Right pointer
                  i = a; j = b; do {j = dataRight(j); } while (!Data[i][j]);
                  Matrix[a][b].Right = &amp;Matrix[i][j];
  
                  // Up pointer
                  i = a; j = b; do {i = dataUp(i); } while (!Data[i][j]);
                  Matrix[a][b].Up = &amp;Matrix[i][j];
  
                  // Down pointer
                  i = a; j = b; do {i = dataDown(i); } while (!Data[i][j]);
                  Matrix[a][b].Down = &amp;Matrix[i][j];
  
                  //Head pointer
                  Matrix[a][b].Header = &amp;Matrix[0][b];
                  Matrix[a][b].HeaderID = b+1;
  
              }
          }
      }
  
      //Initialize root
      RootNode-&gt;Right = &amp;Matrix[0][0];
      RootNode-&gt;Left = &amp;Matrix[0][nCol-1];
      Matrix[0][0].Left = RootNode;
      Matrix[0][nCol-1].Right = RootNode;
  }
  
  void Cover(struct str_node *ColNode){
  
      cout&lt;&lt;"Covering header node "&lt;&lt;ColNode-&gt;HeaderID&lt;&lt;'\n';
  
      struct str_node *RowNode, *RightNode;
  
      ColNode-&gt;Right-&gt;Left = ColNode-&gt;Left;
      ColNode-&gt;Left-&gt;Right = ColNode-&gt;Right;
  
      for(RowNode = ColNode-&gt;Down ; RowNode!=ColNode ; RowNode = RowNode-&gt;Down) {
          for(RightNode = RowNode-&gt;Right ; RightNode!=RowNode ; RightNode = RightNode-&gt;Right) {
              RightNode-&gt;Up-&gt;Down = RightNode-&gt;Down;
              RightNode-&gt;Down-&gt;Up = RightNode-&gt;Up;
          }
      }
  }
  
  void UnCover(struct str_node *ColNode) {
      //uncover the covered nodes to find a different solution
      struct str_node *RowNode, *LeftNode;
  
      for(RowNode = ColNode-&gt;Up; RowNode!=ColNode; RowNode = RowNode-&gt;Up) {
          for(LeftNode = RowNode-&gt;Left; LeftNode!=RowNode; LeftNode = LeftNode-&gt;Left) {
              LeftNode-&gt;Up-&gt;Down = LeftNode;
              LeftNode-&gt;Down-&gt;Up = LeftNode;
          }
      }
      ColNode-&gt;Right-&gt;Left = ColNode;
      ColNode-&gt;Left-&gt;Right = ColNode;
  }
  
  void Search(int k){
  
      //all columns covered
  
      if( RootNode-&gt;Right == RootNode){
          cout&lt;&lt;"found\n";
          if(maxResult &lt; k)
              maxResult = k;
          return;
      }
  
      //if not covered
      else{
  
          struct str_node *Column = RootNode-&gt;Right;
          struct str_node *RowNode;
          struct str_node *RightNode;
          struct str_node *LeftNode;
  
          Cover(Column);
  
          for( RowNode = Column-&gt;Down ; RowNode!=Column ; RowNode = RowNode-&gt;Down){
  
              ResultRow.push_back(RowNode);
  
              for(RightNode = RowNode-&gt;Right; RightNode!=RowNode; RightNode = RightNode-&gt;Right)
                  Cover(RightNode-&gt;Header);
  
              Search(k+1);
              RowNode = ResultRow.back();
              ResultRow.pop_back();
              Column = RowNode-&gt;Header;
  
              for(LeftNode = RowNode-&gt;Left; LeftNode!=RowNode; LeftNode = LeftNode-&gt;Left)
                  UnCover(LeftNode-&gt;Header);
          }
          UnCover(Column);
      }
  }
  
  void GetData(void){
      int pos,k;
      scanf("%d%d",&amp;nCol, &amp;nRow);
  
      for(int i=0 ; i&lt;nCol ; i++)
          Data[0][i] = true;
  
      for(int i=1 ; i&lt;=nRow ; i++){
          scanf("%d",&amp;k);
          for(int j=0 ; j&lt;k ; j++){
              scanf("%d",&amp;pos);
              Data[i][pos-1] = true;
          }
      }
      CreateToroidalMatrix();
  }
  
  int main(void){
      GetData();
      Search(0); // from level 0
      printf("%d\n",maxResult+1);
      return 0;
  }
  </code></pre>