Dancing Links

For this blog post I'm going to explain one of the most useful and yet easy to grasp algorithms used in modern day Computer Science: Dancing Links. Dancing Links is used to solve the Exact Cover problem (which is NP-complete) efficiently.

I'll be breaking down each aspect that you need to understand in order to apply the Dancing Links algorithm to your own problems, so you don't need to know any relevant information before reading this!

What is the Exact Cover problem?

An Exact Cover problem is a problem that consists of a set of constraints and a set of values. The aim of the problem is to find the values in the set which satisfy every constraint exactly once. This may sound a bit odd at first, but most of you will have tried (and completed) many problems like this when solving puzzle games, one famous example being Sudoku. Sudoku is an exact cover problem, it's just not formatted as one. This leads onto the question, how do you represent an exact cover problem?

Well, they are usually represented using an incidence matrix, or even a simple table would do. Let's take a look:

In this example, doubly-linked lists are used to represent an exact cover problem. A much more simple representation of the exact same problem would be:

In case you're new to matrices and are baffled by the "simplistic" image, for this example you can just think of it as table. Keep in mind they're not the same thing, but visually they produce the same results. For example, the second image has 7 columns and 6 rows, the first column having two 1s in rows 2 and 4.

Great, now you know how to represent an exact cover problem, but what does it actually mean? Don't worry about the first image too much for now, we'll focus more on that when we move on to the actual algorithm. As I mentioned earlier, you can visualise the second image using "rows" and "columns". Well, the columns represent the constraints of the problem and the rows represent each possible position. We can use this logic to convert a Sudoku puzzle into an exact cover problem.

Sudoku has 4 constraints (matrix columns):

• Position: There's must be 1 number per cell
• Region: Each number must appear exactly once in every region
• Row: Each number must appear exactly once in every row
• Column: Each number must appear exactly once in every column

To make things even easier, all of these 4 constraints always have the same number of occurrences in Sudoku.

E.g. For a 9x9 Sudoku board, there will be 9^2 cells (rows*columns), 9^2 regions (regions*number-range), 9^2 columns (columns*number-range), etc. I'm sure you get the picture. We can use this to calculate the number of matrix columns being rows^2*4, in this example rows being 9.

Similarly for the matrix rows, there would be rows^3 possibilities (rows*columns*number-range).

How do we solve it using Dancing Links?

There are 5 steps to go through in order to solve the problem using Dancing Links:

1. Choose a column (constraint) with the least amount of 1s in. If there are none left then the process is complete.
2. Choose a row which satisfies that constraint (has a 1 in that column). If there are none then the process should backtrack to the previous time a row was chosen and make a different choice instead.
3. Add that row to the set of solutions.
4. Delete (or simply 'cover') all rows that satisfy any of the constraints that are also satisfied by the chosen row, thus rendering those constraints empty of 1s. (All columns that have a 1 in the chosen row are deleted and all rows which have a 1 in these columns are also deleted).
5. Return to step 1.

This image shows steps 1 through 4 visually. As you probably noticed, it's very similar to the first image on the post. At first column A is chosen. Row AD (The row which only has a 1 in columns A and D) is made black in this example, to show that it's been chosen and added to the partial solution. Columns A and D are then covered so that they're no longer part of the matrix (the surrounding arrows diverting other columns/rows).

Also, all rows in columns A and D are covered, thus completing step 4.

If you noticed that the cell in the final row of column D doesn't look to be covered (as well as the cells in Column A) this is simply because columns A and D are already covered, so they don't need to be.

After all the backtracking and searching is complete, you should end up with something like this:

All columns have been covered, leaving rows AD, BG and CEF making up the final solution.

That basically wraps this up, if you have any questions then you can contact me here or on the SH Discord. Just remember, there are thousands of puzzles which can be formatted as exact cover problems, and this algorithm can solve all of them. I hope you enjoyed this post and learnt something new. Thanks for reading!