Sudoku Solver

The key idea

Walk the empty cells one at a time. For each, try every digit 1-9; keep a digit only if it breaks no rule in its row, column, or 3x3 box, then recurse to the next empty cell. If no digit fits, the earlier choice was wrong, so undo it and try the next candidate there. This try-undo-retry is backtracking.

Problem

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

- Each of the digits 1-9 must occur exactly once in each row.
- Each of the digits 1-9 must occur exactly once in each column.
- Each of the digits 1-9 must occur exactly once in each of the nine 3x3 sub-boxes of the grid.

The . character indicates empty cells. The given board is guaranteed to have only one solution.

Constraints

board.length == 9
board[i].length == 9
board[i][j] is a digit 1-9 or .
It is guaranteed that the input board has only one solution

Examples

Input: board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]] Output: [["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]

Complexity

Time: O(9^m) Space: O(m)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →