Sudoku Solver with Dancing Links

I used Algorithm DLX to create a Sudoku solver. I set up the 2D matrix of constraints and possibilities, then copied the algorithm. I also learned how the algorithm works.

The start, headers, and row nodes are all the same class(Node). It does all the linking necessary to create the 2D matrix. The start node only has to point in one direction. I initialize the headers in the same order as on this Wiki page. There are 4 different types of constraints. Each constraint type has 81 columns.

The data variable can be used to describe headers and row nodes. It is a list of 4 ints. A header node will have two 0’s in the list and 2 non zeros. The index indicates whether it refers to a row, column, box or number in that order. For example the data for the header/constraint node of Box 1, number 2 is [0, 0, 1, 2]. Row nodes don’t have any zeros in their data list. There are 81 cells and each cell can have 9 different numbers in it. The total of 729 rows represents every number that can be put in every cell. The row, column, box and number are known for each row. Every row has a node in each of the four types of constraints.

I loop through all the constraints to find the four that match the current row. This keeps the row in order so I can link them easily. For each constraint the current row matches, create a node at the bottom of that column. When that row of 4 is created, they are doubly and circularly linked. Every header points up to the bottom node in its column, and every bottom node points down to its header. In the end every node(besides start) is doubly linked in two directions(the up, down direction and the left, right direction). Plus every row node has a pointer to its header(helps with cover and uncover).

This is where I copied the Solve, Cover, and Uncover methods from.

Solve is a recursive depth first search algorithm. The puzzle is solved when the start node points to itself. If that is not the case it searches unsatisfied constraints for a potential solution. It confused me when I saw the first loop goes down a column adding each node in the column/constraint to the solution. It doesn’t make sense because a real solution can’t have two nodes in the same column. But the solution will never have two nodes in the same column because it will either call Solve again or remove the node from the solution before looping again. The next loop does make sense, it covers the rest of the constraints that the current row satisfies. This is also what is done to create a puzzle. Any cell that is filled in covers 4 constraints, 1 of each type. This is what the right node cover loop is doing. The left node uncover loop undoes this.

There is no way to reach a column once it has been covered. Every solution has all constraints satisfied(each cell satisfies 4 constraints). The first call to Solve will not reach the end of the method if there is a valid solution because there has to be a node in that column that is part of the solution. The algorithm keeps putting numbers in cells until its current solution breaks, then it backtracks without repeating potential solutions.

Here are a bunch of puzzles in .smd format. Unfortunately I couldn’t find many more puzzles in this format.