BackTrackingProblem 5 of 19

Sudoku Solver

Brute Force
Time: O(9^(n²))
Space: O(n²)
Optimal
Time: O(9^m)
Space: O(1)

Problem Statement

Write a program to solve a Sudoku puzzle by filling the empty cells. A sudoku solution must satisfy all of the following rules:

  1. Each of the digits 1-9 must occur exactly once in each row.
  2. Each of the digits 1-9 must occur exactly once in each column.
  3. Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes.

The '.' character indicates empty cells.

Example:

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

Approach 1: Brute Force (Try All Digits)

Intuition

For each empty cell, try all digits from 1 to 9. For each digit, check if placing it violates any Sudoku rule. If valid, place it and move to the next empty cell. Backtrack if stuck.

Algorithm

  1. Find the next empty cell
  2. Try digits 1-9 in that cell
  3. For each digit, check if it's valid (not in same row, column, or 3x3 box)
  4. If valid, place it and recurse
  5. If recursion returns false, backtrack (reset to empty)
  6. If all cells filled, return true
java
class Solution {
    public boolean isValid(char[][] board, int row, int col, char c) {
        for (int i = 0; i < 9; i++) {
            // Check row
            if (board[row][i] == c) return false;
            // Check column
            if (board[i][col] == c) return false;
            // Check 3x3 box
            int boxRow = 3 * (row / 3) + i / 3;
            int boxCol = 3 * (col / 3) + i % 3;
            if (board[boxRow][boxCol] == c) return false;
        }
        return true;
    }
    
    public boolean solve(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    // Try digits 1-9
                    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] = '.';  // Backtrack
                        }
                    }
                    return false;  // No valid digit found
                }
            }
        }
        return true;  // All cells filled
    }
    
    public void solveSudoku(char[][] board) {
        solve(board);
    }
}

Complexity Analysis

  • Time Complexity: O(9^(n²)) - In worst case, try 9 digits for each of 81 cells
  • Space Complexity: O(n²) - Recursion stack depth

Approach 2: Optimal (Using Hash Sets for O(1) Validation)

Intuition

Pre-compute which digits are already present in each row, column, and box using hash sets. This reduces validation from O(n) to O(1) for each placement.

Algorithm

  1. Initialize sets for each row, column, and box
  2. Pre-populate sets with existing digits
  3. For each empty cell, check sets instead of iterating
  4. Update sets when placing/removing digits
java
import java.util.*;

class Solution {
    private Set<Character>[] rows = new HashSet[9];
    private Set<Character>[] cols = new HashSet[9];
    private Set<Character>[] boxes = new HashSet[9];
    
    private int getBoxIndex(int row, int col) {
        return (row / 3) * 3 + col / 3;
    }
    
    public boolean solve(char[][] board, int row, int col) {
        // Move to next row if column exceeds
        if (col == 9) {
            row++;
            col = 0;
        }
        
        // All cells filled
        if (row == 9) return true;
        
        // Skip filled cells
        if (board[row][col] != '.') {
            return solve(board, row, col + 1);
        }
        
        int boxIdx = getBoxIndex(row, col);
        
        // Try digits 1-9
        for (char c = '1'; c <= '9'; c++) {
            if (rows[row].contains(c) || cols[col].contains(c) || boxes[boxIdx].contains(c)) {
                continue;
            }
            
            // Place digit
            board[row][col] = c;
            rows[row].add(c);
            cols[col].add(c);
            boxes[boxIdx].add(c);
            
            if (solve(board, row, col + 1)) {
                return true;
            }
            
            // Backtrack
            board[row][col] = '.';
            rows[row].remove(c);
            cols[col].remove(c);
            boxes[boxIdx].remove(c);
        }
        
        return false;
    }
    
    public void solveSudoku(char[][] board) {
        // Initialize sets
        for (int i = 0; i < 9; i++) {
            rows[i] = new HashSet<>();
            cols[i] = new HashSet<>();
            boxes[i] = new HashSet<>();
        }
        
        // Populate sets with existing digits
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    char c = board[i][j];
                    rows[i].add(c);
                    cols[j].add(c);
                    boxes[getBoxIndex(i, j)].add(c);
                }
            }
        }
        
        solve(board, 0, 0);
    }
}

Complexity Analysis

  • Time Complexity: O(9^m) where m is number of empty cells - Much faster in practice
  • Space Complexity: O(1) - Fixed 27 sets of max 9 elements each

Key Takeaways

  1. Box Index Formula: (row/3)*3 + col/3 gives the 3x3 box index (0-8)
  2. Hash Set Optimization: Pre-computing constraints reduces validation time
  3. Cell-by-Cell: Process cells sequentially, backtrack when stuck
  4. Constraint Propagation: Could further optimize using techniques like naked singles
  5. LeetCode #37: Hard problem - Sudoku Solver
  6. Unique Solution: Standard Sudoku puzzles have exactly one solution
Previous
Remove Invalid Parentheses
Next
m Coloring Problem