Re:Donald Knuth's 2024 Christmas Lecture: Strong and Weak Co...
by OskarS on Friday February 07, 2025 @08:25AM
(#42972250)
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.
Re:Donald Knuth's 2024 Christmas Lecture: Strong and Weak Co...
by mangodrunk on Friday February 07, 2025 @07:52PM
(#42979259)
Is this the paper? https://arxiv.org/abs/cs/0011047
Re:Donald Knuth's 2024 Christmas Lecture: Strong and Weak Co...
by bandana on Friday February 07, 2025 @09:16PM
(#42979735)
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.
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).