Visualization of LeetCode #37: Sudoku Solver.
This is an educational tool to understand the backtracking algorithm.
Sudoku Solver
The Sudoku Solver uses backtracking to fill a 9×9 grid where each row, column, and 3×3 sub-box must contain the digits 1-9 without repetition. The algorithm tries each digit in empty cells, validates the placement, and backtracks when conflicts occur.
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 9 3×3 sub-boxes of the grid.
The '.' character indicates empty cells. It is guaranteed that the input board has only one solution.
Visualization
Cells Filled
0
Backtracks
0
Current Digit
-
Sudoku Grid
Code
Status
Log
How It Works
The backtracking algorithm systematically explores all possible digit placements:
- Find empty cell: Scan the board for the next empty cell (marked with '.').
- Try digits 1-9: For each digit, check if it's valid in the current position.
- Validate: Check if the digit appears in the same row, column, or 3×3 box.
- Place & recurse: If valid, place the digit and recursively solve the rest.
- Backtrack: If no valid digits exist or recursion fails, undo and try the next digit.
- Success: When all cells are filled validly, the puzzle is solved.
Complexity Analysis
- Time Complexity: O(9^(n*n)) where n=9, but pruning through validation significantly reduces the search space in practice.
- Space Complexity: O(n*n) for the board and O(n*n) for the recursion stack in worst case.