A DFS sudoku solver

Question

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<Vec<u32>>,
}



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::<u32>().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 a number is valid
fn is_valid(sudoku: &Sudoku, num: u32, row: usize, column: usize) -> bool {
    let dim = (sudoku.size * sudoku.size) as usize;
    let mut check_column = Vec::new();
    for i in 0..dim {
        check_column.push(sudoku.board[i][column]);
    }

    // check the row
    for value in &sudoku.board[row] {
        if *value == num {
            return false;
        }
    }

    // check the column
    for value in &check_column {
        if *value == num {
            return false;
        }
    }

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

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

    true
}



fn solve_sudoku(mut sudoku: &mut Sudoku, mut row: usize, mut column: usize) -> bool {
    let dim = (sudoku.size * sudoku.size) as usize;

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

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

    // skip tip values
    if sudoku.board[row][column] > 0 {
        return solve_sudoku(&mut sudoku, row, column + 1);
    }

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

    sudoku.board[row][column] = 0;
    return false;
}



fn main() {
    println!("Enter the size of your sudoku (typically 3).");
    let mut size = String::new();
    io::stdin()
        .read_line(&mut size)
        .expect("Failed to read line!");

    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 = generate_sudoku(size);
    solve_sudoku(&mut sudoku, 0, 0);
    println!("=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-");
    for row in sudoku.board {
        for column in row {
            print!("{} ", column);
        }
        println!();
    }
}

Answer 1

1. 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) {
       |                     ^^^^^^^
       |
   

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

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

4. 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.

5. 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.

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

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

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

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

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

11. Use consistent ways of reading input.

#[macro_use]
extern crate text_io;

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

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::<u32>().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!();
    }
}