title: Pentomino solving algorithm using Algorithm X for exact cover problems
body: <p>i am working on this for several days now and finally decided to post my problem here. I will explain you in detail what i am doing and how.
  Before continuing. I went through Wikipedia and another 20 sites which explain this problem but it didn't help me.</p>
  
  <p><a href="http://en.wikipedia.org/wiki/Dancing_Links" rel="nofollow noreferrer">Dancing Links - Wikipedia</a></p>
  
  <p><a href="http://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X" rel="nofollow noreferrer">Knuth's algorithm x</a>.</p>
  
  <p>One of the more useful sites:(<a href="http://www.ams.org/samplings/feature-column/fcarc-kannodle" rel="nofollow noreferrer">Kanoodle</a>) but when it comes to my problem  the explanation is very poor.</p>
  
  <p>Problem: How many ways are there to cover a rectangle of 5xn with W-, I- and L-Pentominos. You are allowed to flip and rotate them. What are Pentominos you may ask? Pentominos consist of 5 squares wich together build a figure. For example a W-Pentomino.</p>
  
  <pre><code>   | A | B | C
  ---------------
  a  | 1 | 0 | 0 |
  -------------
  b  | 1 | 1 | 0 |    Imagine all the 1s together they build a big "W".
  -------------       If you look at my picture it will be clearer.
  c  | 0 | 1 | 1 |
  </code></pre>
  
  <p>Instead of implementing W-, L- and I-Pentominos in a 5xn field i cut my task and started to think about all possible ways to fill a "W" in a 5x3 field.
  Like this.
  <img src="https://i.stack.imgur.com/Zq7WF.jpg" alt="enter image description here">
  My next step was to think about a Matrix which looked similar to the DLX-Algorithm of Knuth and i came up with this. The green line between yellow and orange means that you could put both together to have another valid solution. My next text describes this green line.
  <img src="https://i.stack.imgur.com/0obLl.jpg" alt="enter image description here"></p>
  
  <p>I noticed that if i take a row and check if any other row under or above this row hasn't a 1 in the same column i had a valid solution. But i didn't know how to implement it. After researching hours and hours i found another way to describe my problem. I took a subset (my W-Pentomino) and defined it like this.
  <img src="https://i.stack.imgur.com/Pthkd.jpg" alt="---picture."></p>
  
  <p>Yet again i had trouble implementing this.</p>
  
  <p>So here is my question: How would you implement this problem in JAVA. Is my approach good? Could you work with my ideas? If yes, how would you go on, if no, would you tell me where are the fails in my thoughts?</p>
  
  <p>Here is the code that has been given to me.</p>
  
  <pre><code>package data;
  
  public class PentominoWILDLX
  {
      static Node h;          // header element
  
      static int cnt;         // count solutions
  
      public PentominoWILDLX()
      {
          h = new Node();     // init header element
          cnt = 0;            // init counter
      }
  
  
      public static void search (int k)           // finds &amp; counts solutions
      {
          if(h.R == h)                            // if empty: count &amp; done
          {
              cnt++; return;                      // choose next column c
          }
          Node c = h.R;                           // remove c from clumns
          cover(c);                               // choose next colun c
          for (Node r=c.D; r!=c; r=r.D)           // forall rows with 1 in c
          {
              for(Node j=r.R; j!=r; j=j.R)        // forall 1-elements in row
              {
                  cover(j.C);                     // remove clumn
              }
              search(k+1);                        // recursion with k+1 &lt;&lt; hier überpfüen ob ich ändern muss
              for (Node j=r.L; j!=r; j=j.L)       // forall 1-elemnts in row
              {
                  uncover(j.C);                   // backtrack . unremove? &lt;&lt; googlen
              }
              uncover(c);                         // unremove f c to coulmns
          }
      }
  
  
  
      public static void cover (Node c)           // remove clumn c
      {
          c.R.L = c.L;                            // remove header
          c.L.R = c.R;                            // from row list
          for (Node i=c.D; i!=c; i=i.D)           // forall rows with 1
          {
              for (Node j=i.R; i!=j; j=j.R)       // forall elem in row
              {
                  j.D.U = j.U;                    // rmove row elemnt
                  j.U.D = j.D;                    // from column list
              }
          }
      }
  
      public static void uncover (Node c)         // undo remove col c
      {
          for (Node i=c.U; i!=c; i=i.U)           // forall rows with 1
          {
              for (Node j=i.L; i!=j; j=j.L)       // for all elem in row
              {
                  j.D.U = j;                      // unremove row ele,
                  j.U.D = j;                      // to lumn list
              }
              c.R.L = c;                          // unremove header
              c.L.R = c;                          // to row list
          }
      } // end of class
  
      class Node                  // represents 1 element or header
      {
          Node C;                 // reference to column-header &lt;&lt; h?,
          Node L;                 // left
          Node R;                 // right
          Node U;                 // reference up
          Node D;                 // down reference down
  
          Node()
          {
              C=L=R=U=D=this;     // 2*double-linked circular list
          }
      }   // end of class
  
      public static void main(String[] args)
      {
  
      }
  
  }
  </code></pre>