Sudoku is an addictive number placement puzzle that is logic-based. To win, you should fill the missing cells such that all rows, columns and each of the nine 3x3 boxes contain all numbers from 1 to 9. A well-posed Sudoku has only one solution.
After conquering basic algorithms, a Sudoku solver feels like a rite of passage to be a good coder. So, let's write a program that can solve any Sudoku puzzle in less than a second, starting from scratch.
Algorithm
To solve any problem, we should begin by designing an algorithm. Let's see -
-
Check if the Sudoku puzzle is valid.
-
Find an empty cell and guess a number.
-
Continue with (1) until either:
a. No empty cells are left - we found a solution!
b. We cannot proceed - We made wrong guesses. Then, we should step back and try and continue (1) with a different guess.
This backtracking algorithm will enumerate all solutions. If you are familiar with graphs, you will notice it is identical to depth-first search.
Each circle is an intermediate solution. You jump to the bottom circles by making a valid guess (arrow) and when you reached the bottom, you take a step back and explore other possibilities.
Encoding
To achieve a compact representation, we can write down a Sudoku row by row as an array of numbers. Empty cells are indicated with 0. Then, the above puzzle becomes:
000000005000075060715000002074031006100706003600520970300000859020980000400000000
Validating a region
With this representation in mind, we can begin by writing a check for all Sudoku constraints - all rows, columns and 3x3 boxes should contain 1 to 9 exactly once. Let's call each one of them regions. A region can be one particular row or a column or a box.
fn is_valid_region(region: [u8; 9]) -> bool {
let mut seen = [false; 10];
for n in region {
if n != 0 && seen[n as usize] {
return false;
}
seen[n as usize] = true;
}
true
}
The function is_valid_region checks if the numbers 1-9 occur only once.
Fetching the nth row of a Sudoku is straightforward. In our representation, the 1st row is 0, 1, 2, ..., 8. The 2nd row is 9, 10, 11, ..., 17 and so on. So, the nth row is:
With a similar approach, we can deduce the patterns for nth column and the nth box. To keep the code simple, I hard coded the 1st box and the offsets to get the other boxes.
fn get_row(sudoku: [u8; 81], row_index: usize) -> [u8; 9] {
let mut row = [0; 9];
for i in 0..9 {
row[i] = sudoku[i + row_index * 9];
}
row
}
fn get_column(sudoku: [u8; 81], column_index: usize) -> [u8; 9] {
let mut column = [0; 9];
for i in 0..9 {
column[i] = sudoku[i * 9 + column_index];
}
column
}
fn get_box(sudoku: [u8; 81], box_index: usize) -> [u8; 9] {
let mut box_region = [0; 9];
let first_box = [0, 1, 2, 9, 10, 11, 18, 19, 20];
let box_offsets = [
0,
3,
6,
9 * 3,
9 * 3 + 3,
9 * 3 + 6,
9 * 6,
9 * 6 + 3,
9 * 6 + 6,
];
for i in 0..9 {
box_region[i] = sudoku[first_box[i] + box_offsets[box_index]];
}
box_region
}
Validating Sudoku
To check if a Sudoku is valid, we just need to extract all 27 regions and verify that they are consistent.
fn is_valid_sudoku(sudoku: [u8; 81]) -> bool {
for i in 0..9 {
if !(is_valid_region(get_row(sudoku, i))
&& is_valid_region(get_column(sudoku, i))
&& is_valid_region(get_box(sudoku, i)))
{
return false;
}
}
true
}
Solving
The backtracking algorithm that we designed looks like this in Rust:
pub fn solve_sudoku(sudoku: [u8; 81]) -> Vec<[u8; 81]> {
let mut solutions = Vec::new();
fn solver(solution: [u8; 81], solutions: &mut Vec<[u8; 81]>) {
let mut empty_cell_found = false;
for i in 0..81 {
if solution[i] == 0 {
empty_cell_found = true;
for n in 1..10 {
let mut new_solution = solution;
new_solution[i] = n;
if is_valid_sudoku(new_solution) {
solver(new_solution, solutions);
}
}
break;
}
}
if !empty_cell_found {
solutions.push(solution);
}
}
solver(sudoku, &mut solutions);
solutions
}
We find an empty cell, make a valid guess and call solver recursively. We keep exploring deeper and deeper until we cannot proceed further. If all the cells are filled up, then it's a solution. We add it to our list. We continue searching the remaining paths in this graph.
This worked beautifully. It printed out the solution to the above puzzle in 0.0s.
534678912672195348198342567859761423426853791713924856961537284287419635345286179
Here's another example:
let sudoku = [
6, 4, 5, 9, 0, 0, 0, 0, 0,
0, 7, 3, 1, 0, 0, 0, 5, 0,
2, 0, 0, 0, 5, 0, 0, 0, 0,
5, 9, 0, 0, 3, 7, 6, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 4, 5, 8, 0, 0, 3, 9,
0, 0, 0, 0, 7, 0, 0, 0, 3,
0, 3, 0, 0, 0, 4, 1, 9, 0,
0, 0, 0, 0, 0, 1, 8, 2, 7,
];
let solutions: Vec<[u8; 81]> = vec![
[
6, 4, 5, 9, 2, 8, 3, 7, 1,
9, 7, 3, 1, 4, 6, 2, 5, 8,
2, 8, 1, 7, 5, 3, 9, 4, 6,
5, 9, 8, 4, 3, 7, 6, 1, 2,
3, 2, 7, 6, 1, 9, 5, 8, 4,
1, 6, 4, 5, 8, 2, 7, 3, 9,
8, 1, 9, 2, 7, 5, 4, 6, 3,
7, 3, 2, 8, 6, 4, 1, 9, 5,
4, 5, 6, 3, 9, 1, 8, 2, 7,
]];
assert_eq!(solve_sudoku(sudoku), solutions);
