News for hackers. Stuff that matters.
Re:Donald Knuth's 2024 Christmas Lecture: Strong and Weak Co... by bandana on Friday February 07, 2025 @06:19AM (#42971407)
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).

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