What is the time complexity of Sudoku Solver?

The optimal solution has a time complexity of O(9^m).

What data structures are used to solve Sudoku Solver?

This problem uses Array, Hash Table, Backtracking, Matrix. Understanding these concepts is essential for solving this Hard problem efficiently.

What are the key insights for solving Sudoku Solver?

Insight 1: Backtracking is essential because we need to explore different possibilities for filling empty cells, and if a choice leads to an invalid state, we must revert (backtrack) and try another possibility. Insight 2: Using sets (or boolean arrays in C) to track the digits already present in each row, column, and 3x3 box allows for efficient checking of the Sudoku constraints.

Which companies ask LeetCode 37. Sudoku Solver in interviews?

This problem is frequently asked at Adobe, Amazon, Apple, Bloomberg, Cadence and 13 more companies.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Sudoku Solver - LeetCode 37 Solution

Sudoku Solver - Complete Solution Guide

Sudoku Solver is LeetCode problem 37, a Hard level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

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 : Each of the digits 1-9 must occur exactly once in each row. Each of the digits 1-9 must occur exactly once in each column. Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid. The '.' character indicates empty cells. Example 1: Input: board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",

Detailed Explanation

The Sudoku Solver problem requires you to write a program that solves a given Sudoku puzzle. The input is a 9x9 grid represented as a 2D array of characters, where digits '1'-'9' represent filled cells and '.' represents empty cells. The task is to fill the empty cells such that the solution satisfies the Sudoku rules: each row, each column, and each of the nine 3x3 sub-boxes must contain the digits '1'-'9' exactly once. The provided board is guaranteed to have only one solution, and the solution must be done in-place, modifying the given board directly.

Solution Approach

The provided solutions use a backtracking algorithm to explore possible solutions for the Sudoku puzzle. The algorithm iterates through empty cells, attempting to fill them with digits from 1 to 9. Before placing a digit, it checks if the digit is valid according to Sudoku rules (not already present in the row, column, or 3x3 box). If the digit is valid, it's placed, and the algorithm recursively calls itself to solve the rest of the puzzle. If the recursive call leads to a solution, the algorithm returns true. Otherwise, it backtracks by removing the digit and trying the next one. The sets (or boolean arrays) are used to track the digits already used in each row, column, and box, to quickly check the validity.

Step-by-Step Algorithm

