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:
photo © 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.
In 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.)
Now playing:
Underworld - Shudder-King of Snake
(from Beaucoup Fish)
Loading links to posts on similar topics...
5 Responses
#1 Ryan said...
26-Jun-11 7:04 AMI 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!
#2 julian m bucknall said...
05-Sep-11 9:48 AMRyan: 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 PMGerard's Universal Polyomino Solver does not show code, but solves a variety of pentomino puzzles.
#4 Naomi said...
25-Jun-15 6:31 AMThis is what I used to play when I was a little girl ! May I know where I could buy one please ?
#5 julian m bucknall said...
25-Jun-15 9:18 AMNaomi: 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.
_emphasis_**strong**[text](url)`IEnumerable`* an item1. an item> Now is the time...Preview of response