NUHMAN.com

Introduction

LeetCode 37: Sudoku Solver is an extension of the Valid Sudoku problem. In this problem, you're given a 9x9 Sudoku grid partially filled with digits, and the task is to fill the grid to complete the Sudoku puzzle, ensuring that it follows all Sudoku rules:

1. Each row must contain the digits 1-9 without repetition.
2. Each column must contain the digits 1-9 without repetition.
3. Each 3x3 subgrid must also contain the digits 1-9 without repetition.

This problem is solved using the backtracking algorithm, which explores each possible solution and backtracks if a conflict is found.

Problem Statement

Given a partially filled 9x9 Sudoku board, write a program to solve the puzzle by filling the empty cells. You may assume that the Sudoku puzzle has only one solution.

Examples

go

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"]]

Approach: Backtracking

The key idea is to attempt to place digits in empty cells and backtrack when an invalid placement occurs.

Steps:

1. Find the first empty cell ('.').
2. Try placing each digit (1-9) in that cell.

• For each digit, check if it’s valid (not already in the row, column, or 3x3 subgrid).

1. If the digit is valid:

• Place it and recursively attempt to fill the rest of the board.

1. If placing a number results in a valid solution for the whole board, return true.
2. If placing a number leads to an invalid state, backtrack by resetting the cell and trying the next digit.
3. If no solution is possible (all digits lead to conflicts), return false.

Go Implementation

go

func solveSudoku(board [][]byte) {
    solve(board)
}

func solve(board [][]byte) bool {
    for i := 0; i < 9; i++ {
        for j := 0; j < 9; j++ {
            if board[i][j] == '.' {
                for num := '1'; num <= '9'; num++ {
                    if isValid(board, i, j, byte(num)) {
                        board[i][j] = byte(num)
                        if solve(board) {
                            return true
                        }
                        board[i][j] = '.' // Backtrack
                    }
                }
                return false
            }
        }
    }
    return true
}

func isValid(board [][]byte, row, col int, num byte) bool {
    // Check row
    for i := 0; i < 9; i++ {
        if board[row][i] == num {
            return false
        }
    }

    // Check column
    for i := 0; i < 9; i++ {
        if board[i][col] == num {
            return false
        }
    }

    // Check 3x3 subgrid
    startRow, startCol := (row/3)*3, (col/3)*3
    for i := startRow; i < startRow+3; i++ {
        for j := startCol; j < startCol+3; j++ {
            if board[i][j] == num {
                return false
            }
        }
    }

    return true
}

Example Walkthrough

Let's walk through the process of solving a sample puzzle:

go

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"]]

1. Start with the first empty cell (board[0][2]).
2. Try placing numbers from 1 to 9. Let's say 5 works.
3. Continue filling the next empty cells recursively.
4. Once all cells are filled, the solution is found.

The algorithm backtracks if it ever encounters a conflict, ensuring that the Sudoku is solved correctly.

Time and Space Complexity

MetricComplexityTime ComplexityO(9^(n*n))Space ComplexityO(n*n)

• The time complexity is O(9^(n*n)), where n is the size of the board (9). This is because in the worst case, we may try all 9 digits in every empty cell.
• The space complexity is O(n*n) due to the recursive call stack, where n is the size of the grid (9).

Edge Cases

• The board may already be solved when provided as input.
• It’s assumed that there’s always one valid solution (as per problem constraints).

Key Takeaways

• The backtracking algorithm is a natural fit for solving constraint-based problems like Sudoku.
• By systematically trying and backtracking on possible values for each empty cell, we can explore all potential solutions efficiently.
• The recursive structure of the algorithm enables easy backtracking and ensures the solution space is fully explored.