Simple Sudoku Solver in Rust

I have been learning Rust recently. As my starter project I have decided to write a simple Sudoku solver. This is something I have previously done when learning other languages as the problem is sufficiently complex to force you to get familiar with the language's features and it's data structures but small enough to let you easily try different approaches.

In the past I have been inspired and learned from other people's coding related blogs so I have decided to document my efforts in the hopes that it will be useful to someone else learning Rust.

Sudoku Solving Algorithm

There are many ways to solve Sudoku problems but the one I am going to use here is based on the set of potential numbers each cell can have. This is not going to solve the mode difficult puzzles but provides a reasonably good solver.

In a completely empty board every cell can potentially have any number as its value. So the set of potential values is [1..9] for every cell on the board. Sudoku puzzles do not start with an empty board but they already have some of the cells filled in.

We turn the inital set of cells into a list of constraints that we apply to the the board. For example; if the top-left corner (0,0) is set to 4, this reduces the potentials in the following ways:

• The potential sets for the top-left corner is reduced to 4
• The potential sets for all of the cells in the top row can no longer have 4 in it
• The potential sets for all of the cells in the left-most column can no longer have 4 in it
• The potential sets for all the cells in the top-left 3*3 grid can no longer have 4 in it

If the potential set falls to 1 for any cell, that cell has been solved. Whatever is the last remaining potential number is the solution for that cell and it is added to the list of constraints.

The above process continues until the list of constraints is empty. At that pointer either all of the cells have been solved.

Setting up the data

At the lowest level we need to represent the state of a cell. For now all that it has is a set of potential values. The Rust std library has the HashSet which seems like a good way to represent the potentials.

use std::collections::HashSet;

struct Cell {
    potentials: HashSet<u32>,
}

The cells are part of a 9-by-9 map. One way to represent this is to use a vector of vectors using Vec. So the Map now looks like

struct Map {
    cells: Vec<Vec<Cell>>,
}

Now I need a function to setup this data. I want to be able to pass in 9*9 sudoku board and the code will set up all potential information for the cells. My first attempt was to create a function accepting a tuple of tuples. The function was to be called in the following way;

build_map( ( ( 0,0,0, 1,2,3, 4,5,5 ), .../*8 more rows */ ) )

It quickly turned out that this was a bad idea. Because tuples can be heterogeneous, mixing different types, there is no easy way to iterate through all the entries in a tuple. Specific tuple members are accessed using the . notation, where the first member is .0. While this could have been made to work it would have been very messy and unreadable.

Turns out that defining an array of arrays in rust is really simple and powerful. The code to do declare an array of 9 unsigned integers is

array : [u32; 9];

and to create an array of arrays I just need to wrap the definition inside another array definition

array_of_arrays : [[u32; 9];9];

So the function signature is just;

build_map( rows : [[u32; 9];9] ) -> Map {
    // build the map 
}

The build_map function needs to turn the simple map representation into a set of cells that contain the potential values. The vector of vectors is simply two nested vector definitions with a cell at its lowest level. First I need to setup the 'outer' vector that represents rows and have the outer loop create a vector entry for each row

    let mut cells: Vec<Vec<Cell>> = Vec::new();
    for y in 0..rows.len() {
        let mut new_row: Vec<Cell> = Vec::new();
        // setup the row and it to the row vector
        // ...the inner loop
        cells.push(new_row);
    }

This demonstrates how nice the plain Rust arrays are. Because the length is part of the type, we can use len() to get the array length. ( Coming from a C++ background with raw pointers this feels very luxurious ) The same also works for the nested array in the code segment below.

The other noteworthy language feature is the range operator a..b which produces all the numbers in the range from to a (inclusive) to b (exclusive)

Both the outer vector cells and the inner vector new_row need to be mutable because they both get modified in the loop.

The full function for building the map is;

fn build_map(rows: [[u32; 9]; 9]) -> Map {
    let mut cells: Vec<Vec<Cell>> = Vec::new();
    for y in 0..rows.len() {
        let mut new_row: Vec<Cell> = Vec::new();
        for x in 0..rows[y].len() {
            let value = rows[y][x];
            let mut cell = build_cell(value);
            new_row.push(cell);
        }
        cells.push(new_row);
    }
    Map {
        cells: cells,
    }
}

The final statement in the function constructs and returns the Map object. This makes use of two more Rust features like; the literal instantiation syntax where each field is set with its initial value, and the implicit return value.

The actual cell setup is deferred to its own function build_cell that takes the initial value of the cell as its input and sets up the appropriate potential set. The special case is the 0-value which here means that the cell is unsolved and is not initially set. Note tha

fn build_cell(value: u32) -> Cell {
    let mut cell = Cell {
        potentials: HashSet::new(),
    };
    if value == 0 {
        for number in 1..10 {
            cell.potentials.insert(number);
        }
    } else {
        cell.potentials.insert(value);
    }
    return cell;
}

Displaying the board

I want to be able to view the current state of the board so I can follow the progress of the program. The function takes a map as its argument and iterates through its nested vectors printing the current state of each cell and some spacing to make the board more readable.

fn print_map(map: &Map ) {
    for y in 0..map.cells.len() {
        for x in 0..map.cells[y].len() {
            let buf = if x % 3 == 0 { " " } else { "" };
            print!( "{}{}", buf, resolved_to( &map.cells[y][x]) );
        }
        print!("\n");
        if (y + 1) % 3 == 0 {
            print!("\n");
        }
    }
}

The resolved_to function works out what value the given cell resolves to; if there is only one potential value left, that is the value of the cell. Otherwise the value is still unresolved and we return a 0.

fn resolved_to( cell: &Cell) -> u32 {
    if cell.potentials.len() == 1 {
        return *cell.potentials.iter().next().unwrap();
    } else {
        return 0;
    }
}

The code above is pretty self explanatory except for returning the remaining value. First, we get an iterator to potentials set, next gets the actual value from the iterator, which is an option ( which means it could be None) so we need to unwrap the value to get to the u32. Finally, the iterator returns a reference to the value so it needs to be dereferenced with the *. The whole thing feels a bit clunky and I think there must be a cleaner way for getting the only value from the set.

Impl keyword

So far all of the code has been very procedural. While this works it would make more sense to group functions that operate on same structures together like we can do with classes in typical object oriented languages.

Rust does not allow structs to have methods but we can attach functionality to a structure by using inherent implementation. Inherent implementations are declared using the implkeyword.

impl Cell{
    // methods go here
} 

To convert the resolved_to function into a method on Cell we put it inside an impl Cell block and change the cell references to self.

impl Cell{
    fn resolved_to( &self) -> u32 {
        if self.potentials.len() == 1 {
            return *self.potentials.iter().next().unwrap();
        } else {
            return 0;
        }
    }
}

Now we can call the resolved_to method on the cell. So instead of calling the function,

            print!( "{}{}", buf, resolved_to( &map.cells[y][x]) );

we can now call the method on Cell

            print!( "{}{}", buf, map.cells[y][x].resolved_to() );

In Rust parlance resolved_to is a method on Cell because the method is associated with a Cell structure that is passed in as the self argument. The impl block can also have associated functions which are functions that do not have a self argument. Typically these would be used for constructors.

We can mnove the build_cell function inside the impl Cell block and rename it new

impl Cell{
    fn new (value: u32) -> Cell {
        // .. the code is the same as it was inside build_cell
    }
    //... rest of Cell
}

We should also do the same to the functions constructing and printing the map.

I am going to leave the actual solving for my next post.