13,291,084 members (68,480 online)
alternative version

#### Stats

88.8K views
34 bookmarked
Posted 20 Oct 2011

# Solve the Pentomino puzzle with C++ and dancing links

, 2 Dec 2011
 Rate this:
Program to find all the solutions to a Pentomino puzzle.

## Introduction

When ordering old files, I found a lot of code. This is a program to find the solution to a jigsaw puzzle. I don't remember why I wrote it, it was a challenge I found interesting.

## The Problem

There is a jigsaw. You have to put all the pieces in a square rectangle. You can flip and rotate pieces.

## The solution

I wrote it first with an array of boards with pieces on it. Each piece that did fit without holes would be a new board. It was slow and it did use a lot of resources (for allocating arrays).

So I rewrote it in a way that the algorithm goes forward and backwards on the same board, adding and removing pieces.

The idea is pretty simple. You put the first piece (iterating an array of pieces). If it is OK, then you get to put the next one. If you can't, then you go backwards and remove it from the array. The only thing you have to remember is the order of the pieces so that when you go backwards, you can continue with the next piece.

There are three classes for handling the pieces:

• `CPiezas`: The class responsible for loading all the pieces from a file in XML format. The XML format is simple, there is a root node `PIEZAS` with child nodes `PIEZA`.
• Each `PIEZA` node has these attributes:

• `Nombre`: Name of the piece.
• `Ancho`: Width of the piece.
• `Alto`: Height of the piece.
• `Contenido`: Content. Using 0 for void and 1 for piece content, it represents the piece using width and height. For example, Ancho="4" Alto="2" Contenido="11110010" should be read:
• ```1111
0010```

The class `CPiezas` also has an array (map) with all the pieces (`CPiezaInfo`) that it loads from the XML.

• `CPiezaInfo`: Contains information about the pieces and all its possible rotations and inversions. It contains a vector of `CPieza`. Each `CPieza` of the vector represents a possible rotation or inversion of the piece.
• `CPieza`: Each item of this class represents a piece in a rotated or inverted state. It has the colour and the methods for rotation and inversion. As there are 8 possible combinations of rotation and inversion (4 for rotation and 2 for inversion), the ID holds both the piece ID and the state.
• For example, the ID 26 represents the piece ID:2, State:6. All possible states are defined in an enum `TipoPieza`. This class inherits from `CFillRectangle` which contains the general rectangle operations.

## The code - Rectangle operations

The class `CFillRectangle` is responsible for marking squares inside a rectangle. It was written with efficiency in mind (considering large vectors of boards). So, it uses binary logic to assign the squares. So, in a byte, 8 squares are used and marked as 1 or 0. This class is used for both boards and pieces.

## The code - The board

The class `CBoard` which inherits from `CFillRectangle` represents the place to put the pieces. The variables are:

• `Fila`: Represents the current row to put a piece.
• `Columna`: Represents the current column to put a piece.
• `nodos`: An array of 12 items of type `CNodo`. Each `CNodo` represents a piece in a location of the board. Each `CNodo` also has the index variable to move to the next piece in an array of pieces.
• `inodo`: Represents the current position being processed in the array `nodos` (0-11).
• `nodeseval`: A counter for each piece that is being tried.
• `mappiezas`: A map that links each piece ID with the `CPieza` object.
• `vecpiezas`: A vector to iterate pieces with the index variable of `CNodo`.
• `mappiezasdisp`: A map that represents if the piece is in the board or not (the piece is available or not).
• `piezas`: A pointer to the pieces.

The methods are:

• `TieneHuecos`: Gets if the board has any unoccupied cells. This method is not used and could be removed.
• `MarcarCasillas`: Given a piece (a parameter of type `CPieza`), it marks or unmarks all cells of the board that correspond to the piece in the current location of the board (variables `Fila` and `Columna`).
• `AsignarProxColumnaFila`: It assigns the board variables `Fila` and `Columna` to the first unmarked cell of the board from bottom to top, left to right.
• `CorrespondePieza`: Checks if placing a piece in the current board cell (`Fila` and `Columna`) can be done.
• `InitPiezasDisp`: Loads all the piece arrays (`vecpiezas`, `mappiezasdisp`, `mappiezas`).
• `Init`: Loads the 12 nodes of `nodos` and sets them to null.
• `MarcarPiezaInfo`: Given a piece, it marks or unmarks all of them in the map (in all positions) as available or not.
• `GetIndexFirstAvailable`: Gets the next piece in the vector `vecpiezas` that is available (checks `mappiezasdisp`).

## The code - The solver

The class `CPuzzleSolver` is where the algorithm takes place. The variable "`soluciones`" is used to store solutions (array of 12 `CNodo`). The variable `solman` is an object of type `CSolutionMan` used to filter duplicated solutions. The method `SolvePuzzle` inits the board and the arrays, and executes the method `HacerMovida` until user cancels or the algorithm finishes. A description of `HacerMovida`:

```if (Current piece index in current node is last + 1, go backwards)
{
Put null into current node.
Move backwards (go to the node before, index of nodes -1)

if (There are no more nodes before)
End Process.
Position the board in the coordinates of the current node.

Remove the piece of the current node from
the board (we need to move to the next piece).
Add the piece of current node to the list of available pieces.

Move to the next available piece in the current node.
}
else
{
if (Add the piece of the current node to the board)
{
Add the piece to the board (mark cells).
Remove the piece from the list of available pieces.
Assign the current node the coordinates of the board.
if (not find next free cell in the board, the board is full, solution)
{
Remove piece from board
Add piece to list of available pieces
Move to the next available piece in the current node.
}
else
{
Move to the next node (which is null).
Assign the node the first available piece from the list.
}
}
else
Move to the next available piece in the current node.
}```

## The code - Deleting duplicates

The class `CSolutionMan` uses an array of type `CSolPuntos` to delete duplicated solutions. The class `CSolPuntos`, unlike the board (`CFillRectangle`), contains an ID of piece instead of a boolean (1 or 0).

The idea is that, to check for duplicates, it is way easier to rotate or invert points in a board than pieces.

The algorithm is:

• Iterate solutions (i).
• For each solution, rotate, invert, rotate, and invert (result: 3 new solutions).
• Compare each remaining solution (n-i sols) to the three solutions of the previous step.
• If equal, remove solution.

## Algorithm X

There is a faster algorithm to solve this problem called Algorithm X developed by Donald Knuth. The most efficient implementation of this algorithm is dancing links.

The problem this algorithm resolves is "Exact cover". Basically, what it does is, given a matrix of 1s and 0s, find all rows that cover exactly once all columns with 1s:

 A B C D P 0 1 0 1 Q 1 0 0 0 R 1 1 0 0 S 0 0 1 0 T 0 0 1 1

In that example, the rows P, Q, and S and the rows R and T are the solutions for the given matrix. It seems simple, but for a larger matrix, finding all the solutions takes time.

The algorithm X consist of 4 steps that are executed until the matrix is null (a solution is found) or a column has all 0s (unsuccessful). Each iteration reduces the matrix size.

• Find the column with fewer 1s (if there is more than one, choose the first). For example, column A.
• For that column, choose a row where the intersection of the row and column is 1. Remember the row. For example, Row Q.
• For that row, choose the columns where the row value is 1 and for those columns, remove all rows where the value of the column is 1 (in this example, the only 1 of row Q is in column A, so remove rows Q and R).
• Remove the columns selected previously (A in this example).

After executing the steps, the matrix has column A removed and rows Q and R removed:

 B C D P 1 0 1 S 0 1 0 T 0 1 1

Next we choose column B and from that column, Row P. We remember that row. From row P, we select columns B and D (where row P value is 1). Columns B and D have 1s in row T and P (of course). So, rows P and T go, and so columns B and D:

 C S 1

Here we select column C (we have little choice) and select Row S. Row S and column C go and we end with an empty matrix (success). The selected rows are Q, P, S. This is one solution.

To continue, we select the next 1 row of the column with fewer 1s (column A) in the original matrix. That row is Row R. Row R has 1s in columns A and B, so we select those columns. Those columns have 1s in rows P, Q, and R. So, rows P, Q, and R go, and so columns A and B:

 C D S 1 0 T 1 1

Now the column with fewer 1s is column D. The first row with 1 is T. So we select Row T. Row T has 1s in columns C and D, which have 1s in all rows, so we end with an empty matrix again (success). The solution are rows R and T.

## Implementation of Algorithm X, dancing links

For a large matrix, removing and restoring rows and columns are time expensive operations. Besides, in most problems, these matrixes are "sparse" which means that there are a lot of 0s and a few 1s. So, it is a good idea to only represent the 1s.

First we introduce the concept of double linked circular list:

Each item has two pointers, one to the left and one to the right. The final item points to the first.

To iterate the list moving to the right, starting with `Item2`:

`For (i = Item1.Right; i != Item1.Right; i = i.Right)`

To remove an item (`Item2` for example) using only `Item2`:

`Item2.Right.Left = Item2.Left`

Here, we point `Item3.Left` (`Item2.Right.Left`) to `Item2.Left` (`Item1`) so that it "skips" `Item2`. `Item2.Right` is `Item3`. `Item2.Left` is `Item1`.

`Item2.Left.Right = Item2.Right`

Here, we point `Item1.Left` (`Item2.Left.Right`) to `Item2.Right` (`Item3`) so that it "skips" `Item2`. `Item2.Left` is `Item1`. `Item2.Right` is `Item3`.

To add an item (`Item23` for example) at the right of `Item2` (between `Item2` and `Item3`) using only `Item2`:

```Item2.Right.Left = Item23
Item2.Right = Item23```

Here we point `Item3.Left` to `Item23` and `Item2.Right` to `Item23`. `Item2.Right` is `Item3`.

```Item23.Right = Item2.Right
Item23.Left = Item2```

Here we point `Item23.Right` to `Item3` (`Item2.Right`) and `Item23.Left` to `Item2`.

Now, the problem of algorithm X can be represented with each 1 as a node and circular double links lists interlaced in a matrix with nodes that point up, down, left, and right. Representing the sample problem:

In this image, the node at Row S is alone in the row, so it points both left and right to itself. Each node also has a pointer to its column header (in the algorithm).

## Representing the pentominoes problem as exact cover

We can represent the board as 60 "cells" to be filled. Each piece with its orientation, at a certain position in the board "covers" certain "cells". For example, the T piece, starting in the position 1 covers cells 1, 2, 3, 8, and 14.

So, we can make a grid with 60 columns, and represent every position (in the board) of each piece at all orientations. It is a pretty big matrix. But each piece can only be put in the board once, so we need to make sure it doesn't repeat. To do that, we add 12 columns (one for each piece) and we put a 1 in the corresponding piece. If the T piece is piece 3, the representation of the three boards filled with T piece starting at 1, 2, and 3 would be:

Of course, there are 60 board columns and I only represented 17, the rest of the columns have 0 values for this example. For this problem, it is a sparse matrix. Of 72 values for each row, only 6 will have 1 value (8%). The matrix has 1864 rows if we only consider a piece with 2 of 8 orientations to remove trivial solutions.

## Trivial results

To avoid rotated or inverted solutions, you can use only 2 orientations out of a piece which allows 8 orientations.

The two most important methods are the cover and uncover (or `remove` and `restore`). Given a col, they remove the col and all the rows where the col has an item. Visually, it's like removing a TV antenna:

```void CDLinks::Remove(CColumnHeader* hcol)
{
hcol->right->left = hcol->left;
hcol->left->right = hcol->right;

//Iterate all the nodes in the column, going down.
for (CNode* row = hcol->down; row != hcol; row = row->down)
{
//Remove the row, for each node, disconect vertically (zipper).
for (CNode* col = row->right; col != row; col = col->right)
{
//Remove node vertically
col->down->up = col->up;
col->up->down = col->down;

}
}
}

{
//Iterate all the nodes in the column, going down.
for (CNode* row = hcol->up; row != hcol; row = row->up)
{
for (CNode* col = row->left; col != row; col = col->left)
{

col->down->up = col;
col->up->down = col;
}
}
//Restore the heather
hcol->right->left = hcol;
hcol->left->right = hcol;
}```

