Camilo MATAJIRA

Sudoku solver in Rust (part 2)

Camilo MATAJIRA Avatar
Camilo MATAJIRA

This is the follow up to https://camilo.matajira.com/?p=673.
Back then I struggled to implement my “usual” solution to sudoku puzzles. My key pain point was working with a struct (a Cell) that has “references” to itself (next Cell) and to the head of the “linked list”.

Approaching the problem like this worked in Java, Python and Javascript (if I recall correctly) but not in Rust. To satisfy the compiler, I had to keep the state in a 2d array (outside the Cells), and just use the Cells as “relatively” dumb structs that are chained together to transverse easily the puzzle.

With this modification, the code compiled. I also added command line argument parsing with clap, and parsing of puzzles via files or stding with serde_json.

The code is the following:

use std::collections::HashSet;
const SUDOKU_MAX_NUMBER: usize = 9;

use clap::Parser;
use serde_json;
use std::fs;
use std::io::Read;

#[derive(Parser)]
struct Cli {
    input_file: Option<String>,
}

fn main() {
    let cli = Cli::parse();

    match cli.input_file {
        Some(ref input_file) => {
            process_input_file(input_file);
        }
        None => {
            process_stdin();
        }
    }
}

fn solve(initial_conditions: &mut [[usize; 9]; 9]) {
    let mut cell_00 = initialize_cells(&initial_conditions);
    let result = cell_00.solve(initial_conditions);
    match result {
        Ok(_) => {
            for i in initial_conditions {
                let serialized_row = serde_json::to_string(&i).unwrap();
                println!("{}", serialized_row);
            }
        }
        Err(error) => {
            println!("{}", error);
        }
    }
}

fn process_input_file(input_file: &String) {
    let buffer_result = fs::read_to_string(input_file);
    match buffer_result {
        Err(_) => {
            eprintln!("Could not read file: {}", input_file);
            std::process::exit(1);
        }
        Ok(buffer) => {
            let mut initial_conditions = parse_initial_conditions(buffer);
            solve(&mut initial_conditions);
        }
    }
}

fn process_stdin() {
    let mut buffer_try = String::new();
    std::io::stdin()
        .read_to_string(&mut buffer_try)
        .expect("paila");
    let mut initial_conditions = parse_initial_conditions(buffer_try);
    solve(&mut initial_conditions);
}

fn parse_initial_conditions(initial_text: String) -> [[usize; 9]; 9] {
    let parsed: Result<[[usize; 9]; 9], serde_json::Error> = serde_json::from_str(&initial_text);
    match parsed {
        Ok(initial_conditions) => return initial_conditions,
        Err(error) => {
            eprintln!("Problems parsing the Sudoku puzzle");
            let initial_text = "[
[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4, 1, 9, 0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9]
]";
            eprintln!("Input file or stdin should have this format:");
            eprintln!("{}", initial_text);
            eprintln!("Parser error: {}", error);
            std::process::exit(1);
        }
    };
}

struct Cell {
    i: usize,
    j: usize,
    next: Option<Box<Cell>>,
    is_fixed: bool,
}

fn get_set_from_column(i: usize, sudoku: &[[usize; 9]; 9]) -> Result<HashSet<usize>, String> {
    let mut answer = HashSet::new();
    if i > SUDOKU_MAX_NUMBER - 1 {
        return Err("i must be between 0 and 8".into());
    } else {
        for j in 0..SUDOKU_MAX_NUMBER {
            answer.insert(sudoku[j][i]);
        }
        return Ok(answer);
    }
}
fn get_set_from_row(j: usize, sudoku: &[[usize; 9]; 9]) -> Result<HashSet<usize>, String> {
    let mut answer = HashSet::new();
    if j > SUDOKU_MAX_NUMBER - 1 {
        return Err("i must be between 0 and 8".into());
    } else {
        for i in 0..SUDOKU_MAX_NUMBER {
            answer.insert(sudoku[j][i]);
        }
        return Ok(answer);
    }
}

