You would be hard pressed to find to find someone who has not heard of the popular logic game Sudoku. You are given a \(9 \times 9\) board of \(81\) squares logically separated into \(9\) columsn, \(9\) rows, and \(9\) \(3 \times 3\) subsquares. The goal is, given a board with some initial numbers filled in, fill in the rest of the board so that every column, row, and subsquare have all the digits from 1 to 9.

While solving Sudoku is a good brain exercise, we can go one further, write a program to solve Sudokus and henceforth consider all future Sudokus solved. To follow the first part, you should be familiar with basic programming (I’ll be using Java, but it naturally translates to other languages) and the concept of recursion. Part 2, where we introduce the Dancing Links algorithm for solving Sudoku might be slightly more challenging.

1 The simplest solver

Imagine the simplest most brute-force method of trying to solve a Sudoku puzzle. Take the first empty square, and try putting all the numbers from \(1\) to \(9\) into it one by one. Start off by putting a \(1\) there and move on to the next empty square. Repeat this until you fill in all the squares. At this point, you’ll have a fully filled board, but it might not be a correct board – you have a write a function that checks whether a fully filled Sudoku board is valid. If it is, congratulations, you found a solution! Otherwise, you have to go back (the correct term is backtrack), and try the next possible number in turn for the previously filled in square.

1.1 Simplest solver Java code

Here is how the above text translates to a piece of Java code. For the rest of this article we’ll use to the convention to use an int[][] to represent a sudoku board, where a 0 represents an empty value, and numbers 1..9 represent their respective integers.

import java.util.Arrays;

public class VeryNaiveSudokuSolver{
    
    private void solve(int[][] sudoku, int idx){
        int size = sudoku.length;
        if(idx == size*size){
            if(isSolution(sudoku)){
                System.out.println("Found a solution via very naive algorithm: ");
                printSolution(sudoku);
                System.out.println();
            }
        } else{
            int row = idx / size;
            int col = idx % size;
            if(sudoku[row][col] != 0){ // the square is already filled in, don't do anything 
                solve(sudoku,idx+1);
            } else{
                for(int i = 1; i <= 9; i++){
                    sudoku[row][col] = i;
                    solve(sudoku,idx+1); // continue with the next square
                    sudoku[row][col] = 0; // unmake move
                }
            }
        }
    }
    
    // Precondition: `sudoku` all contains numbers from 1..9 and is a 9x9 board
    // Returns true if and only if sudoku is a valid solved sudoku board
    private boolean isSolution(int[][] sudoku){
        final int N = 9;
        final int side = 3;
        boolean[] mask = new boolean[N+1];
        
        // Check rows
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                int num = sudoku[i][j];
                if(mask[num]) return false;
                mask[num] = true;
            }
            Arrays.fill(mask,false);
        }
        
        // Check columns
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                int num = sudoku[j][i];
                if(mask[num]) return false;
                mask[num] = true;
            }
            Arrays.fill(mask,false);
        }
        
        // Check subsquares
        
        for(int i = 0; i < N; i += side){
            for(int j = 0; j < N; j+= side){
                Arrays.fill(mask,false);
                for(int di = 0; di < side; di++){
                    for(int dj = 0; dj < side; dj++){
                        int num = sudoku[i+di][j+dj];
                        if(mask[num]) return false;
                    }
                }
            }
        }
        
        return true; // Everything validated!
    }

    public void runSolver(int[][] sudoku){
        solve(sudoku,0);
    }

}

The above piece of code is a direct translation of the previous explanation. It goes like this:

1. Fill the board completely with numbers
2. Check if it’s a valid solution
3. If there are still boards you haven’t looked at, go back to 1.

Essentially, this will perform a naive Depth-First-Search (DFS). If the initial board is completely empty, you will in theory go through all the \(9^{81}\) board combinations, which is just around the number of all particles in the universe. It will simply never finish! Even if the board is partially filled in with, say, 10 numbers, doing \(9^{71}\) computations will not finish either. Hence the code above is only of educational value, and worthless for solving an actual puzzle!

2 Smarter Sudoku Solving

Consider the naive solver we looked at in the previous section. The problem is that we spend a lot of time exploring solution subspaces that cannot contain a solution! Say you have a sudoku with a \(1\) at position \((1,1)\). Then any solution that tries to place a \(1\) anywhere in column 1 or row 1 cannot possibly be a valid solution since it violates the rules of sudoku.

Let’s modify our solving algorithm in the following way:

