Pentomino solving algorithm using Algorithm X for exact cover problems

Question

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 that has been given to me.

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

    }

}

Answer 1

While in the standard pentomino exact cover problem, each piece must be used exactly once ; Knuth in https://arxiv.org/pdf/cs/0011047.pdf mentions (for a grid of 8x8 minus 4 cells at the center, which would be true for a standard grid of 60 cells):

[...] Imagine a matrix that has 72 columns, one for each of the 12 pentominoes and one for each of the 60 cells [...].

... and this is because we're looking at an exact cover of 60 positions in the grid space, plus 12 positions in the pentomino name space.

But in your problem, the same piece may be used several times. In this case, you don't need to add "columns" to express the need of covering the universe of pentominoes: in your 5x4 grid configuration, you need 20 columns. So you don't need the extra W column full of 1s you showed in your drawing (or the problem is infeasible). A cursory look at your other columns didn't shock. But you should generate this stuff programmatically.

Then, given your 5x4 grid configuration, you will need to have a number of rows corresponding to the number of fixed pentomino variants at their possible positions (which typically comes up to 376 rows, or less if you want to consider symmetries of the board). I set my row names to {pentomino-name}/{pentomino-variant}@{pentomino-origin-x},{pentomino-origin-y}.

The code you provide is missing construction of the matrix of 1s, the 2D array of Nodes and its toroidal links according to the matrix of 1s, the column headers, and a way of printing your solutions.

Answer 2

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: