A short history of polyomino puzzles
4-minute read
Every piece in Fill the Space is a polyomino: a shape made of equal squares joined edge to edge. Two squares make a domino, three a tromino, four a tetromino, five a pentomino. They’re simple enough for a child to draw and deep enough that mathematicians are still counting them. Here’s a short history of the shapes in your tray.
Before they had a name
Puzzles built from squares are old. One early landmark is The Canterbury Puzzles by the English puzzle maker Henry Ernest Dudeney, published in 1907. Its “Broken Chessboard” asks you to assemble a chessboard from thirteen pieces: the twelve different five-square shapes and one two-by-two square. The idea of using every distinct shape of a given size exactly once became one of the great themes of the subject.
Golomb gives them a name
The word polyomino came from the American mathematician Solomon W. Golomb. He introduced it in a 1953 talk to the Harvard Mathematics Club, and set the subject out in a 1954 article, “Checker Boards and Polyominoes”, in The American Mathematical Monthly. He extended the pattern of “domino” to any number of squares, and he showed how simple arguments, like shading a board as a checkerboard, can prove that a shape can or can’t be tiled. His book Polyominoes followed in 1965.
The checkerboard argument is still one of the most useful tools for players. There’s a guide to using it in Fill the Space.
Gardner takes them to everyone
Polyominoes reached a wide audience through Martin Gardner, whose “Mathematical Games” column in Scientific American took them up in 1957. Pentominoes in particular became a craze: there are twelve of them, they hold 60 squares between them, and they can be packed into rectangles of 6 by 10, 5 by 12, 4 by 15 and 3 by 20. In 1960 a computer search by C. B. and Jenifer Haselgrove found that the six-by-ten rectangle alone can be filled in 2,339 different ways, not counting rotations and reflections of the whole board.
Tetris
The most famous polyomino game arrived in 1984. Alexey Pajitnov, working at the Dorodnitsyn Computing Centre of the Soviet Academy of Sciences in Moscow, wrote Tetris, named from “tetra”, for the four squares in each piece, and tennis, his favourite sport. Its pieces are the seven tetrominoes you can make when turning is allowed but flipping isn’t, so an L and a J are different pieces. Tetris is about speed and gravity. Fill the Space keeps the shapes and leaves out the gravity: nothing falls, nothing speeds up, and what counts most is where you put each piece.
Free, one-sided and fixed
How many polyominoes are there? It depends on what counts as “the same” shape, and there are three common answers:
| Squares | Free (turn and flip) | One-sided (turn only) | Fixed (no turning) |
|---|---|---|---|
| 3 | 2 | 2 | 6 |
| 4 | 5 | 7 | 19 |
| 5 | 12 | 18 | 63 |
Tetris uses the one-sided tetrominoes. Fill the Space uses fixed polyominoes: pieces can only slide, so a T pointing up and a T pointing down are different pieces. Nobody has found a formula that gives the number of polyominoes of any size. They have been counted by computer, size by size, far beyond anything you’d want in a tray.
Exact cover
Filling a shape with a set of pieces, with no gaps and no overlaps, is what mathematicians call an exact cover problem. In 2000, the computer scientist Donald Knuth published “Dancing Links”, a now-classic method for searching exact cover problems, with pentomino puzzles as one of its examples. Every Fill the Space room is a small exact cover problem with a guaranteed answer. The hints and solution counts on the archive pages come from the same kind of search.
Where Fill the Space fits
Fill the Space borrows from all of this. From Dudeney and Golomb it takes the pleasure of fitting shapes exactly. From Tetris it takes the familiar pieces. It leaves out the falling and the rush, and it keeps the rule that pieces don’t turn, because that rule makes each room something you can reason your way through. Four rooms a day, every piece used, nothing left over.
To put the history to work, start with how to solve a room.
That’s the last guide. See them all.