1. If placing an integer \(n\) at position \((i,j)\) results in an invalid board state which can’t possibly lead to a solution, abandon this branch of computation.
2. Modify the function that checks whether a board is valid to a function that checks whether placing a number \(n\) at position \((i,j)\) results in a valid board state.

The modified Java code:

public class NaiveSudokuSolver{
    
    private void solve(int[][] board, int ind){
        final int S = board.length;
        if(ind == S*S){
            // We've definitely reached a solution now
            System.out.println("Solution via naive algorithm found: ");
            printSolution(board);
            System.out.println();
        }
        else{
            int row = ind / S;
            int col = ind % S;
            
            // Advance forward on cells that are prefilled
            if(board[row][col] != 0) solve(board, ind+1);
            else{
                // we are positioned on something we need to fill in. Try all possibilities
                for(int i = 1; i <= 9; i++){
                    if(consistent(board, row, col, i)){
                        board[row][col] = i;
                        solve(board,ind+1);
                        board[row][col] = 0; // unmake move
                    }   
                }
            }
            // no solution
        }

    }
      
    // Check whether putting "c" into index "ind" leaves the board in a consistent state
    private boolean consistent(int[][] board, int row, int col, int c) {        
        final int S = board.length;
        // check columns/rows
        for(int i = 0; i < S; i++){
            if(board[row][i] == c) return false;
            if(board[i][col] == c) return false;
        }
        
        // Check subsquare
        
        int rowStart = row - row % side; 
        int colStart = col - col % side;
        
        for(int m = 0; m < side; m++){
            for(int k = 0; k < side; k++){
                if(board[rowStart + k][colStart + m] == c) return false;
            }
        }
        return true;
    }

    public void runSolver(int[][] sudoku){
        solve(sudoku,0);
    }

}

This technique will suffice in solving any Sudoku puzzle reasonably fast.

2.1 Naive DFS Algorithm Benchmark

For benchmarking, Sudoku boards generated by qqwing were used. For each difficulty setting (simple, easy, intermediate, expert), 200 boards were randomly generated and then used for benchmarking.

The table below shows results (in milliseconds).

3 Dancing Links

Dancing Links is an algorithm by Knuth to solve exact cover problems (also called Algorithm X). An exact cover problem, for our purposes, is as follows: given a matrix of ones and zeros, select a subset \(S\) of the rows so that each column has exactly one \(1\) when looking at just the rows \(S\).

If you are interested, I really urge you to read the above linked paper. It might come as a surprise (given he is known for writing encyclopedias of computer science), Knuth is a surprisingly readable author and Dancing Links is based on a surprisingly simple idea regarding doubly-linked lists.

What’s important for us, is that a Sudoku puzzle can be trivially represented as an exact cover problem. Not only that, but many other problems, when suitably expressed as an exact cover problem (for example N-queens), can also be solved using Algorithm X. We just need to write Algorithm X once, and then for any problem in which we are interested in and which can be formulate as an exact cover problem, we just need to implement the translation.

If you are eager and want to have a look at the code on github, here you go.

3.1 Dancing Links Sudoku Benchmark

We use the same data-set for the benchmark of Dancing Links.

Solving a board takes on average around a millisecond. As a rough estimate, Dancing Links is around 30-50 faster (including the time to perform the translation and set-up of Dancing Links data structures).

You might be surprised that as the perceived difficulty from qqwing increased, the solvers seem to perform better. My guess is that this is due to the harder problems presenting more constraints, which are difficult for humans to take into account all at once when solving a Sudoku and causing a lot of back-tracking, are actually easier for a computer – the more logical constraints there are for a fixed number of variables, the quicker a computer will be able to arrive at a solution. If you are interested, I explored a similar idea for the game Hashiwokakero in my masters thesis along a bunch of other things.

3.2 Dancing Links Code

Dancing Links is slightly more complex than a simple recursive Depth-First-Search. You won’t find a better way to understand it and implement it than by reading Knuth’s excellent paper.

If you would prefer to skip to implementation, I have made it available on github. The core of the algorithm is in DancingLinks.java, while the Sudoku-specific implementations are in the rest of the files.

4 Conclusion

There is a large amount of optimizations you can do to our naive version to make it faster. They are Sudoku-specific though, and they will not outperform Dancing Links, and moreover cannot be reused for other combinatorial problems of interest. If you are interested in writing a Sudoku solver, I hence highly encourage you to read Knuth’s paper and, more importantly, implement the algorithm in your language of choice. If you have any questions or comments, please don’t hesitate to speak out in the comment section below.