I’ve recently came across Knuth’s Algorithm X, and the implementation he calls “Dancing Links” (in the context of a Sudoku solver, but that’s a whole other story.)
This is a back-tracking method for a wide range of problems (problems reducible to an instance of the Exact Cover problem.)
While Knuth’s DLX is still not a deterministically polynomial-time algorithm (I just invented a concept! Hurray!) (or is it?) the algorithm is beautiful and very efficient in practice.
Printer-friendly version
Post a Comment