While looking at applications of recursion, I stumbled across a video for solving sudokus using Python by Pr. Thorsten Altenkirch from the University of Nottingham (UK) . The elegant solution got me wondering what an idiomatic Rust implementation would look like. Here is what I came up with.

Modelling the Sudoku grid

Sudokus have a very straightforward code representation as they are 9x9 grids of numbers. Each cell can either contain an integer between 1 to 9 inclusively, or nothing at all. The empty cells are filled sequentially respecting simple unicity rules along rows, columns and 3x3 blocks. A sudoku is solved when no empty cells remain.

Rust being a statically typed language, the most relevant approach is to fill empty cells with the number 0. This way, a sudoku grid can be defined by a two-dimensional array of type usize. Here is the declaration and assignment of our example:

let mut sudoku : [[usize;9];9] = [
    [0,2,8, 3,0,0, 0,0,4],
    [5,0,6, 0,0,0, 0,0,0],
    [7,0,0, 0,4,0, 0,0,0],

    [0,9,3, 0,0,0, 0,0,0],
    [8,0,0, 1,0,0, 6,0,0],
    [0,0,0, 0,5,0, 0,0,8],

    [0,0,0, 0,0,5, 0,4,6],
    [1,0,0, 0,0,9, 0,0,3],
    [0,5,0, 0,1,0, 9,2,0]
];

Variable scope and helper functions

In the Python implementation, the sudoku grid is set as a global variable. Doing so in Rust comes with an important limitation: Only closures have access to global variables, and those who do, can not be recursively called. Given that the solver relies on recursion, the appropriate course of action is rather to use functions that take the sudoku grid variable as a mutable reference should the function need to modify it.

The first function we can write is the helper function possible that will check if a particular integer n can be inserted in the sudoku grid at position (i,j). This function will check uniqueness of the value n along the relevant row, column and 3x3 block. The most idiomatic way to approach this implementation in Rust is to make use of ranges and iterators. Here is the function’s code:

fn possible(grid: &[[usize;9];9], i: usize, j: usize, n: usize) -> bool {
    let (i0, j0) = ( (i / 3) * 3, (j / 3) * 3 );
    let block_check = (j0..j0+3).all(|index_j| (i0..i0+3).all(|index_i| grid[index_j][index_i] != n) );
    let rowcol_check = (0..9).all(|k| (grid[j][k] != n) && (grid[k][i] != n));
    rowcol_check && block_check
}

The all method for iterators is used extensively to check adherence to the unicity rules of the puzzle. Remember that this method uses short-circuiting, meaning that it will return false as soon as a false result is observed. This conveniently saves us from potential useless computations and allows for a very succinct code avoiding for loops. The sudoku grid variable is passed as an immutable reference because the function should not modify it in any way.

for convenience, we will also define a simple helper function that sequentially prints in the console each row of the grid. It is uncreatively called print_sudoku:

fn print_sudoku(grid: &[[usize;9];9]) {
    for row in grid.into_iter() {
        println!("{:?}", row);
    }
    println!("---------------------------");
}

Recursive function call

Now onto the solve function that will use recursion and the backtracking concept. The function returns a boolean signalling whether a solution has been found or not. It is then called recursively at each incremental change of the sudoku grid. It is possible to avoid for loops using the for_each method for iterators, but it felt overkill in this case. Here is the code:

fn solve(grid: &mut [[usize;9];9]) -> bool {
    for j in 0..9 {
        for i in 0..9 {
            if grid[j][i] == 0 {
                for n in 1..10 {
                    if possible( grid, i, j, n) {
                        // Passing a mutable reference as immutable is perfectly allowed
                        grid[j][i] = n; // If possible, assign value
                        if solve( grid ) { print_sudoku( grid ) } // Recursive call on the modified grid
                        grid[j][i] = 0; // If unsuccessful, reset value
                    }
                }
                return false; // No value found for this grid position, solve failed
            }
        }
    }
    true
}

The function as it is written will print all solutions it encounters consecutively, as the print_sudoku function is called when the inner solve function call returns true. If no solutions are found, nothing gets printed. In our example, this is what the function calls generates:

solve(&mut sudoku);

// prints a unique solution:
// [9, 2, 8, 3, 6, 1, 5, 7, 4]
// [5, 4, 6, 9, 7, 2, 3, 8, 1]
// [7, 3, 1, 5, 4, 8, 2, 6, 9]
// [6, 9, 3, 2, 8, 7, 4, 1, 5]
// [8, 7, 5, 1, 9, 4, 6, 3, 2]
// [4, 1, 2, 6, 5, 3, 7, 9, 8]
// [2, 8, 9, 7, 3, 5, 1, 4, 6]
// [1, 6, 7, 4, 2, 9, 8, 5, 3]
// [3, 5, 4, 8, 1, 6, 9, 2, 7]
// ---------------------------

Feel free to put this algorithm to the test and even extend it to suit more elaborate sudoku grids. If you like this post, follow me on Twitter and get notified on the next posts.