Sudoku Solver
Hard
12 views
Topics:
ArraysRecursion
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.
For example, given the following 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"]
]
The program should return the solved Sudoku board:
[
["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"]
]
Constraints:
board.length == 9board[i].length == 9board[i][j]is a digit or.- It is guaranteed that the input board has only one solution.
Solution
Clarifying Questions
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
- Is the input Sudoku board guaranteed to have a valid (but possibly incomplete) starting configuration?
- Are the digit characters in the board guaranteed to be between '1' and '9'?
- Is there guaranteed to be at least one valid solution to the given Sudoku puzzle, or should I handle cases where no solution exists?
- If multiple valid solutions exist, is any valid solution acceptable, or is there a specific solution that must be returned?
- Can I assume the board is always a 9x9 grid, or should my solution handle other grid sizes (e.g., 4x4 for a simpler Sudoku)?
- If no solution exists, what should the function do? Should it modify the board in some specified way or throw an exception?
Brute Force Solution
Approach
The brute force approach to solving Sudoku is like trying every possible combination of numbers until you find one that works. We fill in the empty spaces one by one, checking if our choice breaks any Sudoku rules. If it does, we backtrack and try a different number.
Here's how the algorithm would work step-by-step:
- Find the first empty space in the Sudoku grid.
- Try placing the number 1 in that space.
- Check if placing that number breaks any of the Sudoku rules (same number in the row, column, or 3x3 square).
- If it does break a rule, try the next number (2, then 3, and so on) until you find one that doesn't break any rules.
- If you reach the number 9 and none of them work, that means your previous guess was wrong. Go back to the previous empty space and try a different number there.
- If the number doesn't break any rules, move on to the next empty space and repeat steps 2-5.
- Keep doing this until the entire Sudoku grid is filled.
- If you manage to fill the entire grid without breaking any rules, you've found a solution!
- If you ever get stuck and can't find a valid number for a space, go back to a previous space and try a different number. This is called backtracking.
Code Implementation
def solve_sudoku(board):
def is_valid(board, number, position):
row_of_board = position[0]
column_of_board = position[1]
# Check row
for index in range(len(board[0])):
if board[row_of_board][index] == number and column_of_board != index:
return False
# Check column
for index in range(len(board)):
if board[index][column_of_board] == number and row_of_board != index:
return False
# Check 3x3 box
box_x = column_of_board // 3
box_y = row_of_board // 3
for index_i in range(box_y * 3, box_y * 3 + 3):
for index_j in range(box_x * 3, box_x * 3 + 3):
if board[index_i][index_j] == number and (index_i, index_j) != position:
return False
return True
def find_empty(board):
for row_of_board in range(len(board)):
for column_of_board in range(len(board[0])):
if board[row_of_board][column_of_board] == 0:
return (row_of_board, column_of_board) # row, col
return None
def solve():
empty_spot = find_empty(board)
if not empty_spot:
return True
else:
row_of_board, column_of_board = empty_spot
# Iterate to try each number
for number in range(1, 10):
if is_valid(board, number, (row_of_board, column_of_board)):
board[row_of_board][column_of_board] = number
# Recursively attempt to solve from this state
if solve():
return True
# Reset the cell if the current number doesn't lead to a solution.
board[row_of_board][column_of_board] = 0
# Trigger backtracking if no number works for the current cell
return False
solve()
return boardBig(O) Analysis
Time Complexity
O(9^(number of empty cells)) – The brute-force Sudoku solver explores all possible combinations of numbers for the empty cells. In the worst case, each empty cell could potentially hold any of the 9 digits. Therefore, if there are 'k' empty cells, the algorithm might have to try up to 9^k possibilities. Thus, the time complexity is exponential, driven by the number of empty cells which can be at most 81 (the number of cells in the grid). Although the number of empty cells 'k' is related to the size of the board, the cost grows exponentially with 'k'. This is significantly more than O(n^2) where n is the number of cells on the board.
Space Complexity
O(1) – The backtracking Sudoku solver primarily uses the recursion stack to explore different possibilities. In the worst-case scenario, the algorithm might try filling almost all the empty cells before finding a solution or exhausting all possibilities. Since a standard Sudoku grid is 9x9, there are a fixed number of cells (81). Therefore, the maximum depth of the recursion is bounded by the number of empty cells, which is at most 81. This constant upper bound on the recursion depth implies a constant amount of space used on the call stack, resulting in O(1) auxiliary space.
Optimal Solution
Approach
The Sudoku Solver problem can be efficiently solved using a strategy called backtracking. We try placing numbers one by one, and if a placement leads to a conflict, we undo it and try a different number. This avoids exploring every single possibility, making the process much faster.
Here's how the algorithm would work step-by-step:
- Find an empty cell in the Sudoku grid.
- Try placing numbers 1 through 9 in that cell.
- For each number, check if it's a valid placement according to Sudoku rules (no duplicates in the same row, column, or 3x3 box).
- If the number is valid, tentatively place it in the cell.
- Then, recursively apply the same solving process to the rest of the grid. This is where the backtracking magic happens: we're assuming this placement is correct and seeing where it leads.
- If the recursive call successfully solves the rest of the Sudoku, we're done! The entire board is solved.
- However, if the recursive call leads to a dead end (meaning we can't complete the Sudoku with that initial placement), undo the number we tentatively placed in the cell. This is the backtracking step: we're admitting our earlier assumption was wrong.
- Try the next number in the range 1-9 in that empty cell.
- If we've tried all numbers 1-9 in the empty cell and none of them lead to a solution, it means the Sudoku is either unsolvable or that an earlier number was placed incorrectly. In this case, we backtrack further up the call stack to correct previous assumptions.
- If we reach the point where there are no more empty cells, it means we've successfully filled the entire board without violating any rules. The Sudoku is solved!
Code Implementation
def solve_sudoku(board):
def find_empty_cell(board):
for row in range(9):
for col in range(9):
if board[row][col] == '.':
return (row, col)
return None
def is_valid(board, number, position):
row_position = position[0]
column_position = position[1]
# Check row
for i in range(9):
if board[row_position][i] == str(number) and column_position != i:
return False
# Check column
for i in range(9):
if board[i][column_position] == str(number) and row_position != i:
return False
# Check 3x3 box
box_x = (column_position // 3) * 3
box_y = (row_position // 3) * 3
for i in range(box_y, box_y + 3):
for j in range(box_x, box_x + 3):
if board[i][j] == str(number) and (i, j) != position:
return False
return True
def solve():
empty_cell = find_empty_cell(board)
if not empty_cell:
return True
else:
row, col = empty_cell
for number in range(1, 10):
# We check if placing the current number is valid
if is_valid(board, number, (row, col)):
board[row][col] = str(number)
# Attempt to solve the board recursively
if solve():
return True
# Backtrack if the current placement is wrong
board[row][col] = '.'
# Triggered when no number can solve the cell
return False
solve()Big(O) Analysis
Time Complexity
O(9^(number of empty cells)) – The Sudoku solver uses backtracking to try different numbers in empty cells. In the worst-case scenario, the algorithm may need to try all 9 possible numbers for each empty cell. Let 'k' be the number of empty cells in the Sudoku grid. Since the algorithm branches out and explores each possibility, in the worst case, it can make 9 choices for the first empty cell, 9 choices for the second, and so on. Therefore, the time complexity is proportional to 9 raised to the power of the number of empty cells (k), resulting in O(9^k). Since 'k' can be, in the worst case, a significant fraction of the total cells (81), or even the entire board if it is nearly empty, this effectively represents an exponential time complexity. Checking for validity (row, column, and box) is relatively constant within each recursive step, so the exponential exploration dominates the runtime.
Space Complexity
O(1) – The primary space complexity driver is the recursion depth during backtracking. In the worst-case scenario, the algorithm might have to try different numbers for many cells before finding the correct solution or determining that a path is invalid, leading to recursive calls. The maximum depth of this recursion is bounded by the number of empty cells in the Sudoku grid. Since a Sudoku grid is always 9x9, the number of empty cells is at most 81, which is a constant. Therefore, the space complexity due to the call stack is O(1).
Edge Cases
| Case | How to Handle |
|---|---|
| Null or empty board input | Return immediately or throw an IllegalArgumentException if the board is null or empty, as there's nothing to solve. |
| Invalid board dimensions (not 9x9) | Throw an IllegalArgumentException if the board's dimensions are not 9x9, as the Sudoku rules are defined for that size. |
| Board contains invalid characters (other than digits 1-9 and '.') | Throw an IllegalArgumentException if the board contains characters other than digits 1-9 and '.', indicating an invalid input. |
| Board is already completely solved and valid | The backtracking algorithm should still execute and correctly identify it as a solved state without altering it. |
| Board has no solution | The backtracking algorithm should exhaust all possibilities and return false, leaving the board in its initial, unsolvable state. |
| Board has multiple possible solutions; only one solution needs to be found | The backtracking algorithm stops upon finding the first valid solution, as only one solution is required. |
| Board contains a row, column, or 3x3 subgrid that is already invalid (duplicate numbers) | The backtracking algorithm will immediately return false upon encountering this invalid state, preventing further unnecessary exploration. |
| Potential stack overflow due to excessive recursion depth in backtracking | Ensure the base cases (board solved or no valid moves) are handled effectively to prevent infinite recursion and potential stack overflow. |
Explore Interview QuestionsGoogle Interview QuestionsMeta Interview QuestionsAmazon Interview QuestionsApple Interview QuestionsNetflix Interview Questions
Explore Jobs By LevelEntry-Level Software Engineer JobsMid-Level Software Engineer JobsSenior Software Engineer JobsStaff Software Engineer Jobs
