LeetCode Problem

Problem Description

Write a program to solve a Sudoku puzzle by filling the empty cells.

Examples

Input: [[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]]

Constraints

board.length == 9
board[i].length == 9
board[i][j] is a digit 1-9 or '.'.
It is guaranteed that the input board has only one solution.

Follow-up

Approach to Solve

Use backtracking to solve the Sudoku puzzle.

Code Implementation

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        def is_valid(num, pos):
            for i in range(9):
                if board[pos[0]][i] == num or board[i][pos[1]] == num:
                    return False
            box_x, box_y = pos[1] // 3, pos[0] // 3
            for i in range(box_y * 3, box_y * 3 + 3):
                for j in range(box_x * 3, box_x * 3 + 3):
                    if board[i][j] == num:
                        return False
            return True

        def solve():
            for i in range(9):
                for j in range(9):
                    if board[i][j] == '.':
                        for num in map(str, range(1, 10)):
                            if is_valid(num, (i, j)):
                                board[i][j] = num
                                if solve():
                                    return True
                                board[i][j] = '.'
                        return False
            return True

        solve()

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;
                            }
                            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 || board[row][i] == c || board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) {
                return false;
            }
        }
        return true;
    }

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        solve(board);
    }

    bool solve(vector<vector<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;
                            }
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }

    bool isValid(vector<vector<char>>& board, int row, int col, char c) {
        for (int i = 0; i < 9; i++) {
            if (board[i][col] == c || board[row][i] == c || board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) {
                return false;
            }
        }
        return true;
    }

Explanation

This solution uses a backtracking approach to solve the Sudoku puzzle. Here's a detailed explanation of the algorithm:

We start by iterating through each cell of the 9x9 Sudoku board.
When we encounter an empty cell (denoted by '.'), we try filling it with numbers from 1 to 9.
For each number, we check if it's valid to place in the current cell by ensuring it doesn't violate Sudoku rules (no duplicates in row, column, or 3x3 sub-box).
If the number is valid, we place it in the cell and recursively try to solve the rest of the board.
If we can solve the board with the current configuration, we're done.
If we can't solve the board, we backtrack by removing the number we just placed and try the next number.
If we've tried all numbers from 1 to 9 and none work, we return false to trigger backtracking.
The process continues until we've filled all empty cells and solved the Sudoku.

The time complexity is O(9^(nn)) in the worst case, where n is the board size (9 in standard Sudoku). This is because for each of the n^2 cells, we might need to try all 9 digits. The space complexity is O(nn) due to the recursion stack in the worst case.

This algorithm efficiently solves Sudoku puzzles by exploring all possible configurations and backtracking when it reaches an invalid state.

Complexity

Time Complexity: O(9^(n*n))
Space Complexity: O(n*n)

LeetSolved

Sudoku Solver