Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

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

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; for example, use it to solve the problem above.

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 below; note that the white squares are holes, and of course not part of the problem

our small example

imagine you want to fill the 6 colored squares (again the white space is not part of the problem) using 2 identical pieces - like shown on the right; obviously there are exactly 2 solutions, the one shown, and the one where both pieces are swapped.

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:

  • the first 2 columns (we have 2 pieces) correspond to the piece number
    we set exactly one 1 to indicate which piece we’re talking about
    so for example the first 7 rows correspond to the 7 positions where we can place piece#0

  • because there are 6 squares to be filled, the next 6 columns correspond to the slots that the piece in that position would occupy (1 means the slot is filled, 0 means it is not)
    and since the 2 pieces are identical, the 7 last rows carry the same information, but for piece#1

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

  • this is about piece#0 (hence col0=1 and col1=0)

  • and that piece may be placed on the board in the following position


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 write something like

# returns immediately
solutions = covers_bool(problem)

# gets the 1st solution - may take a bit of time
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; be careful to be able to handle obstacles if you go for nd-arrays

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 that you need to pass to the library of your choice

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 ?

a GUI ?

if time permits, you may find it useful to build a small GUI that let people

to this end, you may find the flet library useful for that - see https://flet.dev/docs/quickstart/ - or any other library that you feel comfortable with; pygame, arcade, may come in handy as well.

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