I found Knuth’s “Dancing Links” paper [1] very well written and a somewhat easy read (I had to reread certain parts a couple times). I had to write a sudoku solver for one of my classes and I read that dancing links and algorithm x was one way to do it [2]. I then read some things around the internet to apply dancing links to sudoku solving [3] [4]. If you read the Wikipedia entry on exact cover problems there is a section on sudoku as an exact cover problem [5] this is one thing necessary to understand in order to implement a sudoku solver with algorithm x and dancing links.
Knuth even talks about dancing links in his new 2017 Christmas Tree Lecture [6] specifically here at 4:28 [7]. Basically he uses dancing links to solve for certain n in the problem he sets up in that lecture.
You may like to know that Knuth's fascicle 5C of The Art of Computer Programming Volume 4 is going to be entirely about Dancing Links. He's still working on it, but the “incomplete draft” is available at the (hidden) link https://cs.stanford.edu/~knuth/fasc5c.ps.gz — check it out if you're interested; it's already 130 pages of fun.
Wow, this really is good I started it and skimmed the rest of it the first 34 pages are explanations and algorithms of dancing links and the rest of the 130 pages is all exercises and answers to those exercises. Truly awesome, thanks again for the link.
I think he mentioned that it would be in his new book, but I had no idea there would be over 100 pages of dancing links. That is sweet! I’d love to take a look at it, so I could get a better grasp of how it applies to other problems.
Knuth even talks about dancing links in his new 2017 Christmas Tree Lecture [6] specifically here at 4:28 [7]. Basically he uses dancing links to solve for certain n in the problem he sets up in that lecture.
[1] https://arxiv.org/abs/cs/0011047
[2] https://en.wikipedia.org/wiki/Sudoku_solving_algorithms#Exac...
[3] http://garethrees.org/2007/06/10/zendoku-generation/
[4] https://www.ocf.berkeley.edu/~jchu/publicportal/sudoku/sudok...
[5] https://en.wikipedia.org/wiki/Exact_cover#Sudoku
[6] https://www.youtube.com/watch?v=BxQw4CdxLr8
[7] https://youtu.be/BxQw4CdxLr8?t=4m28s