Solving Sudoku

While trying to solve LeetCode's Sudoku Solver, I stumbled upon a cool general case of similar Exact Cover problems that can be solved (among other ways) with Dr. Donald Knuth's Dancing Links algorithm. In this blog, we will go through first understanding the problem and the algorithm, and finally implement everything in code. This blog is a summary of all the resources I used in the process, i.e. ocf.berkeley.edu/~jchu/.../sudoku.paper.

Exact Cover Problem

Definition: Given a matrix of 1's and 0's, exact cover is a set of rows in which exactly one 1 will appear for each column.

For example, in Knuth's Dancing Links paper figure 3,

0 0 1 0 1 1 0
1 0 0 1 0 0 1
0 1 1 0 0 1 0
1 0 0 1 0 0 0
0 1 0 0 0 0 1
0 0 0 1 1 0 1

Rows 1, 4, 5 (1 indexed) represent the exact cover.

If we think of the columns as elements and the rows as subsets of the elements then the problem can be seen finding disjoint (non-overlapping) sets (rows) that cover all the elements.

This represent a variety of applications that need to fill constraints. EC can be adapted to Sudoku as a special case of the problem.

EC can also be used to describe many real life problems such as making hotel room assignments given a group that has a many specific room requests, and organizing simple flight schedules for airports.

Finding exact cover is a NP-complete problem and a natural candidate for using backtracking to search for possible solutions.

A naive backtracking solutions will be the following:

If A is empty, the problem is solved; terminate successfully.
Otherwise choose a column, c (deterministically).
Choose a row, r, such that A[r, c] = 1 (nondeterministically).
Include r in the partial solution.
For each j such that A[r, j] = 1,
    delete column j from matrix A;
    for each i such that A[i, j] = 1,
        delete row i from matrix A.
Repeat this algorithm recursively on the reduced matrix A.

• If we find at a sub-problem that there is a column with no 1s then there are no valid smaller sub-problem, and the process backtracks to previous state of the problem.
• At any stage, we should pick the column with the smallest number of 1s in order to reduce branching.

Possible solutions

• Dancing links
• Brute force candidate elimination
  • TLE for hard sudokus which require guessing and backtracking.

Dancing Links Algorithm

The algorithm is based on Dr. Donald Knuth's paper. There is also a recorded lecture on the topic. Dancing Links is a backtracking, depth-first algorithm that can find all possible solutions of the problem.

Core Concept

The name and the core concept of the algorithm depends on using a matrix of doubly-linked lists where the links "dance" or toggle while backtracking possible solutions.

Say we want to remove object x from a list, we need only 2 operations:

x.getRight().setLeft(x.getLeft())
x.getLeft().setRight(x.getRight())

However, when putting the object back in the list, all is needed is to do the reverse of the operation, given that x's pointers remain unchanged.

x.getRight().setLeft(x)
x.getLeft().setRight(x)

A key point here is that x's pointers are not modified after x is deleted. We normally avoid such pointers from outside a linked list so that we don't interfere with garbage collection. However, this is useful for searching a valid solutions using backtracking since we can get the next available/valid entry without having to search through the list and recover x into the list when we backtrack to other areas of the solution space.

