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.