fn get_set_from_sub_matrix_ij(
    i: usize,
    j: usize,
    sudoku: &[[usize; 9]; 9],
) -> Result<HashSet<usize>, String> {
    let mut answer = HashSet::new();
    if i > SUDOKU_MAX_NUMBER - 1 || j > SUDOKU_MAX_NUMBER - 1 {
        return Err("only valid for the head".into());
    } else {
        let original_quadrant = get_quadrant_from_ij(i, j);
        for x in 0..SUDOKU_MAX_NUMBER {
            for y in 0..SUDOKU_MAX_NUMBER {
                if get_quadrant_from_ij(x, y) == original_quadrant {
                    answer.insert(sudoku[x][y]);
                }
            }
        }
        return Ok(answer);
    }
}
fn is_a_good_candidate_for_column(i: usize, candidate: usize, sudoku: &[[usize; 9]; 9]) -> bool {
    let values_column = get_set_from_column(i, &sudoku).unwrap();
    !values_column.contains(&candidate)
}

fn is_a_good_candidate_for_row(j: usize, candidate: usize, sudoku: &[[usize; 9]; 9]) -> bool {
    let values_row = get_set_from_row(j, &sudoku).unwrap();
    !values_row.contains(&candidate)
}
fn is_a_good_candidate_for_sub_matrix(
    i: usize,
    j: usize,
    candidate: usize,
    sudoku: &[[usize; 9]; 9],
) -> bool {
    let values_quadrant_ij = get_set_from_sub_matrix_ij(i, j, &sudoku).unwrap();
    !values_quadrant_ij.contains(&candidate)
}

impl Cell {
    fn solve(&mut self, sudoku: &mut [[usize; 9]; 9]) -> Result<String, String> {
        match self.next {
            Some(_) => {}
            None => return Ok("Solved".into()),
        }
        if self.is_fixed {
            let next_cell_solve_result = self.solve_next(sudoku);
            match next_cell_solve_result {
                Ok(solution) => return Ok(solution),
                Err(e) => return Err(e),
            }
        } else {
            for candidate in 1..SUDOKU_MAX_NUMBER + 1 {
                if is_a_good_candidate_for_column(self.j, candidate, sudoku)
                    && is_a_good_candidate_for_row(self.i, candidate, sudoku)
                    && is_a_good_candidate_for_sub_matrix(self.i, self.j, candidate, sudoku)
                {
                    sudoku[self.i][self.j] = candidate;
                    let next_cell_solve_result = self.solve_next(sudoku);
                    match next_cell_solve_result {
                        Ok(solution) => return Ok(solution),
                        Err(_) => {

                            // println!(
                            //     "{}{} candidate {} is bad, backtracking",
                            //     self.i, self.j, candidate
                            // );
                        }
                    }
                } else {
                    continue;
                }
            }
            sudoku[self.i][self.j] = 0;
            // println!("{}{} ran out of options", self.i, self.j);
            return Err("Go back!".into());
        }
    }
    fn solve_next(&mut self, sudoku: &mut [[usize; 9]; 9]) -> Result<String, String> {
        self.next.as_mut().unwrap().solve(sudoku)
    }
}

#[derive(PartialEq, Debug)]
enum SubMatrixQuadrant {
    Quadrant1,
    Quadrant2,
    Quadrant3,
    Quadrant4,
    Quadrant5,
    Quadrant6,
    Quadrant7,
    Quadrant8,
    Quadrant9,
}

