Sudoku Solver
HardPrompt
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-9must occur exactly once in each row. - Each of the digits
1-9must occur exactly once in each column. - Each of the digits
1-9must occur exactly once in each of the 93x3sub-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 == 9board[i].length == 9board[i][j]is a digit or'.'.- It is guaranteed that the input board has only one solution.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach uses a standard recursive backtracking algorithm. It iterates through the grid to find an empty cell, then tries to place each digit from 1 to 9 in that cell. For each attempt, it checks if the placement is valid according to Sudoku rules. If it is, it proceeds recursively. If a path leads to a dead end, it backtracks and tries the next digit.
Algorithm
- Define a recursive function,
solve(), that attempts to solve the board. - Iterate through each cell of the board from
(0,0)to(8,8). - If a cell
(row, col)is empty, loop through digits '1' to '9'. - For each digit, check its validity using a helper function
isValid()which scans the current row, column, and 3x3 sub-grid. - If the digit is valid, place it and make a recursive call to
solve(). - If the recursive call returns
true, a solution is found, so returntrue. - If it returns
false, backtrack by resetting the cell to '.' and try the next digit. - If all digits fail for a cell, return
false. - If the entire board is scanned without finding empty cells, return
true.
Walkthrough
This method employs a brute-force recursive strategy. The main solve function iterates through the grid. Upon finding an empty cell, it tries to fill it with a digit from 1 to 9. For each digit, it calls a helper function isValid to check if the move is legal. The isValid function performs three checks: whether the digit already exists in the current row, the current column, or the current 3x3 sub-grid. If the move is valid, the function calls itself recursively. If the recursion leads to a dead end (returns false), it backtracks by undoing the move and trying the next digit. This process continues until a full solution is found or all possibilities are exhausted.
class Solution { public void solveSudoku(char[][] board) { solve(board); } private boolean solve(char[][] board) { for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { if (board[i][j] == '.') { for (char c = '1'; c <= '9'; c++) { if (isValid(board, i, j, c)) { board[i][j] = c; if (solve(board)) { return true; } else { board[i][j] = '.'; // Backtrack } } } return false; // No valid number found for this cell } } } return true; // Board is solved } private boolean isValid(char[][] board, int row, int col, char c) { for (int i = 0; i < 9; i++) { // Check row if (board[row][i] == c) { return false; } // Check column if (board[i][col] == c) { return false; } // Check 3x3 box int boxRow = 3 * (row / 3) + i / 3; int boxCol = 3 * (col / 3) + i % 3; if (board[boxRow][boxCol] == c) { return false; } } return true; }}Complexity
Time
O(9^m), where 'm' is the number of empty cells. In the worst case, we have to explore all possible number combinations for the empty cells.
Space
O(m) or O(81) for the recursion stack depth. Since the board size is fixed, this can be considered O(1).
Trade-offs
Pros
Simple to understand and implement.
Guaranteed to find the solution for a valid puzzle.
Cons
Inefficient due to repeated validation checks.
Can be very slow for puzzles with a large number of empty cells.
Solutions
Solution
public class Solution { public void SolveSudoku(char[][] board) { this.board = new ushort ? [9, 9]; for (var i = 0; i < 9; ++i) { for (var j = 0; j < 9; ++j) { if (board[i][j] != '.') { this.board[i, j] = (ushort)(1 << (board[i][j] - '0' - 1)); } } } if (SolveSudoku(0, 0)) { for (var i = 0; i < 9; ++i) { for (var j = 0; j < 9; ++j) { if (board[i][j] == '.') { board[i][j] = '0'; while (this.board[i, j].Value != 0) { board[i][j] = (char)(board[i][j] + 1); this.board[i, j] >>= 1; } } } } } } private ushort ? [, ] board; private bool ValidateHorizontalRule(int row) { ushort temp = 0; for (var i = 0; i < 9; ++i) { if (board[row, i].HasValue) { if ((temp | board[row, i].Value) == temp) { return false; } temp |= board[row, i].Value; } } return true; } private bool ValidateVerticalRule(int column) { ushort temp = 0; for (var i = 0; i < 9; ++i) { if (board[i, column].HasValue) { if ((temp | board[i, column].Value) == temp) { return false; } temp |= board[i, column].Value; } } return true; } private bool ValidateBlockRule(int row, int column) { var startRow = row / 3 * 3; var startColumn = column / 3 * 3; ushort temp = 0; for (var i = startRow; i < startRow + 3; ++i) { for (var j = startColumn; j < startColumn + 3; ++j) { if (board[i, j].HasValue) { if ((temp | board[i, j].Value) == temp) { return false; } temp |= board[i, j].Value; } } } return true; } private bool SolveSudoku(int i, int j) { while (true) { if (j == 9) { ++i; j = 0; } if (i == 9) { return true; } if (board[i, j].HasValue) { ++j; } else { break; } } ushort stop = 1 << 9; for (ushort t = 1; t != stop; t <<= 1) { board[i, j] = t; if (ValidateHorizontalRule(i) && ValidateVerticalRule(j) && ValidateBlockRule(i, j)) { if (SolveSudoku(i, j + 1)) { return true; } } } board[i, j] = null; return false; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.