Pentomino Solving Algorithm Using Algorithm X for Exact Coverage Problems
I've been working on this for a few days now and finally decided to post my problem here. I will explain to you in detail what I am doing and how. Before continuing. I went through Wikipedia and 20 more sites that explain this issue, but it didn't work for me.
One of the more helpful sites :( Kanoodle ) but when it comes to my problem the explanation is very poor.
Problem: how many ways to span a 5xn rectangle with W-, I- and L-Pentominos. You are allowed to flip and rotate them. What can you ask the Pentominos? The pentominos consists of 5 squares, which together form a shape. For example, 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 box, I shortened my task and started thinking about all the possible ways to fill in the "W" in a 5x3 box. Like this.
The next step I thought of was a matrix that was similar to Knuth's DLX algorithm, and I came up with this. A green line between yellow and orange means you could put both together to have a different working solution. The following text describes this green line.
I noticed that if I take a row and check if any other row below or above that row has 1 in the same column, I had the right 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.
Again, I failed to implement this.
So here's my question: how would you implement this problem in JAVA. Is my approach good? Could you work with my ideas? If so, how would you proceed, if not, tell me where my thoughts are not working?
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)
{
}
}
source to share
To find all the possible ways to place the Pentomino inside a rectangle, follow these steps:
- Find the length and with the pentomino, as if you were drawing a rectangle with its size.
- Now find how many times this rectangle will fit into the large rectangle. For example, you have a 3x5 rectangle and a smaller rectangle for the W-shape and 3x3. 5-3 + 1 = 3. There are 3 possible ways to fit a W into a 3x5 square (no click or rotation). If the rectangle was 5x5 and we are still using the same pentomino, then there would be 9 possible different ways to position the shape without flipping or rotating. Use the formula: x = a - b + 1; y = c - d + 1; xy = z (Possible paths without rotation). a = length of the large rectangle; b = the length of the small rectangle; c = width of the large rectangle; d = the width of the small rectangle.
- Since we are dealing with rectangles, you will need to flip the shape and rotate it, and every time you do this, do the same calculation in step 3 and add it to the total.
- Step 3 caused another problem. What to do if the shape is upside down or rotated is the same as the previous one. To calculate this, take a shape in x and y format so that the w-shape is: {(0,0), (1,0), (1,1), (2,1), (2,2)}, if the start was in the upper left corner. Take these coordinates and rotate them. (0, 0) → (0, 3) for the first point rotating 90 degrees counterclockwise. To rotate any points, the first 90 degrees do: (y, w - x - 1) w = the width of the rectangle. To rotate the next 90 degrees, do: (y, h - x - 1) h = the height of the rectangle. To rotate the last time, repeat (y, w - x - 1). Remember that every time you rotate the width and height you need to swap the positions because it is a rectangle and not always a square.If any of these rotated shapes have the same coordinates (they don't have to be in the same order), then that particular rotation will not be verified with step 2.
- Finally, you have to take care of the reflection / flipping. It's easier than spinning. For horizontal flipping (w - x - 1, y); w = shape width.
Here are some pictures of the work I used to figure it out and test it out:
Search for opportunities:
Rotation (squares and rectangles):
Serve:
source to share