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.)

A familiar topic for me for the January 2010 issue: testing a pseudo-random number generator’s (PRNG) output for randomness. I say familiar because I’ve talked about it before, most recently in my book. Well, OK that was 10 years ago, but still, the techniques don’t change. And it’s extremely fascinating, to boot.

I began the article with Knuth’s classic joke on random numbers: is 2 a random number? (Volume 2 of The Art of Computer Programming, Seminumerical Algorithms, page 2.) I’ll note here that xkcd riffed off this joke with a hilarious C version as shown below.

I then invited my readers to think about the problem: could a random digit sequence include three 4s in a row? (Yes.) Could it include a sequence, like 4, 5, 6? (Yes.) And so on. In essence, I made the point that humans are pretty bad at evaluating whether a sequence of numbers is random or not.

Possibly one way to evaluate whether a sequence is random or not is to try and compress it: random sequences do not compress well since they don’t have repeatable (redundant) information that we can take advantage of for compression. I didn’t use this example in the article because it would have meant talking about information theory and about encoding the random numbers in something other than ASCII, or using 8-bit random bytes or something. Anyway...

Basically the only way to test a sequence for randomness is to use statistical tests on the numbers in the sequence. I then derived χ² (chi-square) testing, but in a way that made sense to my semi-technical layman audience. Once I had that statistical tool, I was away: the uniformity test, the gap test, the poker test, the coupon-collector’s test, all mentioned in Knuth.

I threw in a couple of nice images showing that the output from a PRNG should also not exhibit regularity when grouped in pairs and plotted on a graph. This kind of test could be extended to multiple dimensions equally as well (although I must admit that the Minimal Standard Generator I briefly discussed would fail other Knuth tests badly).

I also mentioned in the article George Marsalgia’s DIEHARD tests which encompass and extend Knuth’s. Wikipedia has a little on the tests involved, but it’s best to go to the source for full information.

One story I didn’t talk about is about the Delphi PRNG (seeded through the Randomize() procedure and accessed using the Random() function) and how it meant that an online poker game could  compromised, despite the fact that its output passes Knuth’s tests. In one sense the output is random, and in another it’s completely predictable. It’s a salutary story and you read up on it here.

This article first appeared in issue 290, January 2010.

You can download the PDF here.