Experiment № 096 · The story
Put Back Exactly
Why I picked it
Donald Knuth gave a lecture in 2000 called "Dancing Links", about a trick he credits to Hitotumatu and Noshita in 1979, and the title is the whole idea. When you delete a node from a doubly linked list, the neighbours forget it, but the node doesn't forget them. So if you ever want to undo the deletion, and you undo things in exactly the reverse order you did them, two assignments put it back with nothing to search for and nothing to copy. Backtracking is precisely that kind of undo, so Knuth built his exact-cover solver, Algorithm X, out of lists that unlink and relink themselves thousands of times a second. I had done plenty of searches in this collection, but never one where the undo was the interesting part.
Pentominoes are his own favourite demonstration, and they have a history worth honouring. Dana Scott had a computer tile an 8×8 board with a hole in the middle in 1958 (65 ways), and Colin and Jenifer Haselgrove counted the 2,339 ways to fill a 6×10 rectangle in 1960.
What I enjoy about it
The numbers in the empty squares. Each one is how many placements could still cover that square, given everything already on the board, and the solver keeps them correct for free, because they are just the lengths of the lists it is unlinking. Watch a square drop to 1, or 0, after a careless placement: with "Fewest options" the solver goes straight there, because a square that can be filled in only one way should be filled now, and a square that can't be filled means the whole branch is dead, however promising the rest looks.
Then switch to "Next piece", which does what most of us would do by hand: take the pieces out of the box in order and try each one everywhere. It never looks at the starving squares, so it can't see a doomed board until the very end. The same solver, with one line changed, goes from a tiling every few seconds to almost nothing at all.
Something you might take away
Two things, really. One is that "where should I look next?" can matter more than how fast you look: always go to the place with the fewest choices. The other is about undoing. A lot of cleverness goes into remembering what changed so you can reverse it. Here nothing is remembered; the removed thing simply keeps hold of where it came from, and if you put things back in the opposite order to the way you took them out, it all goes back exactly as it was.