[bandana]

I was not aware of an update to this algorithm, I'll have to look it out.

The original dancing link is one of my favorite papers, you can really see Knuth's love for algorithms (it's not in every paper you see sentences like "This process causes the pointer variables inside the global data structure to execute an exquisitely choreographed dance"). I'm using it to generate crosswords (the horizontal and vertical words forming an exact cover of the grid).

[OskarS]

I cannot recommend checking out Volume 4B enough, then. He goes much deeper, improves the algorithm, adapts it to different constraint problems, and provides hundreds of really cool exercises (including word problems like crosswords, I think). It's the best.

[mangodrunk]

Is this the paper? https://arxiv.org/abs/cs/0011047

[bandana]

Yes that's the one ! I found it when I was trying to solve the tetraminos in The Talos Principle without looking for a game guide... I agree with OskarS it is a rewarding algorithm to implement.