Archive

Archive for September, 2012

Dancing Links

September 30, 2012 1 comment

In computer science, Dancing Links, also known as DLX, is the technique suggested by Donald Knuth to efficiently implement his Algorithm X.[1] Algorithm X is a recursive,nondeterministic, depth-first, backtracking algorithm that finds all solutions to the exact cover problem. Some of the better-known exact cover problems include tiling, the n queens problem, and Sudoku.

Wikipedia

A while ago I spent some time implementing Dancing Links and I used it to make yet another Sudoku solver. One of the reasons I found it interesting was that some claimed that it was one of the fastest known algorithms for Sudoku solvers.

Implementing DLX and encoding the Sudoku problem in exact coverage is non trivial. I found this text useful (although it is actually wrong about the number of constraints, missing the fact that we must encode a single value per cell) while digging into the detail.

A few other related links:

I wanted to test a couple of performance scenarios before publishing but I realize it might not happen. So, before I forget I actually wrote it… here it is.

Advertisements
Categories: Uncategorized