A DFS sudoku solver

This is my attempt at a Sudoku solver using a DFS approach.

I mainly developed it to become a better Rust developer, but if you have any performance tips, I will be glad to hear them :)

My program works for any dim > 1, but these take a long time to calculate. You may wish to limit running the code to 2 or 3 dimensions.

Here are some inputs you can use to test it. If my program returns the original sudoku, then there are no solutions.

9 x x x 7 x 6 8 1 x x x x x 6 x 4 x x 3 x x x x x x 9 x 6 x x x 1 5 x 7 x x x x x x x x x 8 x 3 7 x x x 1 x 1 x x x x x x 3 x x 9 x 6 x x x x x 3 5 2 x 1 x x x 4


x x x 9 x x 4 x x x x x x x 4 5 7 x 7 x x 3 x x x 1 2 1 x x x x x 2 4 x x 9 8 x x x 1 3 x x 3 4 x x x x x 5 5 2 x x x 6 x x 8 x 6 7 8 x x x x x x x 3 x x 1 x x x


x x 1 x 6 8 5 2 x x x x 2 x x x x 1 x x 2 5 1 9 x 3 x x x 8 x 2 4 7 x x 6 x 4 x x x 3 x 2 x x 7 3 8 x 9 x x x 9 x 1 3 5 2 x x 4 x x x x 6 x x x x 8 5 4 7 x 6 x x


Here's my code:

```
#[macro_use]
extern crate text_io;

use std::io;

// struct to represent a sudoku
struct Sudoku {
size: u32,
board: Vec>,
}

fn generate_sudoku(size: u32) -> Sudoku {
let dim = (size * size) as usize;
let mut sudoku = Sudoku {
size: size,
board: Vec::new(),
};

// fill the sudoku with the specified values
for row in 0..dim {
sudoku.board.push(Vec::new());
for _ in 0..dim {
let num: String = read!();
let mut is_number = true;

for ch in num.chars() {
if !ch.is_digit(10) {
is_number = false;
break;
}
}

let number = if is_number {
let num = num.parse::().expect("Not a number! Aborting...");
if num > (dim as u32) { 0 } else { num }
} else {
0
};

sudoku.board[row].push(number);
}
}

sudoku
}

// helper function to determine whether

-
Embrace even more static analysis tools, such as clippy. It provides warnings like:

warning: unneeded return statement
--> src/main.rs:120:5
|
120 | return false;
| ^^^^^^^^^^^^^
|


warning: this expression borrows a reference that is immediately dereferenced by the compiler
--> src/main.rs:111:21
|
111 | if is_valid(&sudoku, try_num as u32, row, column) {
| ^^^^^^^
|


-
Some of your documentation isn't useful: "struct to represent a sudoku" before struct Sudoku doesn't add anything.

-
All of the functions should be methods on Sudoku. Taking a struct as the first argument is a big hint.

-
Why check all the characters of input to see if it's a number, but then parse it and fail anyway? Just check the result of parsing and fallback to 0 on failure.

-
Any time you have a loop creating things for a Vec, try to use collect. It's more efficient, has less code, is more expressive and reduces the need for mutability.

-
Might as well make tiny helper to calculate the dimension.

-
Use iterators, specifically Iterator::any instead of the for loop.

-
Why create check_column but then potentially return early without ever using it? Create it right before it's used?

-
Actually, there's no need to create check_column at all, just us emore iterators.

-
Could use Itertools' cartesian product iterator adapter instead of nesting two for loops.

-
Use consistent ways of reading input.

#[macro_use]
extern crate text_io;

struct Sudoku {
size: u32,
board: Vec>,
}

fn dim(size: u32) -> usize {
(size * size) as _
}

impl Sudoku {
fn new(size: u32) -> Sudoku {
let dim = dim(size);

let board = (0..dim).map(|_| {
(0..dim).map(|_| {
let num: String = read!();
num.parse::().unwrap_or(0)
}).collect()
}).collect();

Sudoku {
size: size,
board: board,
}
}

// helper function to determine whether a number is valid
fn is_valid(&self, num: u32, row: usize, column: usize) -> bool {
// check the row
if self.board[row].iter().any(|&value| value == num) {
return false;
}

// check the column
if self.board.iter().any(|row| row[column] == num) {
return false;
}

// check the box
let box_row = (self.size * ((row as u32) / self.size)) as usize;
let box_column = (self.size * ((column as u32) / self.size)) as usize;

for i in box_row..box_row + (self.size as usize) {
for j in box_column..box_column + (self.size as usize) {
if self.board[i][j] == num {
return false;
}
}
}

true
}

fn solve(&mut self, mut row: usize, mut column: usize) -> bool {
let dim = dim(self.size);

if column == dim {
row += 1;
column = 0;
}

// solved!
if row == dim {
return true;
}

// skip tip values
if self.board[row][column] > 0 {
return self.solve(row, column + 1);
}

// guess number in cell
for try_num in 1..(dim + 1) {
if self.is_valid(try_num as u32, row, column) {
self.board[row][column] = try_num as u32;
if self.solve(row, column + 1) {
return true;
}
}
}

self.board[row][column] = 0;
false
}
}

fn main() {
println!("Enter the size of your sudoku (typically 3).");
let size: String = read!();

let size: u32 = match size.trim().parse() {
Ok(num) if num > 1 => num,
Ok(_) => {
panic!("Number too small! The number must be greater than 1! Aborting...");
}
Err(_) => {
panic!("Not a number! Aborting...");
}
};

let mut sudoku = Sudoku::new(size);
sudoku.solve(0, 0);
println!("=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-");
for row in sudoku.board {
for column in row {
print!("{} ", column);
}
println!();
}
}


StackExchange Code Review Q#161138, answer score: 2