Agfdhyk

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.

Dancing Links - Wikipedia

Knuth's algorithm x.

One of the more useful sites:(Kanoodle) but when it comes to my problem the explanation is very poor.

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.

   | 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 |

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.

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.

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.

Yet again i had trouble implementing this.

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?

Here is the code i wrote sofar.

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 & counts solutions

    {

        if(h.R == h)                            // if empty: count & 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 << 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? << 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 << 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)

    {



    }



}

To find all the possible ways a Pentomino can be put inside a rectangle you can do the following steps:

1. Find the length and with of the pentomino as if you were to draw a rectangle to its size.


2. Now find how many times that rectangle will fit in the bigger rectangle. For example, you have a 3x5 rectangle and the smaller rectangle is for the W shape and it is 3x3. 5-3+1 = 3. There are 3 possible ways to fit the W shape in a 3x5 square (Without flipping or rotating). If the rectangle was 5x5 and we are still using the same pentomino then there would be 9 possible different ways to put the shape without flipping or rotating. Use the formula: x = a - b + 1; y = c - d + 1; xy = z (Possible ways with no rotating). a = length of big rectangle; b = length of small rectangle; c = width of big rectangle; d = width of small rectangle.


3. Since we are dealing with rectangles you will need to flip the shape and rotate it and each time you do so do the same calculation in step 3 and add it to the total.


4. Step 3 brought up another problem. What if the shape flipped or rotated is the same as a previous shape. To calculate this take the shape in the format of x and y so the w shape would be: {(0,0), (1,0), (1,1), (2,1), (2,2)} if the origin was in the top left. Take these coordinates and rotate them. (0, 0) -> (0, 3) for the first point rotating 90 degrees counter clockwise. To rotate any points the first 90 degrees do: (y, w - x - 1) w = width of rectangle. To rotate the next 90 degrees do: (y, h - x - 1) h = height of rectangle. To rotate the final time repeat the (y, w - x - 1). Remember that every time you rotate the width and height must be swapped because it is a rectangle and not always a square. If any of these rotated figures have the same coordinates (They don't have to be in the same order), then that specific rotation will not be checked with step 2.


5. Finally you must take care of reflecting / flipping. This is easier than rotating. To flip horizontally simply do (w - x - 1, y); w = width of shape.

Here are some pictures of work I used to figure this out and test it:

Finding possibilities:

Rotating (Squares and rectangles):

Flipping: