Skip to article frontmatterSkip to article content

Licence CC BY-NC-ND, Thierry Parmentelat - (images courtesy of wikipedia)

pentominoes and exact cover

this activity is about solving puzzles like the one pictured on the right, using a standard combinatorial algorithm

the exact cover problem

an example

in a nutshell, the exact cover problem is a standard, very basic mathematical problem; let’s start with an example
you feed the algorithm with a set of vectors that all have the same length, and contain 0 and 1, like e.g.

0:  (1 0 0 1 1 0 1 0)
1:  (1 0 0 0 1 1 0 1)
2:  (1 0 0 0 1 1 1 0)
3:  (1 0 1 0 1 1 0 0)
4:  (1 0 0 0 1 0 1 1)
5:  (1 0 1 1 1 0 0 0)
6:  (1 0 0 0 0 1 1 1)
7:  (0 1 0 1 1 0 1 0)
8:  (0 1 0 0 1 1 0 1)
9:  (0 1 0 0 1 1 1 0)
10: (0 1 1 0 1 1 0 0)
11: (0 1 0 0 1 0 1 1)
12: (0 1 1 1 1 0 0 0)
13: (0 1 0 0 0 1 1 1)

and the goal is to find a subset of the input vectors, such that each column of the input is covered exactly once
(of course there is the accessory question about whether there are several solutions, but let’s not dwelve into that, for now at least..)
so in the above example, there would be 2 solutions, namely

# a solution has exactly one 1 in each column

5:  (1 0 1 1 1 0 0 0)
13: (0 1 0 0 0 1 1 1)

and

6:  (1 0 0 0 0 1 1 1)
12: (0 1 1 1 1 0 0 0)

the algorithm and its implementation in Python

one possible way to solve this problem has been the subject of a famous article by Donald Knuth - one of the fathers of Computer Science - and is known as Knuth’s Algorithm X - interested students can find more details in the links section below.
we’re not going to go into the details of the algorithm either, but rather focus on the application to solving pentominoes (see next section)

let us just outline that

So your first task is to search for one of these packages (xcover seems the most efficient one), install it, and read the basics about how to use it

application to pentominoes

the pentominoes

and now for something completely different...
the pentaminoes are the 12 patterns that can be made of 5 contiguous squares - modulo rotations and symmetry
they have been given names, letters actually:

some standard problems

they can be taken as the pieces of a puzzle, and so the standard problems are to fill shapes with these 12 pieces - of course each piece is to be used exactly once, in any rotation / symmetry

we’ll consider here the following shapes (of course each shape must have an area of 12∗5=6012 * 5 = 60)

as well as this one within a 8x8 square and a hole inside

how to solve such a problem

the trick is to transform the puzzle problem into an exact cover problem
there are many resources on the Internet that explain how to do that - and feel free to use them too
on our end, let’s consider a smaller problem as depicted ; note that the white squares are holes, and of course not part of the problem

our small example

it turns out this problem can be mapped to the sample input quoted above in the introduction, i.e.

0:  (1 0   0 1 1 0 1 0)
1:  (1 0   0 0 1 1 0 1)
2:  (1 0   0 0 1 1 1 0)
3:  (1 0   1 0 1 1 0 0)
4:  (1 0   0 0 1 0 1 1)
5:  (1 0   1 1 1 0 0 0)
6:  (1 0   0 0 0 1 1 1)

7:  (0 1   0 1 1 0 1 0)
8:  (0 1   0 0 1 1 0 1)
9:  (0 1   0 0 1 1 1 0)
10: (0 1   1 0 1 1 0 0)
11: (0 1   0 0 1 0 1 1)
12: (0 1   1 1 1 0 0 0)
13: (0 1   0 0 0 1 1 1)

how is this obtained ?

you will find one line for each possible position of a piece on the board
this line will contain:

and so for example with our small problem, the line 3: means:

X o X
. o o
X . .

which, once you remove the obstacles, and flatten, reads 1 0 1 1 0 0: the right-hand-side of first line

how to read a solution ?

if you pick xcover as a solver engine, it will expose a generator over solutions; this means that you can wrote something like

solutions = covers_bool(problem)
first = next(solutions)
print(first)
-> [5, 13]

which maps to the following rows into the input problem:

5:  (1 0   1 1 1 0 0 0)
13: (0 1   0 0 0 1 1 1)

which we then interpret, the other way around, like so:

quiz

how many columns are you going to need for a real-scale pentaminos problem ?

solution

you have 12 pieces and 60 slots to fill, so you need 72 columns

what to do

model the problem

decide how to represent the board and pieces:

you will find some helper code in pentominos_data.py if you wish to use it
in particular, note the presence of SMALL_BOARD and SMALL_PIECE that correspond to the following solution, and that may turn out useful for debugging your code

rotations and symmetries

for each piece, compute its - possibly up to 8 - variants

compute all possible translations

for each piece (supposed to have been rotated and/or swapped already) compute all the possible locations on the board

prepare the exact_cover input

given a board and a set of pieces, compute the input to covers_bool()

pretty-print a solution

your solver will then compute one solution (if there’s one, of course)
from this solution, your job is to compute a ‘pretty’ view of the solution, something like e.g.

(( 3  3  6  7  7  5  5  5 11 11 11 11)
 ( 3  6  6  6  7  9  5  5 10 11 12 12)
 ( 3  1  6  7  7  9  9 10 10 10 12  8)
 ( 3  1  1  4  4  4  9  9 10 12 12  8)
 ( 1  1  4  4  2  2  2  2  2  8  8  8))

or, in the case where there are ‘obstacles’ on the board, it could be something like this (use 0 for the holes)

(( 2  7  7  6 11 11 11 11)
 ( 2  7  6  6  6 10 11  4)
 ( 2  7  7  6 10 10 10  4)
 ( 2  5  5  0  0 10  4  4)
 ( 2  5  5  0  0  1  4  3)
 ( 8 12  5  1  1  1  9  3)
 ( 8 12 12 12  1  9  9  3)
 ( 8  8  8 12  9  9  3  3))

matplotlib

if time permits, you could also transform this rough numpy solution into a nicer matplotlib drawing - or any other visual library of your choice, like e.g.

# import matplotlib
# matplotlib.pyplot.colormaps()

testing

you should find at least one solution for

what now ?

further applications

you can use exact_cover to solve a whole range of other problems, like for example sudoku - and it’s actually less obvious to do the mapping; if you’re done early you can give these some thought

séries de Taylor
Taylor (3/3) un dashboard
numpy HOWTOs
meshes