## Friday 11 January 2019

### 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