Re:Dancing Links (A very useful hack by Knuth)
by slackenerny on Tuesday June 01, 2010 @03:04PM
(#1395837)
Cool, this.
A very nifty (if somewhat detailed) complexity analysis of the Algorithm X appeared in blogosphere's festschrift for Knuth's 70, http://11011110.livejournal.com/128249.html
I've used P159 in my absolutely first assignment in the intro programming class. I was to make a N-queens solver. The assignment obviously asked for a 8-line backtracking program. But I was naïve. I went to the library and turned it inside out. My solution was ca. 500 lines, and also implemented a way to find the number of solutions without computing them (this was from IIRC a paper by Rivin), and had a randomized mode which would find just a single solution but for fast for very large N (this I found in Norvig's AIMA in a footnote referencing a paper by J.M., I don't remember the page or the full name)). Good times.
Re:Dancing Links (A very useful hack by Knuth)
by MichaelSalib on Tuesday June 01, 2010 @01:51PM
(#1395633)
I once used this algorithm to solve a word box puzzle: given a dictionary of words, construct the largest possible square of characters where every row and every column in the square forms a word drawn from the dictionary.
A very nifty (if somewhat detailed) complexity analysis of the Algorithm X appeared in blogosphere's festschrift for Knuth's 70, http://11011110.livejournal.com/128249.html
I've used P159 in my absolutely first assignment in the intro programming class. I was to make a N-queens solver. The assignment obviously asked for a 8-line backtracking program. But I was naïve. I went to the library and turned it inside out. My solution was ca. 500 lines, and also implemented a way to find the number of solutions without computing them (this was from IIRC a paper by Rivin), and had a randomized mode which would find just a single solution but for fast for very large N (this I found in Norvig's AIMA in a footnote referencing a paper by J.M., I don't remember the page or the full name)). Good times.