37. Sudoku Solver - DevCodeEx

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.

:

View Leetcode Problem

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;
    }
}

Code Editor (Testing phase)

Improve Your Solution

Use the editor below to refine the provided solution. Select a programming language and try the following:

Add import statement if required.
Optimize the code for better time or space complexity.
Add test cases to validate edge cases and common scenarios.
Handle error conditions or invalid inputs gracefully.
Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.