Problem 37

Abstract / Summary

Fill empty cells in a 9x9 grid so each row column and 3x3 box has digits 1 to 9 without repetition.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 0037.py

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        def simplify(solution):
            changes = 0
            for x in range(9):
                for y in range(9):
                    # solved cell
                    if len(solution[x][y]) == 1:
                        continue

                    avoid = set()
                    for i in range(9):
                        # same column
                        if len(solution[x][i]) == 1:
                            avoid.add(solution[x][i][0])
                        # same row
                        if len(solution[i][y]) == 1:
                            avoid.add(solution[i][y][0])
                        # same box
                        xx = (x // 3) * 3 + i % 3
                        yy = (y // 3) * 3 + i // 3
                        if len(solution[xx][yy]) == 1:
                            avoid.add(solution[xx][yy][0])

                    for a in avoid:
                        if a in solution[x][y]:
                            solution[x][y].remove(a)
                            changes += 1
                    if len(solution[x][y]) == 0:
                        return -1

            return changes


        def validate(solution): # only checks if one candidate per cell, no further validation
            for x in range(9):
                for y in range(9):
                    if len(solution[x][y]) > 1:
                        return False
                    me = solution[x][y][0]
                    for i in range(9):
                        if i != x and me == solution[i][y][0]:
                            return False
                        if i != y and me == solution[x][i][0]:
                            return False
                        xx = (x // 3) * 3 + i % 3
                        yy = (y // 3) * 3 + i // 3
                        if (x != xx or y != yy) and me == solution[xx][yy][0]:
                            return False
            return True


        def isFinished(solution): # only checks if one candidate per cell, no further validation
            for x in range(9):
                for y in range(9):
                    if len(solution[x][y]) > 1:
                        return False
            return True


        def solve(deeper):
            # deep copy (why so weird in Python ?)
            attempt = []
            for x in range(9):
                r = []
                for y in range(9):
                    r.append(deeper[x][y].copy())
                attempt.append(r)

            if simplify(attempt) < 0:
                return None

            if isFinished(attempt):
                return attempt if validate(attempt) else None

            for x in range(9):
                for y in range(9):
                    if len(deeper[x][y]) > 1:
                        guess = deeper[x][y]
                        for c in guess:
                            attempt[x][y] = [ c ]
                            complete = solve(attempt)
                            if complete != None:
                                return complete
                        return None
            return attempt


        # 9 strings, each 9 bytes
        candidates = []
        for row in board:
            r = []
            for cell in row:
                if cell == ".":
                    r.append([ 1,2,3,4,5,6,7,8,9 ])
                else:
                    r.append([ int(cell) ])
            candidates.append(r)

        s = simplify(candidates)
        while s > 0:
            s = simplify(candidates)

        # let's go
        final = solve(candidates)

        # convert to Leetcode format
        result = []
        for x in range(9):
            r = []
            for y in range(9):
                board[x][y] = str(final[x][y][0])
115 lines | 4033 bytes | submitted August 31, 2023 | GitHub   11% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 66% (1+ million submissions).

Typical patterns to solve this problem:
  • Array
  • Backtracking
  • Hash Table
  • Matrix
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The implementation solves a standard 9×9 Sudoku puzzle by maintaining, for every cell, a list of possible digits. The algorithm proceeds in three phases:

  1. Candidate construction - each empty cell receives the full digit set {1…9}, while pre-filled cells receive a singleton list.
  2. Constraint propagation - the simplify routine repeatedly removes digits that are already fixed in the same row, column, or 3×3 box.
  3. Depth-first search with backtracking - when propagation cannot finish the board, the solver guesses a candidate, recurses, and restores state on failure.

All modifications are performed on the supplied board in-place, satisfying the LeetCode contract.

Candidate Initialization

The board is scanned once to build a parallel structure candidates. For a dot (".") the full range 1-9 is stored; otherwise the digit is converted to an integer and wrapped in a list.

candidates = []
for row in board:
    r = []
    for cell in row:
        if cell == ".":
            r.append([1,2,3,4,5,6,7,8,9])
        else:
            r.append([int(cell)])
    candidates.append(r)

This step guarantees that every cell has at least one possible value, establishing a well-defined starting point for the solver.

Constraint Propagation (simplify)

simplify iterates over every cell, collecting digits that are already resolved in the same row, column, and box into a set avoid. Those digits are then removed from the current cell’s candidate list. The function returns the total number of eliminations performed, or -1 if a cell loses all candidates, signalling an immediate contradiction.

def simplify(solution):
    changes = 0
    for x in range(9):
        for y in range(9):
            if len(solution[x][y]) == 1:
                continue
            avoid = set()
            for i in range(9):
                if len(solution[x][i]) == 1:
                    avoid.add(solution[x][i][0])
                if len(solution[i][y]) == 1:
                    avoid.add(solution[i][y][0])
                xx = (x // 3) * 3 + i % 3
                yy = (y // 3) * 3 + i // 3
                if len(solution[xx][yy]) == 1:
                    avoid.add(solution[xx][yy][0])
            for a in avoid:
                if a in solution[x][y]:
                    solution[x][y].remove(a)
                    changes += 1
            if len(solution[x][y]) == 0:
                return -1
    return changes

Edge Cases Handled

  • Cells that are already solved are skipped, preventing unnecessary work.
  • The use of a set eliminates duplicate checks when a digit appears in multiple intersecting constraints.
  • Returning -1 when a candidate list becomes empty captures an impossible configuration early, allowing the caller to backtrack without further recursion.

Validation (validate)

After a full assignment is reached, validate confirms that each digit appears exactly once in its row, column, and box. It assumes every cell holds a singleton list, so the check is a simple equality comparison.

def validate(solution):
    for x in range(9):
        for y in range(9):
            if len(solution[x][y]) > 1:
                return False
            me = solution[x][y][0]
            for i in range(9):
                if i != x and me == solution[i][y][0]:
                    return False
                if i != y and me == solution[x][i][0]:
                    return False
                xx = (x // 3) * 3 + i % 3
                yy = (y // 3) * 3 + i // 3
                if (x != xx or y != yy) and me == solution[xx][yy][0]:
                    return False
    return True

The function gracefully handles the case where a cell still contains multiple candidates by returning False immediately, preventing false positives.

Completion Check (isFinished)

isFinished determines whether every cell has been reduced to a single candidate, serving as a fast termination test before invoking the more expensive validate.

def isFinished(solution):
    for x in range(9):
        for y in range(9):
            if len(solution[x][y]) > 1:
                return False
    return True

Recursive Solver (solve)

The core search routine creates a deep copy of the current candidate grid, applies simplify, and then decides the next action:

  • If propagation yields a contradiction (simplify < 0), the branch is abandoned.
  • If the board is finished, validate decides whether the solution is legal.
  • Otherwise, the algorithm selects the first cell with multiple candidates, iterates over its possibilities, forces each guess, and recurses.
def solve(deeper):
    attempt = []
    for x in range(9):
        r = []
        for y in range(9):
            r.append(deeper[x][y].copy())
        attempt.append(r)

    if simplify(attempt) < 0:
        return None

    if isFinished(attempt):
        return attempt if validate(attempt) else None

    for x in range(9):
        for y in range(9):
            if len(deeper[x][y]) > 1:
                guess = deeper[x][y]
                for c in guess:
                    attempt[x][y] = [c]
                    complete = solve(attempt)
                    if complete != None:
                        return complete
                return None
    return attempt

Edge Cases Handled

  • The deep copy isolates each recursive branch, ensuring that guesses do not corrupt sibling branches.
  • The early return after trying all candidates for a cell prevents unnecessary exploration of other cells when the current branch is already invalid.
  • The final return attempt acts as a safety net for the unlikely case where the loop finishes without finding a multi-candidate cell, returning the partially solved grid.

Iterative Simplification Loop

Before invoking the recursive search, the solver repeatedly calls simplify until no further reductions occur. This maximizes deterministic deductions and reduces the depth of the subsequent search.

s = simplify(candidates)
while s > 0:
    s = simplify(candidates)

The loop stops when simplify reports zero changes, indicating that constraint propagation has reached a fixed point.

Final Board Conversion

When a complete candidate grid is obtained, the solver writes the solved digits back into the original board as strings, matching the expected output format.

final = solve(candidates)
for x in range(9):
    for y in range(9):
        board[x][y] = str(final[x][y][0])

Because final is guaranteed to contain a single digit per cell, the conversion is straightforward and safe.

Performance Optimizations

  • Set-based avoidance - using a Python set to collect digits already placed in intersecting units avoids repeated linear scans and duplicate work.
  • Early contradiction detection - simplify aborts as soon as a cell loses all candidates, preventing deeper recursion on an impossible branch.
  • Fixed-point propagation - the outer loop runs simplify only while it makes progress, eliminating redundant passes once the board is stable.
  • Targeted deep copy - the copy operation replicates only the candidate lists, not the entire board, keeping memory overhead modest while preserving isolation between recursive calls.
  • First-unsolved-cell heuristic - by selecting the first cell with multiple candidates, the solver avoids the overhead of scanning for the minimal-size candidate set, which in practice yields acceptable performance on typical puzzles.

These choices collectively keep the solver responsive for standard Sudoku instances while maintaining clear, readable code.

written by openai gpt

ELI5 - Simplified Explanation

Imagine playing a big puzzle game where you have a square grid filled with empty boxes. This code is like a smart friend helping you play Sudoku. To start, this friend looks at the grid and writes down every number from one to nine in the empty boxes because any of those numbers might work. If a box already has a number, the friend just keeps that one.

After writing down all the possibilities, the friend starts following the three special rules of Sudoku. The friend checks every row, every column, and every little square group to see which numbers are already taken. Whenever a number is found in a row or column, the friend crosses it out from the options in the other empty boxes. This makes the list of possibilities smaller and clearer.

Sometimes, after crossing out numbers, only one option is left for a box. When that happens, the friend knows that number must go there. This keeps happening over and over until many boxes are solved.

If the board still has boxes with more than one option and no more simple moves are left, the friend takes a little risk. The friend picks a box with a few choices, guesses one, and sees if the rest of the puzzle stays correct. If the guess leads to a mistake, the friend goes back and tries a different choice. The friend keeps guessing and checking until every single box is filled with the right number, which finishes the whole game.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 29 | median = 6 | μ = 5.48 | σ = 1.69

Complexity Analysis

not analyzed yet

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Python Java TS
WalkCCC C++ Python Java
leetcode.ca C++ Python C# Java Go PHP
LeetcodeHelp C++ Python Java
MemoryLimitExceeded C++ Python
Progiez C++ Python Java
github aylei Rust
begeekmyfriend C
BigEggStudy C#
black-shadows Python
charles-wangkai Java
chenyanzhe C++
everthis JS
gaosq0604 Python
halfrost Go
haoel C++
JoshCrozier JS
keineahnung2345 C++
lennylxx C++
linouk23 C++
lkwq007 Python
luangong C++
MacJim C++
martianoff Scala
qiyuangong Python
ruoru Rust
shreymehul C#
suxrobGM C#
vli02 C
wisdompeak C++
XiaotaoGuo C++
zfang399 C++
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, C#, Go, Java, PHP, Python
LeetcodeHelp C++, Java, Python
MemoryLimitExceeded Python, C++
Progiez C++, Java, Python
aylei Rust
begeekmyfriend C
BigEggStudy C#
black-shadows Python, Python
charles-wangkai Java
chenyanzhe C++
everthis JavaScript
gaosq0604 Python
halfrost Go
haoel C++
JoshCrozier JavaScript
keineahnung2345 C++
lennylxx C++
linouk23 C++
lkwq007 Python
luangong C++
MacJim C++
martianoff Scala
qiyuangong Python
ruoru Rust
shreymehul C#
suxrobGM C#
vli02 C
wisdompeak C++
XiaotaoGuo C++
zfang399 C++
47 links | 32 authors | 11 languages

Videos

These are a few popular YouTube videos for this problem:
YouTube video 'LeetCode 37. Sudoku Solver'
Happy Coding 17 mins
LeetCode 37. Sudoku Solver
YouTube video '[Java] Leetcode 37. Sudoku Solver [Backtracking #8]'
Eric Programming 18 mins
[Java] Leetcode 37. Sudoku Solver [Backtracking #8]
YouTube video 'Sudoku Solver | Simple Explanation | Leetcode 37 | codestorywithMIK'
codestorywithMIK 27 mins
Sudoku Solver | Simple Explanation | Leetcode 37 | codestorywithMIK
YouTube video 'Sudoku Solver - LeetCode 37 - JavaScript'
AlgoJS 10 mins
Sudoku Solver - LeetCode 37 - JavaScript
YouTube video 'Sudoku Solver | Leetcode 37 | Live coding session 🔥🔥🔥'
Coding Decoded 14 mins
Sudoku Solver | Leetcode 37 | Live coding session 🔥🔥🔥
YouTube video 'Sudoku Solver Python Solution - LeetCode #37'
Professor Oakes 10 mins
Sudoku Solver Python Solution - LeetCode #37
YouTube video 'LeetCode 37: Sudoku Solver | C# Solution | Backtracking Algorithm |'
Code Scribbler 13 mins
LeetCode 37: Sudoku Solver | C# Solution | Backtracking Algorithm |
YouTube video '37. Sudoku Solver | Leetcode Daily - Python'
Leetcode Daily 6 mins
37. Sudoku Solver | Leetcode Daily - Python
YouTube video 'Hard Leetcode 37. Sudoku Solver | Python | Backtracking'
NeedCode⚡ 13 mins
Hard Leetcode 37. Sudoku Solver | Python | Backtracking
YouTube video 'Daily Leetcode #1979: Aug 31, 2025 - 37. Sudoku Solver'
Programming Live with Larry 14 mins
Daily Leetcode #1979: Aug 31, 2025 - 37. Sudoku Solver
YouTube video 'Leetcode 37  Sudoku Solver | Algorithm & Solution | Meta | Amazon | Google 🔥 #leetcode #sudokusolver'
AccelerateAI Careers 14 mins
Leetcode 37 Sudoku Solver | Algorithm & Solution | Meta | Amazon | Google 🔥 #leetcode #sudokusolver
YouTube video 'Sudoku Solver - LeetCode 37 - Python'
Alpha-Code 27 mins
Sudoku Solver - LeetCode 37 - Python
YouTube video 'Leetcode Question 37 "Sudoku Solver" in Javascript'
Ghumman Tech 9 mins
Leetcode Question 37 "Sudoku Solver" in Javascript
YouTube video 'Daily Leetcode #508: Aug 21, 2021 - 37. Sudoku Solver'
Programming Live with Larry 16 mins
Daily Leetcode #508: Aug 21, 2021 - 37. Sudoku Solver
YouTube video 'LeetCode 37 🔥 Sudoku Solver | Backtracking + Optimal Java Solution | Full Explanation + Dry Run'
Study Placement 22 mins
LeetCode 37 🔥 Sudoku Solver | Backtracking + Optimal Java Solution | Full Explanation + Dry Run
YouTube video 'Sudoku Solver | LeetCode 37 | Backtracking | Hard | Java Code | Developer Coder'
Developer Coder 29 mins
Sudoku Solver | LeetCode 37 | Backtracking | Hard | Java Code | Developer Coder
YouTube video '37. Sudoku Solver | Leetcode Daily Challenge | Backtracking'
Eye on AI and DSA 18 mins
37. Sudoku Solver | Leetcode Daily Challenge | Backtracking
YouTube video 'Sudoku Solver | LeetCode 37 - Python'
impoldev 13 mins
Sudoku Solver | LeetCode 37 - Python
YouTube video 'Leetcode 37. Sudoku Solver'
ExpertFunda 30 mins
Leetcode 37. Sudoku Solver
YouTube video 'LeetCode 37 | Sudoku Solver | Java'
Sleepy Cracker 14 mins
LeetCode 37 | Sudoku Solver | Java
20 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

1 similar problem

Solved On The Same Day

27 solutions   August 31, 2023

Fun Facts

This is my longest hard solution with 4033 bytes.

1 fun fact

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality