Pentomino Puzzle Solver

A pentomino is five equal squares joined edge to edge. There are 12 of them once you agree that a shape turned or flipped over is still the same shape, and together they cover 60 squares. Sixty is 6 times 10, and that small coincidence has kept people busy for a lifetime.

The puzzle is easy to state and hard to finish. Put all twelve pieces into a 6 by 10 tray with no gaps and no overlaps. Most people find one answer after a long evening. There are 2,339 of them, and the story of how that number was reached is a short history of how to search carefully.

The shapes and the man who named them

Solomon Golomb did not invent the idea of squares stuck together. The first pentomino problem appeared in 1907, in a puzzle book by Henry Dudeney. What Golomb did was give the family a name and a method. He spoke about polyominoes to the Harvard Mathematics Club in 1953, published his first paper on them a year later, and treated what had been scattered puzzles as one subject with rules of its own.

The name is a joke that stuck. A domino is two squares, so Golomb read the word as if its first letter meant two and built the rest from it: tromino, tetromino, pentomino, and polyomino for the whole family. A Scientific American column by Martin Gardner in 1957 carried the idea to the public, and Golomb later said it brought him a steady stream of letters from every kind of reader. His book on the subject came out in a revised second edition in 1994.

He also named the twelve pieces after the letters they resemble: F, I, L, N, P, T, U, V, W, X, Y and Z. Counting them depends on what you allow. If a piece may be turned and flipped there are 12. If it may be turned but not flipped, six of them split into left and right hands and there are 18. If every position on the grid counts separately there are 63, because eight positions each for F, L, N, P and Y, four each for T, U, V, W and Z, two for I and one for X add up to exactly that.

The same counting works for every size. One square, one domino, two trominoes, five tetrominoes, twelve pentominoes, 35 hexominoes: 1, 1, 2, 5, 12, 35. The honest way to get each term is to build the shapes and throw out the repeats, which a program does in a blink for six squares and which has been pushed, with far more effort, to shapes of dozens of squares.

Four rectangles and a chessboard

Sixty squares make four sensible rectangles. The 6 by 10 has 2,339 solutions, the 5 by 12 has 1,010, the 4 by 15 has 368, and the 3 by 20 has just 2. Those figures treat a solution and its mirror image or half turn as one. The two answers on the narrowest board are close cousins, since one becomes the other when a block of seven pieces in the middle is turned around as a unit.

The 6 by 10 count belongs to Colin Brian Haselgrove and Jenifer Haselgrove, who computed it in 1960. Two years earlier Dana Scott, then a graduate student at Princeton, had taken on a prettier board: a chessboard with the four center squares removed. His program found 65 solutions, and Knuth calls it one of the first experiments in the kind of programming now known as backtracking.

Scott’s account of his own false start is the instructive part. His first idea was to place the first piece, then the second, and so on. Knuth estimates that this plan would have visited about two trillion positions. Scott dropped it and filled the board square by square instead, which cut the work to roughly nine million.

Not every set of pieces has an answer waiting. The five tetrominoes cover 20 squares, yet they cannot fill a 4 by 5 or a 2 by 10 rectangle. Color the board like a checkerboard: a rectangle with an even number of squares has as many dark as light. Four of the tetrominoes always cover two of each. The T covers three of one color and one of the other, wherever it sits. One T, and the totals can never balance. No search is needed.

One puzzle, one table of ones and zeros

The pentomino puzzle has a second, plainer description. Draw a table with 72 columns: one for each of the 60 cells and one for each of the 12 pieces. Add a row for every way of laying one piece on the board, and mark six columns in it, the five cells it covers and the piece it uses. For the 6 by 10 board that comes to 2,056 rows.

A solution is a choice of rows in which every column is marked exactly once. Every cell is covered, no cell is covered twice, and each piece is used once and only once. This is the exact cover problem, and the point of stating the puzzle this way is that the table no longer knows anything about squares or shapes. A method that solves the table solves every puzzle that can be written as one.

Many can. Sudoku is the best known: the rows are the choices of a digit for a cell, and the columns are the demands that every cell be filled and that every row, column and box hold each digit once. For the ordinary nine by nine grid that is 729 rows and 324 columns. The eight queens puzzle fits too, with a twist, because a diagonal may hold at most one queen rather than exactly one.

Dancing links, in plain words

Knuth’s method for the table is simple to describe. Pick a column. One of the rows marked in it has to be in the answer, so try each in turn. Choosing a row settles all the columns it marks, and it rules out every other row that marks any of them, so remove those columns and those rows and solve the smaller table that is left. If a column ever has no rows, the last choice was wrong: put everything back and try the next row.

The cost is all in “put everything back”. Copying the whole table at every step would work and would be hopeless. The trick that gives the method its name is older than Knuth’s paper; he credits Hitotumatu and Noshita, who used it on the queens puzzle in 1979. Keep each list as a chain in which every item knows its two neighbors. To remove an item, make its neighbors point past it. The removed item still remembers who its neighbors were, so two assignments put it back.

That only works if things return in exactly the reverse order of their leaving, and the search does this naturally, because it undoes its latest choice first. Knuth describes the pointers as performing an exquisitely choreographed dance, which is where the title of his paper comes from. Dancing links now has a part of its own in his reference work on programming, first as a separate fascicle in 2019 and then inside Volume 4B.

Why the most cramped cell goes first

The search is free to pick any column, and the choice matters more than any other detail. Golomb and Leonard Baumert suggested the rule in 1965: always branch where there are the fewest branches. In the table that means the column with the fewest rows left. A cell that only two pieces can still reach is a better question than a cell that twenty can, and a cell that nothing can reach ends the branch on the spot.

The numbers are stark. On Scott’s chessboard, taking columns in fixed order cost 103,005 positions for one of the three cases he split the problem into; taking the tightest column first cost 10,421. On the 6 by 10 rectangle Knuth reports 902,631 nodes with the rule and 28,320,810 without it. Finding the tightest column takes a little time at every step, but he notes that the saving grows much faster with the size of the problem than the cost does.

You can watch this happen. Choose the twelve pentominoes and the 3 by 20 board, leave symmetric copies merged, and count. The table has 72 columns and 1,128 rows, and the first column chosen is not a cell at all. It is the X piece, with only 18 places it can go. The whole search visits 16,293 nodes, finds 2 solutions, and multiplies by 4 to report the 8 arrangements that exist when turns and flips are counted separately.

Counting what is really different

That multiplication hides a real question. A rectangle looks the same after a half turn and after a flip in either direction, so every solution comes in a family of four. Counting all four and dividing would be wasteful. Scott’s cure was to pin one piece down. He noticed that the X can sit in only a few essentially different places on his board, and restricted it to those. Knuth did the same on the 6 by 10, keeping the X in one quarter.

A different piece can do the job more simply. Take one with no symmetry of its own, such as the F, and allow it only one position from each family of four that the board’s symmetries turn into each other. No solution can then be its own mirror image, because the F would have to be, so each family is counted once. On the chessboard with its center removed the families have eight members: 65 times 8 is 520.

None of this makes the general problem easy. Exact cover belongs to the class of problems for which no fast method is known, and Knuth says so in the paper. Dancing links is a careful way of doing an exhaustive job, and a board only a little larger, or a set of eighteen one-sided pieces, can keep it running for a very long time. A count that stops early is not a count. It also says nothing about how a person should solve the puzzle, which remains an evening’s work with twelve pieces and a tray.