Step 1: Initialize sets (or boolean arrays) to keep track of the numbers present in each row, column, and 3x3 box.
Step 2: Find all empty cells in the board and store their coordinates.
Step 3: Define a recursive backtracking function that takes the index of the current empty cell to fill as input.
Step 4: The base case for the recursion is when all empty cells have been filled. If this occurs, return true.
Step 5: For each empty cell, iterate through the numbers 1 to 9 and check if placing the number in the cell is valid (i.e., doesn't violate Sudoku rules).
Step 6: If a number is valid, place it in the cell, update the row, column, and box sets, and recursively call the backtracking function for the next empty cell.
Step 7: If the recursive call returns true (meaning a solution was found), return true from the current call.
Step 8: If the recursive call returns false (meaning the current number led to a dead end), remove the number from the cell, update the row, column, and box sets to reflect the removal, and try the next number.
Step 9: If none of the numbers 1 to 9 lead to a solution for the current empty cell, return false, indicating that the current path is invalid.
Step 10: The main function initiates the backtracking process by calling the recursive function with the index of the first empty cell.

Key Insights

Insight 1: Backtracking is essential because we need to explore different possibilities for filling empty cells, and if a choice leads to an invalid state, we must revert (backtrack) and try another possibility.
Insight 2: Using sets (or boolean arrays in C) to track the digits already present in each row, column, and 3x3 box allows for efficient checking of the Sudoku constraints.
Insight 3: Optimizing the search by considering the constraints early (checking if a number is already in the row, column, or box) significantly reduces the search space and improves performance.

Complexity Analysis

Time Complexity: O(9^m)

Space Complexity: O(1)

Topics

This problem involves: Array, Hash Table, Backtracking, Matrix.

Companies

Asked at: Adobe, Amazon, Apple, Bloomberg, Cadence, Citadel, Confluent, DoorDash, Intuit, LINE, Meta, Microsoft, Oracle, Pinterest, Riot Games, Snap, Uber, Yahoo.

Sudoku Solver | LeetCode 37

Hard

Array Hash Table Backtracking Matrix

Time: O(9^m)Space: O(1)

Solution Code

Available in:

import java.util.HashSet;
import java.util.ArrayList;
import java.util.List;
import java.util.Set;

class Solution {
    public void solveSudoku(char[][] board) {
        int N = 9;
        Set<Character>[] rows = new HashSet[N];
        Set<Character>[] cols = new HashSet[N];
        Set<Character>[] boxes = new HashSet[N];
        
        for (int i = 0; i < N; i++) {
            rows[i] = new HashSet<>();
            cols[i] = new HashSet<>();
            boxes[i] = new HashSet<>();
        }
        
        List<int[]> empty_cells = new ArrayList<>();

        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                if (board[r][c] != '.') {
                    char val = board[r][c];
                    int box_id = (r / 3) * 3 + (c / 3);
                    rows[r].add(val);
                    cols[c].add(val);
                    boxes[box_id].add(val);
                } else {
                    empty_cells.add(new int[]{r, c});
                }
            }
        }

        backtrack(board, rows, cols, boxes, empty_cells, 0);
    }

    private boolean backtrack(char[][] board, Set<Character>[] rows, Set<Character>[] cols, Set<Character>[] boxes, List<int[]> empty_cells, int k) {
        if (k == empty_cells.size()) {
            return true;
        }

        int r = empty_cells.get(k)[0];
        int c = empty_cells.get(k)[1];
        int box_id = (r / 3) * 3 + (c / 3);

        for (int i = 1; i <= 9; i++) {
            char val = (char)(i + '0');
            if (!rows[r].contains(val) && !cols[c].contains(val) && !boxes[box_id].contains(val)) {
                board[r][c] = val;
                rows[r].add(val);
                cols[c].add(val);
                boxes[box_id].add(val);

                if (backtrack(board, rows, cols, boxes, empty_cells, k + 1)) {
                    return true;
                }
                
                rows[r].remove(val);
                cols[c].remove(val);
                boxes[box_id].remove(val);
                board[r][c] = '.';
            }
        }
            
        return false;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 37: Sudoku Solver - Detailed explanation and solution approaches.

Topics

Array Hash Table Backtracking Matrix

Companies

AdobeAmazonAppleBloombergCadenceCitadelConfluentDoorDash

Stats

Difficulty:Hard

Languages:4

Companies:18

Problem #:37

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

10 steps

1
Step 1: Initialize sets (or boolean arrays) to keep track of the numbers present in each row, column, and 3x3 box.
2
Step 2: Find all empty cells in the board and store their coordinates.
3
Step 3: Define a recursive backtracking function that takes the index of the current empty cell to fill as input.
4
Step 4: The base case for the recursion is when all empty cells have been filled. If this occurs, return true.
5
Step 5: For each empty cell, iterate through the numbers 1 to 9 and check if placing the number in the cell is valid (i.e., doesn't violate Sudoku rules).
6
Step 6: If a number is valid, place it in the cell, update the row, column, and box sets, and recursively call the backtracking function for the next empty cell.
7
Step 7: If the recursive call returns true (meaning a solution was found), return true from the current call.
8
Step 8: If the recursive call returns false (meaning the current number led to a dead end), remove the number from the cell, update the row, column, and box sets to reflect the removal, and try the next number.
9
Step 9: If none of the numbers 1 to 9 lead to a solution for the current empty cell, return false, indicating that the current path is invalid.
10
Step 10: The main function initiates the backtracking process by calling the recursive function with the index of the first empty cell.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(9^m)

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The time complexity is exponential because for each empty cell, we explore up to 9 possible values. The space complexity is constant because the size of the sets or boolean arrays used to validate the Sudoku rules is fixed, and the number of variables used remains constant regardless of the input board.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Constraint Propagation

Constraint propagation techniques can be used to reduce the search space by eliminating invalid candidate values for empty cells based on the constraints. This can be combined with backtracking for a more efficient solution.

Time: Potentially better than O(9^m) in some cases, depending on the specific propagation rules.Space: O(1)

Trade-offs: Constraint propagation can reduce the search space and improve performance, especially for difficult Sudoku puzzles. However, implementing constraint propagation can be more complex.

✨

Key Insights

1Insight 1: Backtracking is essential because we need to explore different possibilities for filling empty cells, and if a choice leads to an invalid state, we must revert (backtrack) and try another possibility.
2Insight 2: Using sets (or boolean arrays in C) to track the digits already present in each row, column, and 3x3 box allows for efficient checking of the Sudoku constraints.
3Insight 3: Optimizing the search by considering the constraints early (checking if a number is already in the row, column, or box) significantly reduces the search space and improves performance.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

Edge Cases

Edge case 1: An already solved Sudoku board. The algorithm should still work correctly and return the same solved board since the loop finds no empty cells and ends.
Edge case 2: A Sudoku board with no solution (though the problem statement guarantees a solution exists). While the problem guarantees a solution, a robust implementation should handle this. In this case, the algorithm would exhaust all possibilities without finding a valid assignment and return `false` from the initial backtrack call.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not properly resetting the board state during backtracking. Failing to remove the assigned value from the row, column, and box sets (or boolean arrays) after a failed attempt will lead to incorrect results.

✗Common mistake 2: Incorrectly calculating the box ID. The box ID should be calculated as (row / 3) * 3 + (col / 3). Using incorrect formulas can lead to incorrect validation and incorrect solutions.

✗Common mistake 3: Forgetting to check for conflicts before placing a number. Not validating Sudoku rules before assignment results in an invalid board.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: The backtracking algorithm used in Sudoku solvers is applicable to various constraint satisfaction problems, such as scheduling problems (e.g., assigning tasks to employees, scheduling meetings), resource allocation, and game playing (e.g., solving mazes, playing chess).

🏦Real-world scenario 2: Sudoku solving techniques are used in software that generates Sudoku puzzles of varying difficulty levels. These techniques are also helpful for designing other logic puzzles.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

It's okay to not finish hard problems in interviews. Show your problem-solving process.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: July 8, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 13

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 6

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJun 29

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

How do I choose between a hash map and a hash set?

Use a hash set when you only need to track presence/absence of elements (like detecting duplicates). Use a hash map when you need to associate values with keys (like counting frequencies or storing indices). Hash sets use less memory since they only store keys.

Is it okay to not fully solve hard problems in interviews?

Yes! Interviewers care more about your problem-solving process than the final answer. Demonstrate: clear communication, systematic approach, ability to recognize when to pivot strategies, and graceful handling of hints. Partial progress with good reasoning is valued.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Sudoku Solver"?

For this hard-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether hash table techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?