Knuth’s Fascicle 5 has arrived

Or to give it its full title, The Art of Computer Programming, Volume 4, Fascicle 5. Fascicle 6 on Satisfiability was published first, and these two form the first 2/3 (well, perhaps, we’ll see) of Volume 4B of Donald Knuth’s lifelong oeuvre.

Volume 4, Fascicle 5

The interesting thing about this particular fascicle is the concentration on backtracking and the use of what Knuth calls “Dancing Links”. He’d written about these before in a paper, subsequently published in his Selected Papers on Fun & Games from 2011. And Yours Truly, now I recall, had used that as an article for The Delphi Magazine, one of the very much later issues (July 2006), where I used back-tracking and then the dancing links algorithm to first solve Sudoku puzzles efficiently, and second to create them.

Time to dig that one up and transpose it to JavaScript. Stay tuned.

  Loading links to posts on similar topics...