For this project, I decided to revisit my classic sudoku solver: A project I like to implement whenever I’m learning a new programming language. The sudoku solver was my first personal project which I originally wrote in Java in 2008. Since then, I’ve recreated it in Python (https://camilo.matajira.com/?p=220) and JavaScript as well.
This time, I was eager to try implementing it in Rust. However, the experience was somewhat lukewarm. While I learned a lot about the language, I wasn’t able to compile the code including the last function (the solver that joined all together.) The code compiled all the way, until the very last step.
The technical issue:
I wanted to create a linked list of Cell objects, where each Cell kept a reference to the next Cell, and the solver has a Cell as parameter, and a reference to the head of the linked list. To trigger the solver, I needed to provide a mutable reference to the head (the initial Cell of the puzzle) as well as another (possibly mutable) reference to the head, so that each Cell could compute the “state” of the game (see the snippet below).
The Rust compiler didn’t allow this, and despite all kinds of acrobatics and efforts, I couldn’t get the code to compile.
cell_00.solve(&cell_00);It’s a bit of a bummer, but I learned that Rust is not a language that lets you get away with “just any” programming approach. In the world of Rust, a struct cannot have a reference to itself. Having a Cell that references another Cell already requires moving off the beginner’s happy path (by using Box<Cell>). Having two references of the same object in the same function proved to be extremely difficult.
struct Cell {
i: usize,
j: usize,
value: usize,
next: Option<Box<Cell>>,
is_fixed: bool,
}
Anyway, below is my code (including unit tests), followed by the last compiler error I encountered.
use std::collections::HashSet;
fn main() {}
struct Cell {
i: usize,
j: usize,
value: usize,
next: Option<Box<Cell>>,
is_fixed: bool,
}
impl Cell {
fn next_value(&mut self) -> Result<(), String> {
if self.value == 9 {
return Err("Something went wrong".into());
}
self.value = self.value + 1;
Ok(())
}
fn get_ij(&self, i: usize, j: usize) -> Result<&Cell, String> {
if i == 0 && j == 0 {
return Ok(self);
} else {
let mut current = self;
loop {
let next = ¤t.next;
current = match next {
Some(current) => current,
None => {
break;
}
};
if current.i == i && current.j == j {
return Ok(current);
}
}
return Err("Cell not found".into());
}
}
fn get_set_from_column_i(&self, i: usize) -> Result<HashSet<usize>, String> {
let mut answer = HashSet::new();
if self.i != 0 || self.j != 0 {
return Err("only valid for the head".into());
} else {
let mut current = self;
answer.insert(current.value);
loop {
let next = ¤t.next;
current = match next {
Some(current) => current,
None => {
break;
}
};
if current.i == i {
answer.insert(current.value);
}
}
return Ok(answer);
}
}
fn get_set_from_row_j(&self, j: usize) -> Result<HashSet<usize>, String> {
let mut answer = HashSet::new();
if self.i != 0 || self.j != 0 {
return Err("only valid for the head".into());
} else {
let mut current = self;
answer.insert(current.value);
loop {
let next = ¤t.next;
current = match next {
Some(current) => current,
None => {
break;
}
};
if current.j == j {
answer.insert(current.value);
}
}
return Ok(answer);
}
}
fn get_set_from_sub_matrix_ij(&self, i: usize, j: usize) -> Result<HashSet<usize>, String> {
let mut answer = HashSet::new();
if self.i != 0 || self.j != 0 {
return Err("only valid for the head".into());
} else {
let original_quadrant = get_quadrant_from_ij(i, j);
let mut current = self;
let current_quadrant = get_quadrant_from_ij(current.i, current.j);
if current_quadrant == original_quadrant {
answer.insert(current.value);
}
loop {
let next = ¤t.next;
current = match next {
Some(current) => current,
None => {
break;
}
};
let current_quadrant = get_quadrant_from_ij(current.i, current.j);
if current_quadrant == original_quadrant {
answer.insert(current.value);
}
}
return Ok(answer);
}
}
fn is_a_good_candidate_for_column_i(&self, i: usize, candidate: usize) -> bool {
let values_column_i = self.get_set_from_column_i(i).unwrap();
!values_column_i.contains(&candidate)
}
fn is_a_good_candidate_for_row_j(&self, j: usize, candidate: usize) -> bool {
let values_row_j = self.get_set_from_row_j(j).unwrap();
!values_row_j.contains(&candidate)
}
fn is_a_good_candidate_for_sub_matrix_ij(&self, i: usize, j: usize, candidate: usize) -> bool {
let values_quadrant_ij = self.get_set_from_sub_matrix_ij(i, j).unwrap();
!values_quadrant_ij.contains(&candidate)
}
fn solve(&mut self, head: &Cell) -> Result<String, String> {
match self.next {
Some(_) => println!("ok"),
None => return Ok("solved".into()),
}
if self.is_fixed {
self.next.as_mut().expect("paila").solve(&head)
} else {
for candidate in self.value + 1..10 {
if head.is_a_good_candidate_for_column_i(self.i, candidate)
&& head.is_a_good_candidate_for_row_j(self.j, candidate)
&& head.is_a_good_candidate_for_sub_matrix_ij(self.i, self.j, candidate)
{
self.value = candidate;
match self.next.as_mut().expect("paila").solve(&head) {
Ok(solution) => return Ok(solution),
Err(_) => continue,
}
} else {
continue;
}
}
Err("paila".into())
}
}
}
#[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 < 6 => SubMatrixQuadrant::Quadrant2,
(x, y) if x < 3 => SubMatrixQuadrant::Quadrant3,
(x, y) if x < 6 && y < 3 => SubMatrixQuadrant::Quadrant4,
(x, y) if x < 6 && y < 6 => SubMatrixQuadrant::Quadrant5,
(x, y) if x < 6 => SubMatrixQuadrant::Quadrant6,
(x, y) if y < 3 => SubMatrixQuadrant::Quadrant7,
(x, y) if y < 6 => SubMatrixQuadrant::Quadrant8,
_ => SubMatrixQuadrant::Quadrant9,
}
}
fn initialize_cells(&initial_conditions: &[[usize; 9]; 9]) -> Box<Cell> {
let mut cell_00 = Box::new(Cell {
i: 0,
j: 0,
value: initial_conditions[0][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: j,
j: i,
value: *value_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,
value: 9,
next: None,
is_fixed: false,
};
assert_eq!(test_1.i, 0);
assert_eq!(test_1.j, 1);
}
#[test]
fn test_cell_next_value() {
let mut test_1 = Cell {
i: 0,
j: 0,
value: 0,
next: None,
is_fixed: false,
};
let _ = test_1.next_value();
assert_eq!(test_1.value, 1);
}
#[test]
fn test_cell_next_value_9() {
let mut test_1 = Cell {
i: 0,
j: 0,
value: 9,
next: None,
is_fixed: false,
};
let res = test_1.next_value();
assert!(matches!(res, Err(_)), "expected error, got: {:?}", res);
}
#[test]
fn test_cell_next_cell() {
let test_2 = Box::new(Cell {
i: 0,
j: 1,
value: 1,
next: None,
is_fixed: false,
});
let test_1 = Box::new(Cell {
i: 0,
j: 0,
value: 0,
next: Some(test_2),
is_fixed: false,
});
let Some(next) = test_1.next else { panic!() };
assert_eq!(next.value, 1);
}
#[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.value, 5);
assert_eq!(cell_00.is_fixed, true);
let cell_01 = cell_00.next.unwrap();
assert_eq!(cell_01.i, 1);
assert_eq!(cell_01.j, 0);
assert_eq!(cell_01.value, 3);
assert_eq!(cell_01.is_fixed, true);
let cell_02 = cell_01.next.unwrap();
assert_eq!(cell_02.i, 2);
assert_eq!(cell_02.j, 0);
assert_eq!(cell_02.value, 0);
assert_eq!(cell_02.is_fixed, false);
}
#[test]
fn test_get_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 cell_00 = initialize_cells(&initial_conditions);
let result_cell_00 = &cell_00.get_ij(0, 0).unwrap();
assert_eq!(result_cell_00.i, 0);
assert_eq!(result_cell_00.j, 0);
assert_eq!(result_cell_00.value, 5);
assert_eq!(result_cell_00.is_fixed, true);
let cell_40 = &cell_00.get_ij(4, 0).unwrap();
assert_eq!(cell_40.i, 4);
assert_eq!(cell_40.j, 0);
assert_eq!(cell_40.value, 7);
assert_eq!(cell_40.is_fixed, true);
let cell_88 = &cell_00.get_ij(8, 8).unwrap();
assert_eq!(cell_88.i, 8);
assert_eq!(cell_88.j, 8);
assert_eq!(cell_88.value, 9);
assert_eq!(cell_88.is_fixed, true);
}
#[test]
fn test_get_column_i() {
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: [usize; 9] = [5, 6, 0, 8, 4, 7, 0, 0, 0];
let cell_00 = initialize_cells(&initial_conditions);
assert_eq!(answer, cell_00.get_column_i(0).unwrap());
}
#[test]
fn test_get_set_from_column_i() {
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 mut answer = HashSet::new();
for i in [5, 6, 0, 8, 4, 7, 0, 0, 0] {
answer.insert(i);
}
let cell_00 = initialize_cells(&initial_conditions);
assert_eq!(answer, cell_00.get_set_from_column_i(0).unwrap());
}
#[test]
fn test_get_row_j() {
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: [usize; 9] = [5, 3, 0, 0, 7, 0, 0, 0, 0];
let cell_00 = initialize_cells(&initial_conditions);
assert_eq!(answer, cell_00.get_row_j(0).unwrap());
}
#[test]
fn test_get_set_from_row_j() {
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 mut answer = HashSet::new();
for i in [5, 3, 0, 0, 7, 0, 0, 0, 0] {
answer.insert(i);
}
let cell_00 = initialize_cells(&initial_conditions);
assert_eq!(answer, cell_00.get_set_from_row_j(0).unwrap());
}
#[test]
fn test_get_quadrants() {
assert_eq!(SubMatrixQuadrant::Quadrant1, get_quadrant_from_ij(0, 0));
assert_eq!(SubMatrixQuadrant::Quadrant2, get_quadrant_from_ij(0, 3));
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 mut answer = HashSet::new();
for i in [5, 3, 0, 6, 0, 0, 0, 9, 8] {
answer.insert(i);
}
let cell_00 = initialize_cells(&initial_conditions);
assert_eq!(answer, cell_00.get_set_from_sub_matrix_ij(0, 0).unwrap());
let mut answer = HashSet::new();
for i in [8, 0, 0, 4, 0, 0, 7, 0, 0] {
answer.insert(i);
}
assert_eq!(answer, cell_00.get_set_from_sub_matrix_ij(0, 3).unwrap());
let mut answer = HashSet::new();
for i in [2, 8, 0, 0, 0, 5, 0, 7, 9] {
answer.insert(i);
}
assert_eq!(answer, cell_00.get_set_from_sub_matrix_ij(7, 7).unwrap());
let mut answer = HashSet::new();
for i in [0, 6, 0, 8, 0, 3, 0, 2, 0] {
answer.insert(i);
}
assert_eq!(answer, cell_00.get_set_from_sub_matrix_ij(3, 3).unwrap());
}
#[test]
fn test_is_a_good_candidate_for_column_i() {
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.is_a_good_candidate_for_column_i(0, 5), false);
assert_eq!(cell_00.is_a_good_candidate_for_column_i(0, 9), true);
}
#[test]
fn test_is_a_good_candidate_for_row_j() {
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.is_a_good_candidate_for_row_j(0, 5), false);
assert_eq!(cell_00.is_a_good_candidate_for_row_j(0, 7), false);
assert_eq!(cell_00.is_a_good_candidate_for_row_j(0, 3), false);
assert_eq!(cell_00.is_a_good_candidate_for_row_j(0, 9), 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],
];
let cell_00 = initialize_cells(&initial_conditions);
assert_eq!(
cell_00.is_a_good_candidate_for_sub_matrix_ij(1, 1, 5),
false
);
assert_eq!(
cell_00.is_a_good_candidate_for_sub_matrix_ij(8, 8, 2),
false
);
assert_eq!(cell_00.is_a_good_candidate_for_sub_matrix_ij(8, 8, 3), true);
}
#[test]
fn test_solve() {
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);
static GLOBAL_HEAD: Box<Cell> = initialize_cells(&initial_conditions);
cell_00.solve(&cell_00);
}
}
Below the compiler error:
cargo test
(...)
error[E0502]: cannot borrow `*cell_00` as mutable because it is also borrowed as immutable
--> src/main.rs:532:9
|
532 | cell_00.solve(&cell_00);
| ^^^^^^^^-----^--------^
| | | |
| | | immutable borrow occurs here
| | immutable borrow later used by call
| mutable borrow occurs here
Some errors have detailed explanations: E0435, E0502, E0596, E0599.
For more information about an error, try `rustc --explain E0435`.
error: could not compile `sudoku_rust` (bin "sudoku_rust" test) due to 5 previous errors
One response to “My failed sudoku solver in Rust”
[…] 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 […]