Sudoku Solver
LeetCode 37 | Difficulty: Hard
HardProblem Description
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 `3x3` sub-boxes of the grid.
The '.' character indicates empty cells.
Example 1:
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"]]
Explanation: The input board is shown above and the only valid solution is shown below:
Constraints:
- `board.length == 9`
- `board[i].length == 9`
- `board[i][j]` is a digit or `'.'`.
- It is **guaranteed** that the input board has only one solution.
Topics: Array, Hash Table, Backtracking, Matrix
Approach
Backtracking
Explore all candidates by building solutions incrementally. At each step, choose an option, explore further, then unchoose (backtrack) to try the next option. Prune branches that can't lead to valid solutions.
Generate all combinations/permutations, or find solutions that satisfy constraints.
Hash Map
Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?
Need fast lookups, counting frequencies, finding complements/pairs.
Matrix
Treat the matrix as a 2D grid. Common techniques: directional arrays (dx, dy) for movement, BFS/DFS for connected regions, in-place marking for visited cells, boundary traversal for spiral patterns.
Grid traversal, island problems, path finding, rotating/transforming matrices.
Solutions
Solution 1: C# (Best: 264 ms)
| Metric | Value |
|---|---|
| Runtime | 264 ms |
| Memory | N/A |
| Date | 2018-02-23 |
public class Solution {
public void SolveSudoku(char[,] board)
{
if (board == null || board.GetLength(0) != 9 || board.GetLength(1) != 9)
{
throw new ArgumentException("invalid sudoku board");
}
Solve(board);
}
public bool Solve(char[,] board)
{
for (int i = 0; i < board.GetLength(0); i++)
{
for (int j = 0; j < board.GetLength(1); j++)
{
if (board[i, j] == '.')
{
for (int k = 1; k <= 9; k++)
{
char val = (char)k.ToString()[0];
if (IsValid(board, i, j, val))
{
board[i, j] = val;
if (Solve(board))
{
return true;
}
else
{
board[i, j] = '.';
}
}
}
return false;
}
}
}
return true;
}
public bool IsValid(char[,] board, int row, int col, char c)
{
for (int i = 0; i < 9; i++)
{
if (board[row, i] != '.' && board[row, i] == c)
{
return false;
}
if (board[i, col] != '.' && board[i, col] == c)
{
return false;
}
if (board[3 * (row / 3) + i / 3, 3 * (col / 3) + i % 3] != '.' &&
board[3 * (row / 3) + i / 3, 3 * (col / 3) + i % 3] == c)
{
return false;
}
}
return true;
}
}
📜 2 more C# submission(s)
Submission (2020-01-10) — 332 ms, 33 MB
public class Solution {
public bool SolveSudoku(char[][] board)
{
for (int i = 0; i < board.Length; i++)
{
for (int j = 0; j < board[0].Length; j++)
{
if (board[i][j] == '.')
{
for (int k = 1; k <= 9; k++)
{
char val = (char)k.ToString()[0];
if (IsValid(board, i, j, val))
{
board[i][j] = val;
if (SolveSudoku(board))
{
return true;
}
else
{
board[i][j] = '.';
}
}
}
return false;
}
}
}
return true;
}
public bool IsValid(char[][] board, int row, int col, char c)
{
for (int i = 0; i < 9; i++)
{
if (board[row][i] == c ||
board[i][col] == c ||
board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c)
{
return false;
}
}
return true;
}
}
Submission (2020-01-10) — 336 ms, 33.2 MB
public class Solution {
public bool SolveSudoku(char[][] board)
{
for (int i = 0; i < board.Length; i++)
{
for (int j = 0; j < board[0].Length; j++)
{
if (board[i][j] == '.')
{
for (int k = 1; k <= 9; k++)
{
char val = (char)k.ToString()[0];
if (IsValid(board, i, j, val))
{
board[i][j] = val;
if (SolveSudoku(board))
{
return true;
}
else
{
board[i][j] = '.';
}
}
}
return false;
}
}
}
return true;
}
public bool IsValid(char[][] board, int row, int col, char c)
{
for (int i = 0; i < 9; i++)
{
if (board[row][i] != '.' && board[row][i] == c)
{
return false;
}
if (board[i][col] != '.' && board[i][col] == c)
{
return false;
}
if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] != '.' &&
board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c)
{
return false;
}
}
return true;
}
}
Complexity Analysis
| Approach | Time | Space |
|---|---|---|
| Backtracking | $O(n! or 2^n)$ | $O(n)$ |
| Hash Map | $O(n)$ | $O(n)$ |
Interview Tips
- Break the problem into smaller subproblems. Communicate your approach before coding.
- Hash map gives O(1) lookup — think about what to use as key vs value.
- Identify pruning conditions early to avoid exploring invalid branches.
- LeetCode provides 2 hint(s) for this problem — try solving without them first.
💡 Hints
Hint 1: For each cell, place a valid number and try solving for the remaining empty cells.
Hint 2: If stuck, undo (backtrack) and try another valid number.