DFS sudoku解算器

Question

这是我使用DFS方法在Sudoku解决程序上的尝试。

我开发它主要是为了成为一个更好的Rust开发人员，但是如果您有任何性能技巧，我会很高兴听到它们:)

我的程序适用于任何一个dim > 1，但是这些都需要很长的时间来计算。您可能希望将代码运行限制在2或3维。

下面是一些您可以用来测试它的输入。如果我的程序返回原来的sudoku，那么就没有解决方案了。

9 x7 x6 8 1 x6 x4 x4 x3 x6 x5 x7 x 8 x7 x1 x3 x 9 x9 x 6 x5 2 x1 x 4 x9 x 4 x5 7 x 3 x1 1 x2 x 9 8 x 9 x 7 xX 1 3 x3 4 x 5 5 2 x6 x 8 x 6 7 8 x3 x 1 x 1 x6 8 2 x2 x 1 x 2 x5 1 9 x3 x 8 x4 7 x6 x6 x 4 x3 x 7 8 x9 x 9 x 4 x6 x6 x 8 x5 4 x 6 x 6 x

这是我的密码：

#[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. 使用更多的静态分析工具，如克里皮。它提供了如下警告:警告:不需要的返回语句-> src/main.rs: 120 :5酶切120返回假；\^警告:该表达式借用编译器立即取消引用的引用-> src/main.rs: 111 :21 x\111，如果is_valid(&sudoku，try_num as u32，行，列){^__{^
2. 在struct Sudoku不添加任何内容之前，您的一些文档是没有用的："struct来表示sudoku“。
3. 所有函数都应该是Sudoku上的方法。把结构作为第一个参数是一个很大的暗示。
4. 为什么要检查输入的所有字符，看看它是否是一个数字，然后解析它，然后失败呢？只需检查解析结果，并在失败时返回到0。
5. 当您有一个为Vec创建东西的循环时，请尝试使用collect。它效率更高，代码更少，更有表现力，并且减少了对易变性的需求。
6. 还不如做个小帮手来计算尺寸。
7. 使用迭代器，特别是Iterator::any，而不是for循环。
8. 为什么要创建check_column，但可能会在没有使用它的情况下提前返回呢？在它被使用之前创建它？
9. 实际上，根本不需要创建check_column，只需要创建更多的迭代器。
10. 可以使用Itertools的笛卡尔积迭代器适配器而不是嵌套两个for循环。
11. 使用一致的阅读输入方式。

#[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!();
    }
}