Problem overview
The function solve_sudoku receives a 9x9 board as a Vec<Vec<char>>. Each cell holds a digit from '1' to '9' or '.' for an empty cell. The function fills every empty cell so that each row, each column and each of the nine 3x3 boxes contains the digits 1 to 9 exactly once, and returns the finished board. The input is guaranteed to have exactly one solution.
For the sample puzzle that starts with the rows 53..7.... and 6..195..., the solved board begins 534678912 and 672195348. The clues already on the board never change; only the dots are replaced.
Approach: try a digit, recurse, undo on failure
A person solving a Sudoku looks for a cell where only one digit fits. The simplest program-friendly strategy is more mechanical and just as correct: find the first empty cell, try the digits 1 to 9 there one by one, and keep only a digit that breaks no rule. Then solve the rest of the board the same way. If the rest turns out to be unsolvable, the digit was a bad guess: erase it and try the next one. This is backtracking.
Each recursive call answers one question: "can the board, as it stands now, be completed?" It returns true when it can, with the board filled in, and false when it can't. A false result tells the caller to undo its latest guess and try something else. The key discipline is that every guess is undone before the next one, so a failed branch leaves no trace.
The search is exponential in the worst case, but the rules reject most digits immediately, so a fixed 9x9 puzzle with a unique solution is solved quickly.
Step by step
- Start the search from
solve_sudokuby callingSelf::backtrack(&mut board). The recursion edits the board in place, so the function passes a mutable borrow. - Return the board. After the search,
boardis the last expression, without a semicolon, so it is the return value. - Declare
backtrackwith a&mut Vec<Vec<char>>parameter and aboolresult. - Scan for an empty cell with nested loops over
rowandcolin0..9, and act only whenboard[row][col] == '.'. - Try the digits with
for val in b'1'..=b'9'and turn each byte into acharwithval as char. - Check the rules with
Self::is_validbefore writing anything. - Place, recurse, undo. Write the digit, call
backtrackagain, returntrueif that succeeds, and otherwise set the cell back to'.'. - Give up on this cell. If no digit worked, return
falseso the caller can change its own guess. - Finish. If the scan finds no empty cell, the board is complete, so the function returns
true. - Write
is_valid, which borrows the board immutably. It scans all 81 cells, and a cell is a conflict when it already holdsvaland shares the target's row, column or 3x3 box.
How is_valid recognises a box
Integer division by 3 turns a row or column index into a box index: 0 to 2 give 0, 3 to 5 give 1 and 6 to 8 give 2. Two cells are in the same box when both their row indices and their column indices land on the same box index. That is what same_row_box, same_col_box and same_box compute.
The target cell itself matches the row-or-column test, but it holds '.', never a digit, so it can't produce a false conflict.
The solution in Rust
impl Solution {
fn is_valid(board: &Vec<Vec<char>>, row: usize, col: usize, val: char) -> bool {
for i in 0..9 {
for j in 0..9 {
let used_value = board[i][j] == val;
let same_row_or_col = row == i || col == j;
let same_row_box = row / 3 == i / 3;
let same_col_box = col / 3 == j / 3;
let same_box = same_row_box && same_col_box;
if used_value && (same_row_or_col || same_box) {
return false;
}
}
}
true
}
fn backtrack(board: &mut Vec<Vec<char>>) -> bool {
for row in 0..9 {
for col in 0..9 {
if board[row][col] == '.' {
for val in b'1'..=b'9' {
let ch = val as char;
if Self::is_valid(board, row, col, ch) {
board[row][col] = ch;
if Self::backtrack(board) {
return true;
}
board[row][col] = '.';
}
}
return false;
}
}
}
true
}
fn solve_sudoku(mut board: Vec<Vec<char>>) -> Vec<Vec<char>> {
Self::backtrack(&mut board);
board
}
}
The Rust details worth a closer look:
- Two kinds of borrow.
backtracktakes&mut Vec<Vec<char>>because it writes to the board.is_validtakes&Vec<Vec<char>>because it only reads. Passing theboardvariable, which is already a&mut, tois_validis accepted: Rust lends it out as a shared borrow for the duration of the call. - Bytes to characters.
b'1'is theu8value of the character'1', sob'1'..=b'9'walks the nine digit codes in order. The range is inclusive, since..would stop beforeb'9'. Au8converts tocharwithas. - Comparing characters. The board stores
charvalues, so the comparison isboard[row][col] == '.'with single quotes. A double-quoted"."is a&strand won't compile against achar. - Indices are
usize. The loop variablesrowandcolare inferred asusizebecause they index the vectors, which is exactly the typeis_validdeclares. mut boardin the signature. The function owns its argument, andmutlets it take a mutable borrow of it. The caller's variable is moved in and can't be used afterwards.- The ignored result.
solve_sudokudoesn't use theboolfrombacktrack. The puzzle is guaranteed to have a solution, so the board is returned filled in.
Complexity
Time. Each call to is_valid scans 81 cells, which is constant work. In the worst case, a board with m empty cells can try up to 9 digits per cell, so the search is bounded by roughly 9^m placements. Rejecting digits early cuts this down enormously in practice, and a board has at most 81 cells.
Space. The board is edited in place. The only extra memory is the recursion, which is at most one frame per empty cell, so at most 81 frames deep.
Edge cases and common mistakes
- Forgetting to undo. If the line that restores
'.'is missing, a failed guess stays on the board and blocks later digits. The search then fails on a puzzle that has a solution. - Returning
trueafter the digit loop. When no digit fits, the answer must befalse. Otherwise the caller believes the board is complete. - Continuing the scan after a guess. The loops return from inside the first empty cell they find, because the recursive call re-scans the whole board. Don't keep looping after the digit loop.
- Checking only the row and column. A digit can fit its row and column and still repeat inside its 3x3 box.
- Unsolvable boards. Because every guess is undone, a puzzle with no solution comes back unchanged.
- Already full boards. A board with no
'.'makes the scan finish at once and returntrue.
Testing
The sample board 53..7...., 6..195..., .98....6., 8...6...3, 4..8.3..1, 7...2...6, .6....28., ...419..5, ....8..79 is solved as:
534678912
672195348
198342567
859761423
426853791
713924856
961537284
287419635
345286179
