Simple Sudoku solver in Rust

Question

This is my little Sudoku solver in Rust. It iterates through empty cells and checks which numbers are absent from the corresponding row, column, and square. If there is one possible candidate, it fills in the answer and moves on to the next empty cell.

Clearly I should be reading from an input rather than hard-coding the puzzle. What other ways can I improve the readability and make it more idiomatic?

type Cell = (usize, usize);
struct Grid {
 data: [[u8; 9]; 9],
 current: Cell,
}
impl Grid {
 // Search possible candidates for a given cell.
 // If one candidate exists, return it.
 fn check(&mut self, cell: Cell) -> Option<u8> { 
 let mut candidates = [true; 9];
 for i in 1..10 {
 candidates[i-1] &= self.check_row(cell, i as u8);
 candidates[i-1] &= self.check_column(cell, i as u8);
 candidates[i-1] &= self.check_square(cell, i as u8);
 }
 if candidates.iter().fold(0, |acc, &x| acc + x as i32) == 1 {
 return Some(candidates.iter()
 .position(|&x| x == true)
 .unwrap() as u8 + 1);
 }
 None
 }
 fn check_row(&self, cell: Cell, num: u8) -> bool {
 let row = self.data[cell.0];
 for i in row.iter() {
 if *i == num { return false; }
 }
 true
 }
 fn check_column(&self, cell: Cell, num: u8) -> bool {
 for row in self.data.iter() {
 if row[cell.1] == num { return false; }
 }
 true
 }
 fn check_square(&self, cell: Cell, num: u8) -> bool {
 let mut square: (usize, usize) = (cell.0 / 3, cell.1 / 3);
 square.0 *= 3;
 square.1 *= 3;
 for row in (square.0)..(square.0 + 3) {
 for column in (square.1)..(square.1 + 3) {
 if self.data[row][column] == num { return false; }
 }
 }
 true
 }
}
// Iterate through empty cells.
impl Iterator for Grid {
 type Item = Cell;
 fn next(&mut self) -> Option<Self::Item> {
 let starting_point = (self.current.0, self.current.1);
 loop {
 self.current.0 = (self.current.0 + 1)%9;
 if self.current.0 == 0 {
 self.current.1 = (self.current.1 + 1)%9;
 }
 if (self.current.0, self.current.1) == starting_point {
 return None;
 }
 if self.data[self.current.0][self.current.1] == 0 { break }
 }
 Some(self.current)
 }
}
fn main () {
 let mut grid = Grid {
 data: [ [1,6,4,0,0,0,0,0,2],
 [2,0,0,4,0,3,9,1,0],
 [0,0,5,0,8,0,4,0,7],
 [0,9,0,0,0,6,5,0,0],
 [5,0,0,1,0,2,0,0,8],
 [0,0,8,9,0,0,0,3,0],
 [8,0,9,0,4,0,2,0,0],
 [0,7,3,5,0,9,0,0,1],
 [4,0,0,0,0,0,6,7,9] ],
 current: (0, 0),
 };
 loop {
 if let None = grid.next() { break; }
 let empty_cell = grid.current;
 match grid.check(empty_cell) {
 Some(i) => {
 grid.data[empty_cell.0][empty_cell.1] = i;
 },
 None => continue,
 }
 }
 for row in grid.data.iter() {
 println!("{:?}", row);
 }
}

Answer 1

General

