sudoku_rust/

lib.rs

use rand::Rng;

pub const N: usize = 9;
pub const SRN: usize = 3;

#[derive(Clone, Copy)]
pub struct Cell {
    pub num: u8,
    pub locked: bool,
}
type Grid = [[Cell; N]; N];

pub struct SudokuBoard {
    pub cells: Grid,
}

impl SudokuBoard {
    /// Create an empty board with all cells "locked"
    pub fn new() -> Self {
        Self {
            cells: [[Cell {
                num: 0,
                locked: true,
            }; N]; N],
        }
    }

    /// Fill board completely with solved state
    pub fn fill(&mut self) {
        self.fill_diagonal();
        self.fill_remaining(0, SRN);
    }

    fn fill_diagonal(&mut self) {
        for i in 0..SRN {
            self.fill_box(i * SRN, i * SRN);
        }
    }

    /// Returns false if given SRN x SRN block contains num.
    pub fn unused_in_box(grid: Grid, row_start: usize, col_start: usize, num: u8) -> bool {
        for i in 0..SRN {
            for j in 0..SRN {
                if grid[row_start + i][col_start + j].num == num {
                    return false;
                }
            }
        }
        return true;
    }

    fn fill_box(&mut self, row: usize, col: usize) {
        let mut rng = rand::thread_rng();
        let mut num: Option<u8> = None;
        for i in 0..SRN {
            for j in 0..SRN {
                while num == None || !Self::unused_in_box(self.cells, row, col, num.unwrap()) {
                    num = Some(rng.gen_range(0..=N as u8));
                }
                self.cells[row + i][col + j].num = num.unwrap();
            }
        }
    }

    /// Check if safe to put in cell
    pub fn check_if_safe(grid: Grid, i: usize, j: usize, num: u8) -> bool {
        num == 0
            || (Self::unused_in_row(grid, i, num)
                && Self::unused_in_col(grid, j, num)
                && Self::unused_in_box(grid, i - i % SRN, j - j % SRN, num))
    }

    pub fn unused_in_row(grid: Grid, i: usize, num: u8) -> bool {
        for j in 0..N {
            if grid[i][j].num == num {
                return false;
            }
        }
        return true;
    }

    pub fn unused_in_col(grid: Grid, j: usize, num: u8) -> bool {
        for i in 0..N {
            if grid[i][j].num == num {
                return false;
            }
        }
        return true;
    }

    /// A recursive function to fill remaining
    /// matrix
    pub fn fill_remaining(&mut self, mut i: usize, mut j: usize) -> bool {
        if j >= N && i < N - 1 {
            i += 1;
            j = 0;
        }
        if i >= N && j >= N {
            return true;
        }
        if i < SRN {
            if j < SRN {
                j = SRN;
            }
        } else if i < N - SRN {
            if j == i / SRN * SRN {
                j += SRN;
            }
        } else {
            if j == N - SRN {
                i += 1;
                j = 0;
                if i >= N {
                    return true;
                }
            }
        }

        for num in 1..=N as u8 {
            if Self::check_if_safe(self.cells, i, j, num) {
                self.cells[i][j].num = num;
                self.cells[i][j].locked = true;
                if self.fill_remaining(i, j + 1) {
                    return true;
                }
                self.cells[i][j].num = 0;
                self.cells[i][j].locked = false;
            }
        }

        false
    }

    /// Get the amount of unique solutions a board has
    pub fn solve(mut grid: Grid, mut counter: u32) -> u32 {
        let mut row = 0;
        let mut col = 0;
        for i in 0..81 {
            row = i / N;
            col = i % N;
            if grid[row][col].num == 0 {
                for num in 1..10 {
                    // Check if it is safe to place
                    // the num (1-N)  in the
                    // given row ,col ->we move to next column
                    if Self::check_if_safe(grid, row, col, num) {
                        /*  assigning the num in the current
                        (row,col)  position of the grid and
                        assuming our assigned num in the position
                        is correct */
                        grid[row][col].num = num;
                        grid[row][col].locked = true;
                        if Self::check_filled(grid) {
                            counter += 1;
                            break;
                        } else {
                            // Checking for next
                            // possibility with next column
                            return Self::solve(grid, counter);
                        }
                    }
                    /* removing the assigned num , since our
                    assumption was wrong , and we go for next
                    assumption with diff num value   */
                }
                break;
            }
        }
        grid[row][col].num = 0;
        grid[row][col].locked = false;
        return counter;
    }

    /// Check if the board has no mistakes
    pub fn check_valid(mut grid: Grid) -> bool {
        for i in 0..N {
            for j in 0..N {
                let original = grid[i][j].num;
                grid[i][j].num = 0;
                if !Self::check_if_safe(grid, i, j, original) {
                    return false;
                }
                grid[i][j].num = original;
            }
        }
        true
    }

    /// Check if the board is solved
    pub fn check_solved(grid: Grid) -> bool {
        Self::check_filled(grid) && Self::check_valid(grid)
    }

    /// Check if the board is completely filled
    pub fn check_filled(grid: Grid) -> bool {
        for row in 0..N {
            for col in 0..N {
                if grid[row][col].num == 0 {
                    return false;
                }
            }
        }

        true
    }

    /// Remove cells from the filled solved board to make a puzzle
    pub fn remove_cells(&mut self, mut attempts: u32) {
        let mut rng = rand::thread_rng();

        while attempts > 0 {
            // Select a random cell that is not already empty
            let mut row = rng.gen_range(0..N);
            let mut col = rng.gen_range(0..N);
            while self.cells[row][col].num == 0 {
                row = rng.gen_range(0..N);
                col = rng.gen_range(0..N);
            }

            //Remember its cell value in case we need to put it back
            let backup = self.cells[row][col].clone();
            self.cells[row][col].num = 0;
            self.cells[row][col].locked = false;

            // Take a full copy of the grid
            let copy_grid = self.cells.clone();

            let counter = Self::solve(copy_grid, 0);
            // Count the number of solutions that this grid has (using a backtracking approach implemented in the solveGrid() function)
            //If the number of solution is different from 1 then we need to cancel the change by putting the value we took away back in the grid
            if counter != 1 {
                self.cells[row][col] = backup;
                //We could stop here, but we can also have another attempt with a different cell just to try to remove more numbers
                attempts -= 1;
            }
        }
    }

    /// Display the board in stdout
    pub fn display(&self) {
        Self::display_grid(&self.cells);
    }

    /// Display grid in stdout
    pub fn display_grid(grid: &Grid) {
        println!(
            "{}",
            grid.map(|a| {
                a.map(|a| match a.num {
                    0 => " ".to_string(),
                    _ => a.num.to_string(),
                })
                .join(" ")
            })
            .join("\n")
        );
    }
}

#[cfg(test)]
mod tests {
    use crate::{SudokuBoard, N};

    #[test]
    fn check_solved() {
        let mut board = SudokuBoard::new();
        board.fill();
        assert!(SudokuBoard::check_solved(board.cells));

        board.cells[0][0].num = N as u8 - board.cells[0][0].num;
        assert!(!SudokuBoard::check_solved(board.cells));

        board.cells[0][0].num = 0;
        assert!(!SudokuBoard::check_solved(board.cells));
        assert!(SudokuBoard::check_valid(board.cells));
    }
}