Simple Sudoku Solver in Rust - part 2

In my last post I setup all the data structures for representing the sudoku board so now it is time to write the actual sudoku solver.

Initial Constraints

First, I need a list of constraints that are applied to the map in order to solve other cells. At the beginning this set of constraints is given by the starting values in the map.

Each constraint has a map location and value, so the constraint, which really is a solved cell, should look like

struct SolvedCell {
    x: u32,
    y: u32,
    value: u32,
}

I want to add these constraints into a queue as I discover them and remove them from the queue as they are applied to the map. The natural container for this is a double ended queue, or a deque. Rust has VecDeque that provides the capabilities your would expect to find in a deque.

These constraints are associated with the map, so the deque should be art of the Map structure

struct Map {
    cells: Vec<Vec<Cell>>,
    solved_cells: VecDeque<SolvedCell>,     // keeps track of new solved cells
}

The initial list of solved cells can be constructed when the rest of the map data is set up in the Map constructor. The constructor needs to record all of the cells with a non-zero starting value. The following lines need to be added to the constructor

impl Map{
    fn new(rows: [[u32; 9]; 9]) -> Map {
        // initial solved cells
        let mut solved_cells = VecDeque::new();
        //...
                // inside the inner loop, add all solved cells to the deque
                if value != 0 {
                    solved_cells.push_back(SolvedCell {
                        x: x as u32,
                        y: y as u32,
                        value: value,
                    });
                }
        //..
        // setup the solved cells in the initializer                
        Map {
            // ..
            solved_cells : solved_cells
        }
    }

Looping

Now we can write the code for actually doing the solving. On the top level we create a new solve on Map that applies constraints to the map until it runs out of them. At that point the map is either solved or is unsolvable by the program. The code for solve is below;

impl Map{
    //....
    fn solve(&self) {
        loop {
            let solved = self.solved_cells.pop_front();
            if solved.is_none() {
                break;
            }
            self.reduce_potentials(map, solved.unwrap());
        }
    }
}

The code keeps taking values from the front of the queue until the returned value is none. If there is a value it handles it in reduce_potentials.

This uses the Rust keyword loop to setup an infinite loop that can be only be broken out with a break statement. I rather like this syntax, as it is equivalent of doing for(;;){...} in C++ but there it always felt like a failure to come up with the right loop condition. Because Rust has a specific keyword for the infinite loop, I think, it encourages clearer thinking about the loop and its stopping condition.

Note that I did not need to declare the type of solved at any point. As long as the type returned from solved_cells is compatible with the argument required by reduce_potentials Rust is happy.

Applying constraints

The reduce_potentials method identifies all cells effected by the solved cell and reduces the potential set of values for all of them. As I described in the first post, the set of potential values is reduced for all cells on the same vertical and horizontal axis and that are in the same 3x3 sub-map.

    fn reduce_potentials(&mut self, solved: SolvedCell) {
        // horizontal
        for x in 0..9 {
            self.reduce_cell_potentials( x, solved.y, solved.value );
        }
        // vertical
        for y in 0..9 {
            self.reduce_cell_potentials( solved.x, y, solved.value );
        }
        // square
        let sq_x: u32 = (solved.x / 3) * 3;
        let sq_y: u32 = (solved.y / 3) * 3;
        for y in 0..3 {
            for x in 0..3 {
                self.reduce_cell_potentials( sq_x+x, sq_y+y, solved.value );
            }
        }
    }

The final missing piece is the reduce_cell_potentials which removes the given value from the set of possible values the cell can take. I also want to print the map every time a new cell has been solved so I can follow the progress.

    fn reduce_cell_potentials( &mut self, x : u32, y : u32, value : u32 ) {
        let num_solutions = self.solved_cells.len();
        {
            let cell: &mut Cell = &mut self.cells[y as usize][x as usize];
            if !(cell.is_solved()) {
                cell.reduce_potentials(value);
                if cell.is_solved() {
                    // the last operation solved the cell
                    self.solved_cells.push_back(SolvedCell {
                        x: x,
                        y: y,
                        value: cell.resolved_to(),
                    })
                }
            }
        }
        if num_solutions != self.solved_cells.len() {
            self.print(  );
        }
    }

There is a strange scope from line 3 to 16 that looks unnecessary. This is required by the borrow-checker because on line 4 the code creates a mutable borrow to a cell which is inside self. While this reference is held no other references can be created to self which would happen on calling any method on Map. The scope ensures that cell has been given back when we call print.

I am in two minds about the need for the scope; It looks odd and it is not easy to understand why it is needed by just reading the code. On the other hand it does suggest that maybe the code is not structured as well as it could be, it is mixing cell state management and drawing. I think this will behaviour will go away with the non-lexical scopes. The compiler was remarkably helpful in pointing out the problem.

This will now successfully solve simple sudoku puzzles. I have uploaded the code to GitHub at https://github.com/janiorca/articles/tree/master/sudoku-2