fn get_quadrant_from_ij(x: usize, y: usize) -> SubMatrixQuadrant {
    match (x, y) {
        (x, y) if x < 3 && y < 3 => SubMatrixQuadrant::Quadrant1,
        (x, y) if x < 3 && y >= 3 && y < 6 => SubMatrixQuadrant::Quadrant2,
        (x, y) if x < 3 && y >= 6 => SubMatrixQuadrant::Quadrant3,
        (x, y) if x >= 3 && x < 6 && y < 3 => SubMatrixQuadrant::Quadrant4,
        (x, y) if x >= 3 && x < 6 && y >= 3 && y < 6 => SubMatrixQuadrant::Quadrant5,
        (x, y) if x >= 3 && x < 6 && y >= 6 => SubMatrixQuadrant::Quadrant6,
        (x, y) if x >= 6 && y < 3 => SubMatrixQuadrant::Quadrant7,
        (x, y) if x >= 6 && y >= 3 && y < 6 => SubMatrixQuadrant::Quadrant8,
        (x, y) if x >= 6 && y >= 6 => SubMatrixQuadrant::Quadrant9,
        (_, _) => SubMatrixQuadrant::Quadrant9,
    }
}
fn initialize_cells(&initial_conditions: &[[usize; 9]; 9]) -> Box<Cell> {
    let mut cell_00 = Box::new(Cell {
        i: 0,
        j: 0,
        next: None,
        is_fixed: initial_conditions[0][0] > 0,
    });
    let mut previous_cell = &mut cell_00;
    for (i, row_i) in initial_conditions.iter().enumerate() {
        for (j, value_j) in row_i.iter().enumerate() {
            if i == 0 && j == 0 {
                continue;
            }
            let is_fixed = *value_j > (0 as usize);
            let new_cell = Box::new(Cell {
                i: i,
                j: j,
                is_fixed: is_fixed,
                next: None,
            });
            previous_cell.next = Some(new_cell);
            previous_cell = previous_cell.next.as_mut().unwrap();
        }
    }
    return cell_00;
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_cell() {
        let test_1 = Cell {
            i: 0,
            j: 1,
            next: None,
            is_fixed: false,
        };
        assert_eq!(test_1.i, 0);
        assert_eq!(test_1.j, 1);
    }
    #[test]
    fn test_cell_next_cell() {
        let test_2 = Box::new(Cell {
            i: 0,
            j: 1,
            next: None,
            is_fixed: false,
        });
        let test_1 = Box::new(Cell {
            i: 0,
            j: 0,
            next: Some(test_2),
            is_fixed: false,
        });
        let Some(_next) = test_1.next else { panic!() };
    }
    #[test]
    fn test_initialize() {
        let initial_conditions = [
            [5, 3, 0, 0, 7, 0, 0, 0, 0],
            [6, 0, 0, 1, 9, 5, 0, 0, 0],
            [0, 9, 8, 0, 0, 0, 0, 6, 0],
            [8, 0, 0, 0, 6, 0, 0, 0, 3],
            [4, 0, 0, 8, 0, 3, 0, 0, 1],
            [7, 0, 0, 0, 2, 0, 0, 0, 6],
            [0, 6, 0, 0, 0, 0, 2, 8, 0],
            [0, 0, 0, 4, 1, 9, 0, 0, 5],
            [0, 0, 0, 0, 8, 0, 0, 7, 9],
        ];
        let cell_00 = initialize_cells(&initial_conditions);
        assert_eq!(cell_00.i, 0);
        assert_eq!(cell_00.j, 0);
        assert_eq!(cell_00.is_fixed, true);

        let cell_01 = cell_00.next.unwrap();
        assert_eq!(cell_01.i, 0);
        assert_eq!(cell_01.j, 1);
        assert_eq!(cell_01.is_fixed, true);

        let cell_02 = cell_01.next.unwrap();
        assert_eq!(cell_02.i, 0);
        assert_eq!(cell_02.j, 2);
        assert_eq!(cell_02.is_fixed, false);

        let cell_03 = cell_02.next.unwrap();
        let cell_04 = cell_03.next.unwrap();
        let cell_05 = cell_04.next.unwrap();
        let cell_06 = cell_05.next.unwrap();
        let cell_07 = cell_06.next.unwrap();
        let cell_08 = cell_07.next.unwrap();
        let cell_10 = cell_08.next.unwrap();
        assert_eq!(cell_10.i, 1);
        assert_eq!(cell_10.j, 0);
        assert_eq!(cell_10.is_fixed, true);
    }

    #[test]
    fn test_get_set_from_column() {
        let initial_conditions = [
            [5, 3, 0, 0, 7, 0, 0, 0, 0],
            [6, 0, 0, 1, 9, 5, 0, 0, 0],
            [0, 9, 8, 0, 0, 0, 0, 6, 0],
            [8, 0, 0, 0, 6, 0, 0, 0, 3],
            [4, 0, 0, 8, 0, 3, 0, 0, 1],
            [7, 0, 0, 0, 2, 0, 0, 0, 6],
            [0, 6, 0, 0, 0, 0, 2, 8, 0],
            [0, 0, 0, 4, 1, 9, 0, 0, 5],
            [0, 0, 0, 0, 8, 0, 0, 7, 9],
        ];
        let answer = HashSet::from([5, 6, 0, 8, 4, 7, 0, 0, 0]);
        assert_eq!(answer, get_set_from_column(0, &initial_conditions).unwrap());
        let answer = HashSet::from([0, 0, 0, 3, 1, 6, 0, 5, 9]);
        assert_eq!(answer, get_set_from_column(8, &initial_conditions).unwrap());
    }
    #[test]
    fn test_get_set_from_row() {
        let initial_conditions = [
            [5, 3, 0, 0, 7, 0, 0, 0, 0],
            [6, 0, 0, 1, 9, 5, 0, 0, 0],
            [0, 9, 8, 0, 0, 0, 0, 6, 0],
            [8, 0, 0, 0, 6, 0, 0, 0, 3],
            [4, 0, 0, 8, 0, 3, 0, 0, 1],
            [7, 0, 0, 0, 2, 0, 0, 0, 6],
            [0, 6, 0, 0, 0, 0, 2, 8, 0],
            [0, 0, 0, 4, 1, 9, 0, 0, 5],
            [0, 0, 0, 0, 8, 0, 0, 7, 9],
        ];

        let answer = HashSet::from([5, 3, 0, 0, 7, 0, 0, 0, 0]);
        assert_eq!(answer, get_set_from_row(0, &initial_conditions).unwrap());
    }
    #[test]
    fn test_get_quadrants() {
        assert_eq!(SubMatrixQuadrant::Quadrant1, get_quadrant_from_ij(0, 0));
        assert_eq!(SubMatrixQuadrant::Quadrant4, get_quadrant_from_ij(3, 0));
        assert_eq!(SubMatrixQuadrant::Quadrant9, get_quadrant_from_ij(8, 8));
        assert_eq!(SubMatrixQuadrant::Quadrant5, get_quadrant_from_ij(4, 4));
    }
    #[test]
    fn test_get_set_from_sub_matrix_ij() {
        let initial_conditions = [
            [5, 3, 0, 0, 7, 0, 0, 0, 0],
            [6, 0, 0, 1, 9, 5, 0, 0, 0],
            [0, 9, 8, 0, 0, 0, 0, 6, 0],
            [8, 0, 0, 0, 6, 0, 0, 0, 3],
            [4, 0, 0, 8, 0, 3, 0, 0, 1],
            [7, 0, 0, 0, 2, 0, 0, 0, 6],
            [0, 6, 0, 0, 0, 0, 2, 8, 0],
            [0, 0, 0, 4, 1, 9, 0, 0, 5],
            [0, 0, 0, 0, 8, 0, 0, 7, 9],
        ];

        let answer = HashSet::from([5, 3, 0, 6, 0, 0, 0, 9, 8]);
        assert_eq!(
            answer,
            get_set_from_sub_matrix_ij(0, 0, &initial_conditions).unwrap()
        );
        let answer = HashSet::from([8, 0, 0, 4, 0, 0, 7, 0, 0]);
        assert_eq!(
            answer,
            get_set_from_sub_matrix_ij(3, 0, &initial_conditions).unwrap()
        );
        let answer = HashSet::from([2, 8, 0, 0, 0, 5, 0, 7, 9]);
        assert_eq!(
            answer,
            get_set_from_sub_matrix_ij(7, 7, &initial_conditions).unwrap()
        );
        let answer = HashSet::from([0, 6, 0, 8, 0, 3, 0, 2, 0]);
        assert_eq!(
            answer,
            get_set_from_sub_matrix_ij(3, 3, &initial_conditions).unwrap()
        );
    }
    #[test]
    fn test_is_a_good_candidate_for_column() {
        let initial_conditions = [
            [5, 3, 0, 0, 7, 0, 0, 0, 0],
            [6, 0, 0, 1, 9, 5, 0, 0, 0],
            [0, 9, 8, 0, 0, 0, 0, 6, 0],
            [8, 0, 0, 0, 6, 0, 0, 0, 3],
            [4, 0, 0, 8, 0, 3, 0, 0, 1],
            [7, 0, 0, 0, 2, 0, 0, 0, 6],
            [0, 6, 0, 0, 0, 0, 2, 8, 0],
            [0, 0, 0, 4, 1, 9, 0, 0, 5],
            [0, 0, 0, 0, 8, 0, 0, 7, 9],
        ];

        assert_eq!(
            is_a_good_candidate_for_column(0, 5, &initial_conditions),
            false
        );
        assert_eq!(
            is_a_good_candidate_for_column(0, 9, &initial_conditions),
            true
        );
        assert_eq!(
            is_a_good_candidate_for_column(0, 3, &initial_conditions),
            true
        );
        assert_eq!(
            is_a_good_candidate_for_column(8, 9, &initial_conditions),
            false
        );
        assert_eq!(
            is_a_good_candidate_for_column(7, 7, &initial_conditions),
            false
        );
    }
    #[test]
    fn test_is_a_good_candidate_for_row() {
        let initial_conditions = [
            [5, 3, 0, 0, 7, 0, 0, 0, 0],
            [6, 0, 0, 1, 9, 5, 0, 0, 0],
            [0, 9, 8, 0, 0, 0, 0, 6, 0],
            [8, 0, 0, 0, 6, 0, 0, 0, 3],
            [4, 0, 0, 8, 0, 3, 0, 0, 1],
            [7, 0, 0, 0, 2, 0, 0, 0, 6],
            [0, 6, 0, 0, 0, 0, 2, 8, 0],
            [0, 0, 0, 4, 1, 9, 0, 0, 5],
            [0, 0, 0, 0, 8, 0, 0, 7, 9],
        ];

        assert_eq!(
            is_a_good_candidate_for_row(0, 5, &initial_conditions),
            false
        );
        assert_eq!(
            is_a_good_candidate_for_row(0, 7, &initial_conditions),
            false
        );
        assert_eq!(
            is_a_good_candidate_for_row(0, 3, &initial_conditions),
            false
        );
        assert_eq!(is_a_good_candidate_for_row(0, 9, &initial_conditions), true);
        assert_eq!(is_a_good_candidate_for_row(1, 4, &initial_conditions), true);
        assert_eq!(
            is_a_good_candidate_for_row(8, 8, &initial_conditions),
            false
        );
        assert_eq!(
            is_a_good_candidate_for_row(8, 9, &initial_conditions),
            false
        );
        let initial_conditions = [
            [5, 3, 0, 6, 7, 8, 9, 1, 2],
            [6, 7, 2, 1, 9, 5, 3, 4, 8],
            [1, 9, 8, 3, 4, 2, 5, 6, 7],
            [8, 5, 9, 7, 6, 1, 4, 2, 3],
            [0, 2, 6, 8, 5, 3, 7, 9, 1],
            [7, 1, 3, 9, 2, 4, 8, 5, 6],
            [9, 6, 1, 5, 3, 7, 2, 8, 4],
            [2, 8, 7, 4, 1, 9, 6, 3, 5],
            [3, 0, 5, 2, 8, 6, 1, 7, 9],
        ];
        assert_eq!(is_a_good_candidate_for_row(0, 4, &initial_conditions), true);
    }
    #[test]
    fn test_is_a_good_candidate_for_quadrant_ij() {
        let initial_conditions = [
            [5, 3, 0, 0, 7, 0, 0, 0, 0],
            [6, 0, 0, 1, 9, 5, 0, 0, 0],
            [0, 9, 8, 0, 0, 0, 0, 6, 0],
            [8, 0, 0, 0, 6, 0, 0, 0, 3],
            [4, 0, 0, 8, 0, 3, 0, 0, 1],
            [7, 0, 0, 0, 2, 0, 0, 0, 6],
            [0, 6, 0, 0, 0, 0, 2, 8, 0],
            [0, 0, 0, 4, 1, 9, 0, 0, 5],
            [0, 0, 0, 0, 8, 0, 0, 7, 9],
        ];

        assert_eq!(
            is_a_good_candidate_for_sub_matrix(1, 1, 5, &initial_conditions),
            false
        );
        assert_eq!(
            is_a_good_candidate_for_sub_matrix(8, 8, 2, &initial_conditions),
            false
        );
        assert_eq!(
            is_a_good_candidate_for_sub_matrix(8, 8, 3, &initial_conditions),
            true
        );
    }
    #[test]
    fn test_solve() {
        let mut unfeasible_conditions = [
            [0, 1, 2, 0, 0, 0, 0, 0, 0],
            [3, 4, 5, 0, 0, 0, 0, 0, 0],
            [6, 7, 8, 0, 0, 0, 0, 0, 0],
            [9, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0],
        ];

        let mut cell_00 = initialize_cells(&unfeasible_conditions);
        let result = cell_00.solve(&mut unfeasible_conditions);
        match result {
            Ok(_) => assert!(false), // should not be solvable
            Err(_) => assert!(true), // expected failure
        }
    }
    #[test]
    fn test_solve_3() {
        let mut initial_conditions = [
            [5, 3, 0, 6, 7, 8, 9, 1, 2],
            [6, 7, 2, 1, 9, 5, 3, 4, 8],
            [1, 9, 8, 3, 4, 2, 5, 6, 7],
            [8, 5, 9, 7, 6, 1, 4, 2, 3],
            [0, 2, 6, 8, 5, 3, 7, 9, 1],
            [7, 1, 3, 9, 2, 4, 8, 5, 6],
            [9, 6, 1, 5, 3, 7, 2, 8, 4],
            [2, 8, 7, 4, 1, 9, 6, 3, 5],
            [3, 0, 5, 2, 8, 6, 1, 7, 9],
        ];
        let mut cell_00 = initialize_cells(&initial_conditions);
        let result = cell_00.solve(&mut initial_conditions);
        for row in initial_conditions {
            println!("original {:?}", row);
        }
        match result {
            Ok(_) => assert!(true),   // should not be solvable
            Err(_) => assert!(false), // expected failure
        }
        assert_eq!(initial_conditions[4][0], 4);
        assert_eq!(initial_conditions[8][1], 4);
        assert_eq!(initial_conditions[0][2], 4);
    }

    #[test]
    fn test_solve_4() {
        let mut initial_conditions = [
            [5, 3, 0, 0, 7, 0, 0, 0, 0],
            [6, 0, 0, 1, 9, 5, 0, 0, 0],
            [0, 9, 8, 0, 0, 0, 0, 6, 0],
            [8, 0, 0, 0, 6, 0, 0, 0, 3],
            [4, 0, 0, 8, 0, 3, 0, 0, 1],
            [7, 0, 0, 0, 2, 0, 0, 0, 6],
            [0, 6, 0, 0, 0, 0, 2, 8, 0],
            [0, 0, 0, 4, 1, 9, 0, 0, 5],
            [0, 0, 0, 0, 8, 0, 0, 7, 9],
        ];

        let solution = [
            [5, 3, 4, 6, 7, 8, 9, 1, 2],
            [6, 7, 2, 1, 9, 5, 3, 4, 8],
            [1, 9, 8, 3, 4, 2, 5, 6, 7],
            [8, 5, 9, 7, 6, 1, 4, 2, 3],
            [4, 2, 6, 8, 5, 3, 7, 9, 1],
            [7, 1, 3, 9, 2, 4, 8, 5, 6],
            [9, 6, 1, 5, 3, 7, 2, 8, 4],
            [2, 8, 7, 4, 1, 9, 6, 3, 5],
            [3, 4, 5, 2, 8, 6, 1, 7, 9],
        ];

        let mut cell_00 = initialize_cells(&initial_conditions);
        let result = cell_00.solve(&mut initial_conditions);
        match result {
            Ok(_) => assert!(true),   // should not be solvable
            Err(_) => assert!(false), // expected failure
        }
        assert_eq!(initial_conditions, solution);
    }
    #[test]
    fn test_parse() {
        let initial_text = "[
            [5, 3, 0, 0, 7, 0, 0, 0, 0],
            [6, 0, 0, 1, 9, 5, 0, 0, 0],
            [0, 9, 8, 0, 0, 0, 0, 6, 0],
            [8, 0, 0, 0, 6, 0, 0, 0, 3],
            [4, 0, 0, 8, 0, 3, 0, 0, 1],
            [7, 0, 0, 0, 2, 0, 0, 0, 6],
            [0, 6, 0, 0, 0, 0, 2, 8, 0],
            [0, 0, 0, 4, 1, 9, 0, 0, 5],
            [0, 0, 0, 0, 8, 0, 0, 7, 9]
        ]";
        let answer = [
            [5, 3, 0, 0, 7, 0, 0, 0, 0],
            [6, 0, 0, 1, 9, 5, 0, 0, 0],
            [0, 9, 8, 0, 0, 0, 0, 6, 0],
            [8, 0, 0, 0, 6, 0, 0, 0, 3],
            [4, 0, 0, 8, 0, 3, 0, 0, 1],
            [7, 0, 0, 0, 2, 0, 0, 0, 6],
            [0, 6, 0, 0, 0, 0, 2, 8, 0],
            [0, 0, 0, 4, 1, 9, 0, 0, 5],
            [0, 0, 0, 0, 8, 0, 0, 7, 9],
        ];
        let initial_conditions = parse_initial_conditions(initial_text.into());

        assert_eq!(initial_conditions, answer);
    }
    #[test]
    fn test_global_solve() {
        let mut initial_conditions: [[usize; 9]; 9] = [
            [5, 3, 0, 0, 7, 0, 0, 0, 0],
            [6, 0, 0, 1, 9, 5, 0, 0, 0],
            [0, 9, 8, 0, 0, 0, 0, 6, 0],
            [8, 0, 0, 0, 6, 0, 0, 0, 3],
            [4, 0, 0, 8, 0, 3, 0, 0, 1],
            [7, 0, 0, 0, 2, 0, 0, 0, 6],
            [0, 6, 0, 0, 0, 0, 2, 8, 0],
            [0, 0, 0, 4, 1, 9, 0, 0, 5],
            [0, 0, 0, 0, 8, 0, 0, 7, 9],
        ];
        let answer: [[usize; 9]; 9] = [
            [5, 3, 4, 6, 7, 8, 9, 1, 2],
            [6, 7, 2, 1, 9, 5, 3, 4, 8],
            [1, 9, 8, 3, 4, 2, 5, 6, 7],
            [8, 5, 9, 7, 6, 1, 4, 2, 3],
            [4, 2, 6, 8, 5, 3, 7, 9, 1],
            [7, 1, 3, 9, 2, 4, 8, 5, 6],
            [9, 6, 1, 5, 3, 7, 2, 8, 4],
            [2, 8, 7, 4, 1, 9, 6, 3, 5],
            [3, 4, 5, 2, 8, 6, 1, 7, 9],
        ];

        solve(&mut initial_conditions);

        assert_eq!(initial_conditions, answer);
    }
}

Tagged in :

Camilo MATAJIRA Avatar
Camilo MATAJIRA