Home > Uncategorized > Dancing Links

Dancing Links

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
  1. No comments yet.
  1. January 20, 2013 at 8:19 pm

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: