PCPlus 294: Learn to solve pentominoes

This article was just a great deal of fun to write. I wanted to talk about Knuth’s DLX algorithm (“Dancing Links”) as a solution to the exact cover problem. I’d already talked about Sudoku (a great demo of DLX) recently as an article in the mag, so there was nothing for it but to go for pentominoes, one of the other examples Knuth gave. And it gave me a great reason to bring out my old pentomino set that I was given as a teenager and futz around with it. Needless to say I’m still just as bad at solving it as I was then.

Here’s a pentomino set, a beautiful wooden hand-crafted one:

Pentominosphoto © 2009 Jeffrey Bary | more info (via: Wylio)

Actually this is an enhanced version: if you look there’s an extra 2×2 block in the top left hand corner so that you can solve putting the twelve 5-square pieces, plus the extra one, into an 8×8 box. In fact, one of Knuth’s examples solves this exact problem, but with the square block in the center.

About 4 years ago I bought my own wooden set in a 6×10 box – it uses 12 different colored hardwoods for the pieces – because I couldn’t find my teenage set. This sized box is the “usual” problem to solve and there are 2339 solutions. And then, of course, the next vacation I took in England at my parents’, I did find it.

PC Plus logoIn the article I talked about how you might approach writing a program to solve putting the 12 pentominoes into a 3×20 box (there are 2 solutions). I started off with the brute force method, which is laughable as an algorithm, although doable on modern machines, and moved on to more subtle methods like observing that X or F (the pieces are named after the letters of the alphabet they most closely resemble) cannot be placed right next to the short edges, and so on.

I then talked about the exact cover problem. Suppose you have a matrix of ones and zeroes. Can you select a set of the rows such that when they’re merged together there is one and only one 1 in each of the columns? This is known as an exact cover, and is amenable to a solution that involves a backtracking algorithm. Knuth was the first to notice that you can do some clever recursive stuff with linked lists of linked lists that would help with the housekeeping needed for backtracking, and called the resulting algorithm, the Dancing Links Algorithm, or DLX.

It turns out you can phrase a pentominoes problem as an exact cover (in essence, every square in the box has to be occupied by one and only one square from the 12 pieces) and so is amenable to a solution from DLX. Ditto, a Sudoku puzzle can also be cast into a large exact cover problem.

(Aside: although the DLX paper is still available online, it’s now been published in Knuth’s Selected Papers on Fun and Games.)

This article first appeared in issue 294, May 2010. It also appeared online on the PCPlus website.

You can read the PDF here.

(I write a monthly column for PCPlus, a computer news-views-n-reviews magazine in the UK (actually there are 13 issues a year — there's an Xmas issue as well — so it's a bit more than monthly). The column is called Theory Workshop and appears in the Make It section of the magazine. When I signed up, my editor and the magazine were gracious enough to allow me to reprint the articles here after say a year or so.)

Album cover for Beaucoup FishNow playing:
Underworld - Shudder-King of Snake
(from Beaucoup Fish)

Loading similar posts...   Loading links to posts on similar topics...

5 Responses

#1 Ryan said...
26-Jun-11 7:04 AM

I am wordering if there has been designed a program to solve a pentomino puzzle by taking input for the size of the board (no blank squares) AND the specific shapes to use to solve it.

Thank you!

julian m bucknall avatar
#2 julian m bucknall said...
05-Sep-11 9:48 AM

Ryan: Not that I know of. However, once a general pentomino app is written (something I've been meaning to do for a while), it should be easy to change it to make it solve such a problem for an arbitrary board size and pieces.

Cheers, Julian

#3 Howard Fink said...
24-Feb-15 1:08 PM

Gerard's Universal Polyomino Solver does not show code, but solves a variety of pentomino puzzles.

#4 Naomi said...
25-Jun-15 6:31 AM

This is what I used to play when I was a little girl ! May I know where I could buy one please ?

julian m bucknall avatar
#5 julian m bucknall said...
25-Jun-15 9:18 AM

Naomi: It all depends on what you want and how much you want to pay. Amazon have a bunch, ditto eBay.

Cheers, Julian

Leave a response

Note: some MarkDown is allowed, but HTML is not. Expand to show what's available.

  •  Emphasize with italics: surround word with underscores _emphasis_
  •  Emphasize strongly: surround word with double-asterisks **strong**
  •  Link: surround text with square brackets, url with parentheses [text](url)
  •  Inline code: surround text with backticks `IEnumerable`
  •  Unordered list: start each line with an asterisk, space * an item
  •  Ordered list: start each line with a digit, period, space 1. an item
  •  Insert code block: start each line with four spaces
  •  Insert blockquote: start each line with right-angle-bracket, space > Now is the time...
Preview of response