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);