Sudoku Solver
Hard · Backtracking · Array · Hash Table · Backtracking · Matrix
Problem
Write a program that fills in a partially completed 9 x 9 Sudoku board in place. Empty cells are marked with '.'. A completed board satisfies all three rules:
- each row contains every digit 1-9 exactly once;
- each column contains every digit 1-9 exactly once;
- each of the nine 3 x 3 boxes contains every digit 1-9 exactly once.
The input is guaranteed to have exactly one solution. Your function returns nothing; the tests check board after the call.
Examples
Input: board = [["5","3",".","1",".",".","9",".","4"],[".",".",".","9","6","4","5",".","7"],[".",".","4",".",".",".","1",".","2"],["3","7",".",".","2","9","6","4","."],[".","2",".",".",".","5",".","7","."],[".","4",".","3","7",".","8",".","9"],["7","1",".","2",".",".","4",".","3"],["2","9","6","4",".",".",".",".","."],["4","5","3","7",".",".",".","9","."]] Output: [["5","3","7","1","8","2","9","6","4"],["1","8","2","9","6","4","5","3","7"],["9","6","4","5","3","7","1","8","2"],["3","7","1","8","2","9","6","4","5"],["8","2","9","6","4","5","3","7","1"],["6","4","5","3","7","1","8","2","9"],["7","1","8","2","9","6","4","5","3"],["2","9","6","4","5","3","7","1","8"],["4","5","3","7","1","8","2","9","6"]]
Each of the 40 blanks is fixed by the row, column and box rules, giving this one grid.
Input: board = [[".","3",".",".","8","2",".","6","4"],["1","8","2","9",".","4","5","3","."],["9","6","4","5","3","7","1","8","2"],["3","7","1","8",".","9","6","4","5"],["8","2","9","6","4",".","3","7","1"],["6","4","5","3",".","1","8","2","9"],["7","1","8","2","9","6","4","5","3"],[".","9","6","4","5","3","7","1","8"],["4","5","3","7","1","8","2","9","6"]] Output: [["5","3","7","1","8","2","9","6","4"],["1","8","2","9","6","4","5","3","7"],["9","6","4","5","3","7","1","8","2"],["3","7","1","8","2","9","6","4","5"],["8","2","9","6","4","5","3","7","1"],["6","4","5","3","7","1","8","2","9"],["7","1","8","2","9","6","4","5","3"],["2","9","6","4","5","3","7","1","8"],["4","5","3","7","1","8","2","9","6"]]
Only ten cells are empty; each has exactly one digit missing from its row, column or box.
Constraints
- len(board) == 9, len(board[i]) == 9
- board[i][j] is a digit '1'-'9' or '.'
- The puzzle has exactly one solution
Approaches
- Baseline: plain backtracking in reading order — time O(9^E), space O(E)
Follow-up
How would you check that a puzzle is proper, with exactly one solution? Keep searching after the first solution and stop at the second (see the use case “Does the puzzle have exactly one solution?”). For much larger puzzles, exact cover with dancing links is the classic next step.
Related problems
Start free on Cariara · Coding problems · System design studio