1. Run clippy. It will automatically tell you such things as:

   • equality checks against true are unnecessary

      --> src/main.rs:20:57
      |
     20 | return Some(candidates.iter().position(|&x| x == true).unwrap() as u8 + 1);
      | ^^^^^^^^^ 
     

   • it is more idiomatic to loop over references to containers instead of using explicit iteration methods

      --> src/main.rs:26:18
      |
     26 | for i in row.iter() {
      | ^^^^^^^^^^ help: to write this more concisely, try: `&row`
     

   • redundant pattern matching, consider using is_none()

      --> src/main.rs:97:16
      |
     97 | if let None = grid.next() {
      | -------^^^^-------------- help: try this: `if grid.next().is_none()`
     

2. Cell is a name of a type in the standard library, so I was a bit confused to start with. Not sure of a better name.

main

1. Use while or while let instead of a loop.

2. The continue is not useful, it's at the end of the block. Switch to an if let instead.

3. Why isn't the return value of your iterator used? Why don't you use that instead of getting grid.current?

4. Why is grid.current even part of the grid in the first place?

Grid

1. If you want to document a function, use ///, not //.

2. Don't cast booleans as a number. I'm honestly surprised this even compiles. Instead, count the true values

3. Memorize all the available Iterator methods. In this case, any and all are valuable.

Grid::check_square

1. There's no need to specify the type of square.

2. I don't think it's useful to cram the square data into a tuple. Instead, whip up a little closure to perform the same work.

3. I like Itertools. Here, I use its cartesian_product.

extern crate itertools;
use itertools::Itertools;
type Cell = (usize, usize);
struct Grid {
 data: [[u8; 9]; 9],
 current: Cell,
}
impl Grid {
 /// Search possible candidates for a given cell.
 /// If one candidate exists, return it.
 fn check(&mut self, cell: Cell) -> Option<u8> {
 let mut candidates = [true; 9];
 for i in 1..10 {
 candidates[i - 1] &= self.check_row(cell, i as u8);
 candidates[i - 1] &= self.check_column(cell, i as u8);
 candidates[i - 1] &= self.check_square(cell, i as u8);
 }
 if candidates.iter().filter(|&&x| x).count() == 1 {
 return Some(candidates.iter().position(|&x| x).unwrap() as u8 + 1);
 }
 None
 }
 fn check_row(&self, cell: Cell, num: u8) -> bool {
 self.data[cell.0].iter().all(|&i| i != num)
 }
 fn check_column(&self, cell: Cell, num: u8) -> bool {
 self.data.iter().all(|row| row[cell.1] != num)
 }
 fn check_square(&self, cell: Cell, num: u8) -> bool {
 let truncated_range_of_3 = |x| {
 let start = (x / 3) * 3;
 start..start + 3
 };
 let rows = truncated_range_of_3(cell.0);
 let cols = truncated_range_of_3(cell.1);
 rows.cartesian_product(cols).all(|(row, col)| self.data[row][col] != num)
 }
}
/// Iterate through empty cells.
impl Iterator for Grid {
 type Item = Cell;
 fn next(&mut self) -> Option<Self::Item> {
 let starting_point = (self.current.0, self.current.1);
 loop {
 self.current.0 = (self.current.0 + 1) % 9;
 if self.current.0 == 0 {
 self.current.1 = (self.current.1 + 1) % 9;
 }
 if (self.current.0, self.current.1) == starting_point {
 return None;
 }
 if self.data[self.current.0][self.current.1] == 0 {
 break;
 }
 }
 Some(self.current)
 }
}
fn main() {
 let mut grid = Grid {
 data: [
 [1, 6, 4, 0, 0, 0, 0, 0, 2],
 [2, 0, 0, 4, 0, 3, 9, 1, 0],
 [0, 0, 5, 0, 8, 0, 4, 0, 7],
 [0, 9, 0, 0, 0, 6, 5, 0, 0],
 [5, 0, 0, 1, 0, 2, 0, 0, 8],
 [0, 0, 8, 9, 0, 0, 0, 3, 0],
 [8, 0, 9, 0, 4, 0, 2, 0, 0],
 [0, 7, 3, 5, 0, 9, 0, 0, 1],
 [4, 0, 0, 0, 0, 0, 6, 7, 9],
 ],
 current: (0, 0),
 };
 while let Some(_) = grid.next() {
 let empty_cell = grid.current;
 if let Some(i) = grid.check(empty_cell) {
 grid.data[empty_cell.0][empty_cell.1] = i;
 }
 }
 for row in &grid.data {
 println!("{:?}", row);
 }
}

That unwrap bothers me, but I'm not sure that this is really clearer:

let mut x = candidates.iter().enumerate().filter_map(|(pos, &check)| {
 if check { Some(pos as u8 + 1) } else { None }
}).fuse();
match (x.next(), x.next()) {
 (Some(pos), None) => Some(pos),
 _ => None,
}

It can be made much nicer by abandoning the array at all. This saves (a tiny bit of) stack space but also probably speeds up the program (by a tiny amount) — the function exits as soon as a second possibility is found:

fn check(&mut self, cell: Cell) -> Option<u8> {
 let mut possibilities = (1..10)
 .filter(|&i| self.check_row(cell, i))
 .filter(|&i| self.check_column(cell, i))
 .filter(|&i| self.check_square(cell, i))
 .fuse();
 match (possibilities.next(), possibilities.next()) {
 (Some(pos), None) => Some(pos),
 _ => None,
 }
}

Good news! My version of the code passes every single test case you provided!