## Results

In my laptop (slow), in 11 min 13 seconds, the program found 9356 solutions. After deleting duplicates, 2339 solutions remained (which is logically correct, 9356/4=2339). It checks for 288 949 150 nodes (try to put pieces in the board).

Using dancing links and avoiding trivial solutions, the program takes 14 seconds to find all the solutions.

This shows that dancing links is a much faster algorithm to calculate solutions for this kind of problems.

To improve speed, all the nodes are stored in a vector, with the `reserve()` method. That way, there is only one allocation instead of one for each node being created.

## Libraries

I migrated the solution to VS 2010. It uses MFC. The code compiles to both 32 and 64 bits.

## Share

 Software Developer Argentina
System developer from Argentina.

Programmed in VB 5,6,.NET, C#, Java, PL-SQL, Transac-SQL, C, C++ and even some "calculator" language.

Love to build small, useful applications.
Usually building big and complicated apps based on solid, reliable components.

## You may also be interested in...

 First Prev Next
 Adapt the algorithm? _Pepe_10-Sep-17 8:35 _Pepe_ 10-Sep-17 8:35
 CTreePuzzle.h Member 379509515-Nov-14 22:28 Member 3795095 15-Nov-14 22:28
 Solution matrix Rezo Mesarkishvili6-Jun-13 2:23 Rezo Mesarkishvili 6-Jun-13 2:23
 Re: Solution matrix ErnestoNet6-Jun-13 15:40 ErnestoNet 6-Jun-13 15:40
 Re: Solution matrix Rezo Mesarkishvili8-Jun-13 10:15 Rezo Mesarkishvili 8-Jun-13 10:15
 Exact Cover Matrix Question Member 29046814-May-13 7:37 Member 2904681 4-May-13 7:37
 Re: Exact Cover Matrix Question ErnestoNet6-May-13 12:03 ErnestoNet 6-May-13 12:03
 Re: Exact Cover Matrix Question ErnestoNet6-May-13 12:12 ErnestoNet 6-May-13 12:12
 Very good algorithm. i have a question Member 382646523-Apr-12 4:52 Member 3826465 23-Apr-12 4:52
 Re: Very good algorithm. i have a question ErnestoNet24-Apr-12 14:10 ErnestoNet 24-Apr-12 14:10
 Re: Very good algorithm. i have a question Member 353038624-Apr-12 23:30 Member 3530386 24-Apr-12 23:30
 Re: Very good algorithm. i have a question Member 382646525-Apr-12 0:52 Member 3826465 25-Apr-12 0:52
 Re: Very good algorithm. i have a question Member 353038631-May-12 22:23 Member 3530386 31-May-12 22:23
 My vote of 5 programming nerd8-Nov-11 7:24 programming nerd 8-Nov-11 7:24
 Re: My vote of 5 ErnestoNet23-Dec-11 12:52 ErnestoNet 23-Dec-11 12:52
 My vote of 5 fredatcodeproject21-Oct-11 2:59 fredatcodeproject 21-Oct-11 2:59
 Re: My vote of 5 ErnestoNet23-Dec-11 12:55 ErnestoNet 23-Dec-11 12:55
 Thanks. I have a lot of projects, but with a lot of dependencies that can´t be included in articles. I´ll try to post and improve articles. it´s the journey, not the destination that matters
 Excellent Pascal Ganaye21-Oct-11 1:44 Pascal Ganaye 21-Oct-11 1:44
 Re: Excellent ErnestoNet21-Oct-11 2:40 ErnestoNet 21-Oct-11 2:40
 Last Visit: 31-Dec-99 19:00     Last Update: 12-Dec-17 11:09 Refresh 1