Theoretically, if we undo the steps taken from an initial state of a linked list in reverse order (undoing steps ABC by taking C'B'A') then we can get back the initial state of the linked list.

Dancing Links for Exact Cover

Dancing Links takes the Exact Cover matrix and puts it into a toroidal doubly-linked list. The links kind of represent the constraints of the problem, i.e. the row, column and grid constraints for Sudoku. Toroidal basically means that the linked lists are circularly connected (i.e. bottom with top and right with left).

For every column, there is a special ColumnNode, which contains that column's Unique Name and the column's size, the number of nodes in the column.

Every 1 in the Exact Cover matrix (actually represent as a set of rows), is a Node. Each Node points to another object up, down, left and right. The first and last Nodes for each column to its corresponding ColumnNode. A special ColumnNode h points to the first ColumnNode on the left as a starting point for the algorithm.

So Knuth's figure 3 would become:

Algorithm

Given the ColumnNode h, the searching algorithm is then simplified to:

if (h.getRight() == h)
{
    // made a round trip from h back to h
    printSolution();
    return;
}
else
{
    ColumnNode column = chooseNextColumn();
    cover(column);

    for (Node row = column.getDown(); rowNode != column; rowNode = rowNode.getDown())
    {
        // row and rowNode are different

        solutions.add(rowNode);

        for (Node rightNode = row.getRight(); otherNode != row; rightNode = rightNode.getRight()) {
            // otherNode ??
            cover(rightNode);
        }

        Search(k + 1);

        solutions.remove(rowNode);
        column = rowNode.getColumn(); // column gets updated

        for (Node leftNode = rowNode.getLeft(); leftNode != row; leftNode = leftNode.getLeft())
            uncover(leftNode);
    }

    uncover(column);
}

Cover

The cover(ColumnNode c) function is the crux of the algorithm. It removes a column from the
matrix as well as remove all rows in the column from other columns they are in. The code becomes:

Node column = dataNode.getColumn();

column.getRight().setLeft(column.getLeft());
column.getLeft().setRight(column.getRight());

for (Node row = column.getDown(); row != column; row = row.getDown()) {
    for (Node rightNode = row.getRight(); rightNode != row; rightNode = rightNode.getRight())
    {
        rightNode.getUp().setDown(rightNode.getDown());
        rightNode.getDown().setUp(rightNode.getUp());
    }
}

Note that we first remove the column from the other columns. Then we go down a column and remove the row by traversing the row to the right. Let's look at some illustrations. Here is the matrix before Column A is covered. All the links in bold are the links that are going to be affected by the cover function.

Now here is the matrix after Column A has been covered. Notice how Column A and rows 2 and 4 are now independently
linked outside of the matrix. In effect, they have been removed. Also note that each node that has
been removed from the matrix still points to an element inside the matrix. This allows us to easily
backtrack.

Uncover

The uncover(ColumnNode c) function is the answer to easy backtracking. Taking advantage of the fact that every node that has been removed retains information about its neighbors, we can easily put the node back into the matrix using the reverse operation of cover(ColumnNode c).

Node column = dataNode.getColumn();

// starting from the bottom row and moving up
for (Node row = column.getUp(); row != column; row = row.getUp())
{
    // starting from the rightmost column within a row
    for (Node leftNode = row.getleft(); leftNode != row; leftNode = leftNode.getRight())
    {
        leftNode.getUp().setDown(leftNode);
        leftNode.getDown().setUp(leftNode);
    }
}
column.getRight().setLeft(column);
column.getLeft().setRight(column);

Notice that the traversal through the column and row are opposite to that of cover(ColumnNode c). We first put the rows back by traveling up the column and to the left of the row. Then we put the column back. In effect, we undo the operation of cover(ColumnNode c).

Miscellaneous Functions

getConstraintWithLeastOptions() advances the column pointer right or chooses the column with the least number of nodes. Choosing the column with the least number of nodes decreases the branching of the algorithm. It can be ignored if this isn't needed.

As described in Knuth's paper, there are two methods to choose the next column in the search method. The first simply chooses the node to the right of ColumnNode h. The second minimizes the branching of the algorithm by looking for the column with the least number of nodes in the column. The second method is much faster for solving 16x16 Sudoku puzzles.

Finding a Solution

A solution is found when all the columns have been removed from the matrix. This means that very row that we have added to the answer has one node in every column. All constraints have been satisfied by the set of rows.

Modeling Sudoku as an Exact Cover Problem

Sudoku is a puzzle on a 9x9 grid with 3x3 regions, with the rule that the digits 1-9 must be placed in each cell such that every row, column, and region contains only one instance of the digit.

To create the sparse matrix of Sudoku needed to convert the problem into an Exact Cover Problem, we need to recognize what the rows and columns represent.

The columns represent the constraints of the puzzle. In Sudoku, we have four:

• A position constraint: Only 1 number can occupy a cell
• A row constraint: Only 1 instance of a number can be in the row
• A column constraint: Only 1 instance of a number can be in a column
• A region constraint: Only 1 instance of a number can be in a region

Each number comes with its own set of constraints. Therefore there are SIZE^2 * 4 columns., where SIZE is the number of candidates/rows/cols there are in the Sudoku Puzzle. In a 4x4, this would be 64 columns. In a 9x9, this would be 324 columns.

Given initial positions in the matrix, those rows will be included in the answer and covered(). Then the Search algorithm will produce the solutions to the puzzle.

Implementation

There are unique ways to code the solution for the problem using the pseudo-code in the paper. The best learning outcome will be to try it out yourself.

For reference, here is an OOP style implementation in C++: github.com/prantoran/.../sudoku-solver.cpp.

Here are some observations and tricks I learned during the process:

• Keep data models as separate classes and keep methods small.
• Take small steps and debug. Ensure that all previous steps are bug free before trying out next steps. For example, I checked whether the constraint columns are generated properly by assigning names and printing them out.
• The branching from a state affect runtime. At every step of search(), I picked the constraint column with the smallest number of options.
• Reduce possible rows by eliminating options that are impossible by checking the existing digits in the rows, columns and grids.

Good luck and have fun!