The Dancing Links Algorithm - An explanation that is less explanatory but more on implementation?

Question

I've been working on a Sudoku Solver, my current solver uses the backtracking algorithm but it still takes too long.

I'm hoping to get it down to less than a second for most cases. As such, I've decided to rewrite it with the dancing links algorithm, understanding it is one of the better bruteforce methods that works well especially with a constraint problem such as the Sudoku Puzzle.

I have tried to read the Wiki and Knuth's paper on it, however both of them are kinda hard to comprehend and extremely verbose.

I also read Sudopedia's version on it, and it seems that once it got to the Sudoku's implementation, it got too abstract.

Can someone try to explain the Dancing Links algorithm not in terms of its derivation but its implementation? (would be great to use the Sudoku as an example)

Thanks!

Answer 1

You might be interested in my implementation in javascript.

---

Firstly you have to understand Exact Cover. An exact cover problem is a problem where you're given a bunch of choices, and a set of constraints and your challenge is to select a bunch of the choices that will fill every constraint exactly once.

For example, consider the case of someone creating their ice dance routine. They have a number of tricks that they need to show the judges, and don't want to perform any trick more than once. They have a number of sequences which are groups of tricks that can be put together and they want to choose the ideal selection of sequences to cover all the tricks once. In this example, the constraints are that they must perform every trick. The choices are the possible sequences they could incorporate into their routine.

A nice way to represent problems of this sort is to draw out a table where the constraints are columns and the choices are rows, and you have a big X in cells where a particular choice fulfills that constraint.

As it turns out, given the right constraints and choices, sudoku can be described as an Exact Cover problem.

---

Ok, assuming you've got that, now you need to understand Algorithm X. Knuth said of it "Algorithm X is simply a statement of the obvious trial-and-error approach. (Indeed, I can’t think of any other reasonable way to do the job, in general.)". So here's my description of algorithm X:

1. If your table has no columns, stop - you've solved it. If you've got a partial solution stored, then it's actually a real solution, return it.
2. Select a column (representing a constraint).
3. Find a row with a cross in that column (representing a choice that fulfills that constraint). Add it to some kind of structure where you're storing potential solutions. If you can't find a row, give up - there are no solutions.
4. Assume that the row you found in 3 is in the solution, so remove all columns that it have an X in that row. While removing all those columns, also remove all rows that have an X in the columns you're removing (because you've already satisfied the constraint, so you're barred from choosing something that would satisfy it again).
5. Now recursively try to solve the reduced table. If you can't, remove the row you tried from the potential solution structure, restore all the rows and columns you removed in steps 3 and 4 and try a different row. If you run out of rows, then give up - there are no solutions.

---

Now that you understand that, you can understand dancing links. Dancing Links is a way of implementing that algorithm efficiently. The key point of dancing links is that in a linked list, when you remove a node (which can be done efficently by modifying the pointers of its neighbours), the node that you've removed has all the information you need to add it back to the linked list (in the case that it turns out you were wrong when you guessed it was part of the solution). That plus the fact that if you make all your linked lists circular then suddenly you lose a lot of special cases is pretty much all dancing-links is.