LeetCode 37: Sudoku Solver Solution

Master LeetCode problem 37 (Sudoku Solver), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

37. Sudoku Solver

Hard

Array Hash Table Backtracking Matrix

Problem Explanation

Explanation:

To solve the Sudoku puzzle, we can use backtracking. We will try placing numbers 1 to 9 in each empty cell and recursively check if the current configuration is valid. If valid, we move on to the next empty cell and repeat the process. If at any point we find that no valid number can be placed, we backtrack to the previous cell and try a different number.

Algorithm:

Define a recursive function that tries placing numbers in empty cells and checks the validity of the current configuration.
For each empty cell, try placing numbers 1 to 9.
If a number can be placed, recursively call the function for the next empty cell.
If no number can be placed, backtrack to the previous cell and try a different number.
Repeat this process until the entire board is filled with valid numbers.

Time Complexity: The time complexity of this algorithm is exponential, but in practice, it performs well for typical Sudoku puzzles.

Space Complexity: The space complexity is O(1) as we are modifying the input board in place.

Solution Code

class Solution {
    public void solveSudoku(char[][] board) {
        if (board == null || board.length == 0) return;
        solve(board);
    }
    
    private boolean solve(char[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; 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] = '.';
                            }
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    
    private boolean isValid(char[][] board, int row, int col, char c) {
        for (int i = 0; i < 9; i++) {
            if (board[i][col] == c) return false;
            if (board[row][i] == c) return false;
            if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false;
        }
        return true;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 37 (Sudoku Solver)?

This page provides optimized solutions for LeetCode problem 37 (Sudoku Solver) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 37 (Sudoku Solver)?

The time complexity for LeetCode 37 (Sudoku Solver) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 37 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 37 in Java, C++, or Python.

Back to LeetCode Solutions