Solving Sudoku Solver Algorithm with Backtracking

1. Introduction and Core Concepts

The sudoku solver algorithm is a classic example of a constraint satisfaction problem (CSP) solved through systematic search. A standard Sudoku puzzle consists of a 9x9 grid divided into nine 3x3 subgrids, or boxes. The objective is to fill the grid so that every row, every column, and every 3x3 box contains the digits 1 through 9 exactly once. Some cells are pre-filled as clues, and the solver must deduce the remaining values while respecting all constraints. While humans use logical deduction and pattern recognition, computers excel at exploring the vast combinatorial search space with algorithmic precision.

At its heart, the Sudoku solver algorithm is not just about solving a puzzle; it is a blueprint for solving any problem where you must make a sequence of choices under constraints. The most famous and pedagogically important approach is backtracking, a depth-first search strategy that incrementally builds candidates and abandons a path as soon as it determines the candidate cannot lead to a valid solution. This trial-and-error mechanism mirrors how a human might solve Sudoku with pencil and eraser, but executed with exhaustive and systematic rigor.

Understanding the sudoku solver algorithm matters far beyond recreational puzzles. It introduces fundamental concepts in artificial intelligence, recursion, and algorithmic design that power real systems from compilers to scheduling engines. Because Sudoku has a well-defined, finite, and verifiable solution space, it serves as an ideal benchmark for teaching and testing search algorithms. Mastering this algorithm provides a transferable mental model for tackling NP-complete problems, where verifying a solution is easy but finding one may require exponential search in the worst case.

What Is a Sudoku Solver Algorithm?

Formally, a Sudoku solver algorithm is any computational procedure that takes an incompletely filled 9x9 grid as input and produces a completed grid that satisfies all Sudoku constraints, or correctly reports that no such completion exists. The input is typically represented as a two-dimensional array where 0 or '.' denotes an empty cell. The output is the same structure with all cells filled. A robust solver must be complete, meaning it will find a solution if one exists, and sound, meaning it will never return an invalid board.

Why Backtracking Is a Natural Fit

Backtracking is a natural fit because Sudoku is an incremental constraint problem. You can place a number in an empty cell, check if it violates any constraints, and then proceed to the next empty cell. If you reach a dead end where no valid number can be placed, you backtrack to the previous decision point and try a different number. This recursive depth-first exploration guarantees that all possibilities will eventually be examined without having to generate every possible board configuration upfront, which would be astronomically large at 9^81 possibilities.

2. How It Works

The backtracking mechanism for Sudoku can be understood as a depth-first traversal of a state-space tree. Each node in the tree represents a partially filled board, and each edge represents placing a valid digit in the next empty cell. The root is the initial puzzle, and leaves are either complete valid solutions or dead-end boards where no legal move exists. The algorithm explores this tree by going as deep as possible along one branch before backtracking.

The theoretical foundation rests on three core operations that are repeated recursively. First, the algorithm must select an unassigned variable, which in Sudoku is an empty cell. The simplest strategy is to pick the first empty cell found by scanning row-major order, though more advanced heuristics can dramatically improve performance. Second, it must order the domain values, typically trying digits 1 through 9 in sequence. Third, and most critically, it must perform constraint checking to test whether assigning a value would keep the board consistent with Sudoku rules.

Constraint checking is what enables pruning, the key to backtracking's efficiency. Instead of blindly filling the entire board and then checking for validity at the end, the algorithm validates each placement immediately. If placing a '5' in row 0, column 2 conflicts with another '5' already in the same row, column, or box, that entire subtree is discarded without further exploration. This early failure detection prevents the algorithm from wasting time on billions of invalid completions that share the same flawed prefix.

When a dead end is reached, the algorithm backtracks. This means it undoes the most recent assignment, resetting the cell to empty, and tries the next candidate value for that cell. If all nine digits have been exhausted for a cell, it backtracks even further to the previous cell. This unwinding is naturally implemented via recursion, where the call stack implicitly remembers the path taken. The recursion terminates successfully when no empty cells remain, indicating a solution, or unsuccessfully when the initial call has tried all values and failed, indicating the puzzle is unsolvable.

The Backtracking Paradigm in Detail

1. Find: Locate the next empty cell. If none exists, the puzzle is solved.
2. Try: For each digit 1-9, check if it is safe to place in that cell.
3. Place & Recurse: If safe, place the digit and recursively attempt to solve the rest of the puzzle.
4. Backtrack: If the recursive call fails, remove the digit (reset to 0) and try the next digit.
5. Fail: If no digit leads to a solution, return failure to trigger backtracking in the caller.

3. Implementation

Implementing a sudoku solver algorithm in Python is straightforward because the board maps naturally to a 2D list and recursion handles the backtracking state. Below are progressively more optimized implementations, each building on the same core logic but improving constraint checking and cell selection.

Basic Backtracking Implementation

This first implementation prioritizes clarity. It uses three helper functions: find_empty to scan for the next zero, is_valid to check row, column, and box constraints, and solve to perform the recursive search. It is complete and correct for any valid 9x9 puzzle, though it may be slow on very sparse or hard puzzles.

def find_empty(board):
    """Find next empty cell (value 0) scanning row-major order."""
    for i in range(9):
        for j in range(9):
            if board[i][j] == 0:
                return (i, j)  # row, col
    return None

def is_valid(board, row, col, num):
    """Check if num can be placed at board[row][col] without conflict."""
    # Check row
    if num in board[row]:
        return False
    # Check column
    for i in range(9):
        if board[i][col] == num:
            return False
    # Check 3x3 box
    box_row, box_col = 3 * (row // 3), 3 * (col // 3)
    for i in range(3):
        for j in range(3):
            if board[box_row + i][box_col + j] == num:
                return False
    return True

def solve(board):
    """Solve Sudoku using naive backtracking. Modifies board in-place."""
    empty = find_empty(board)
    if not empty:
        return True  # No empty cells - solved
    row, col = empty

    for num in range(1, 10):  # try 1 through 9
        if is_valid(board, row, col, num):
            board[row][col] = num  # make tentative assignment
            if solve(board):       # recurse
                return True
            board[row][col] = 0    # backtrack - undo assignment
    return False  # trigger backtracking

# Example usage:
# board = [[5,3,0,0,7,0,0,0,0], ...]
# solve(board)
# print(board)

Optimized Implementation with Constraint Sets

The naive is_valid scans the entire row, column, and box on every call, which is O(9) per check. We can achieve O(1) validation by maintaining three arrays of sets that track which numbers are already used in each row, column, and box. This preprocessing step significantly reduces constant factors and is essential for harder puzzles where millions of checks are performed.

def solve_optimized(board):
    """Optimized solver using sets for O(1) validity checks."""
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]

    # Initialize sets with initial clues
    empties = []
    for i in range(9):
        for j in range(9):
            if board[i][j] != 0:
                num = board[i][j]
                rows[i].add(num)
                cols[j].add(num)
                boxes[(i // 3) * 3 + j // 3].add(num)
            else:
                empties.append((i, j))

    def backtrack(k):
        # k is index in empties list
        if k == len(empties):
            return True
        i, j = empties[k]
        box_id = (i // 3) * 3 + j // 3
        for num in range(1, 10):
            if num not in rows[i] and num not in cols[j] and num not in boxes[box_id]:
                # place
                board[i][j] = num
                rows[i].add(num)
                cols[j].add(num)
                boxes[box_id].add(num)

                if backtrack(k + 1):
                    return True

                # undo
                board[i][j] = 0
                rows[i].remove(num)
                cols[j]..remove(num)
                boxes[box_id].remove(num)
        return False

    return backtrack(0)

MRV Heuristic: Choosing the Most Constrained Cell

Instead of picking the first empty cell, the Minimum Remaining Values (MRV) heuristic selects the empty cell with the fewest legal candidates. This fails faster on bad branches and dramatically prunes the search tree. A cell with only one possible value is forced and should be filled immediately.

def solve_mrv(board):
    """Solver with MRV heuristic - picks cell with fewest candidates."""
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]
    for i in range(9):
        for j in range(9):
            if board[i][j] != 0:
                v = board[i][j]
                rows[i].add(v)
                cols[j].add(v)
                boxes[(i // 3) * 3 + j // 3].add(v)

    def get_candidates(r, c):
        if board[r][c] != 0:
            return []
        box_id = (r // 3) * 3 + c // 3
        used = rows[r] | cols[c] | boxes[box_id]
        return [n for n in range(1, 10) if n not in used]

    def find_best_empty():
        best = None
        min_candidates = 10
        for i in range(9):
            for j in range(9):
                if board[i][j] == 0:
                    cands = get_candidates(i, j)
                    if len(cands) < min_candidates:
                        min_candidates = len(cands)
                        best = (i, j, cands)
                        if min_candidates == 1:
                            return best
        return best

    def backtrack():
        cell = find_best_empty()
        if not cell:
            return True  # solved
        r, c, candidates = cell
        if len(candidates) == 0:
            return False  # dead end
        box_id = (r // 3) * 3 + c // 3
        for num in candidates:
            board[r][c] = num
            rows[r].add(num)
            cols[c].add(num)
            boxes[box_id].add(num)
            if backtrack():
                return True
            board[r][c] = 0
            rows[r].remove(num)
            cols[c].remove(num)
            boxes[box_id].remove(num)
        return False

    return backtrack()

Counting All Solutions and Detecting Uniqueness

Some puzzles have multiple solutions. For puzzle generation and validation, we need to count solutions rather than just find one. This variant explores the entire search tree and counts leaves that are valid completions, with an early exit if more than one solution is found.

def count_solutions(board, limit=2):
    """Count number of solutions up to limit. Returns count."""
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]
    empties = []
    for i in range(9):
        for j in range(9):
            if board[i][j] != 0:
                rows[i].add(board[i][j])
                cols[j].add(board[i][j])
                boxes[(i // 3) * 3 + j // 3].add(board[i][j])
            else:
                empties.append((i, j))

    count = 0
    def backtrack(k):
        nonlocal count
        if count >= limit:  # early stop if we already found enough
            return
        if k == len(empties):
            count += 1
            return
        i, j = empties[k]
        box_id = (i // 3) * 3 + j // 3
        for num in range(1, 10):
            if num not in rows[i] and num not in cols[j] and num not in boxes[box_id]:
                board[i][j] = num
                rows[i].add(num); cols[j].add(num); boxes[box_id].add(num)
                backtrack(k + 1)
                board[i][j] = 0
                rows[i].remove(num); cols[j].remove(num); boxes[box_id].remove(num)

    backtrack(0)
    return count

# Usage: if count_solutions(puzzle) == 1: puzzle has unique solution

4. Step-by-Step Example

Consider a simplified 4x4 Sudoku (with 2x2 boxes) to make the walkthrough tractable, but the logic scales directly to 9x9. Suppose we have the board where 0 denotes empty: Row0: [1, 0, 0, 4], Row1: [0, 0, 1, 0], Row2: [0, 1, 0, 0], Row3: [4, 0, 0, 1]. The constraints are identical: each row, column, and 2x2 box must contain 1-4. We will trace the naive row-major backtracking solver.

Step 1: find_empty returns (0,1), the first zero. The solver tries num=1. is_valid fails because row 0 already contains 1. It tries num=2. Row 0 has no 2, column 1 has 1, and the top-left 2x2 box contains 1, so 2 is valid. It places 2 at (0,1). The board becomes [1,2,0,4] on the first row and recurses.

Step 2: Next empty is (0,2). Try 1: column 2 already has 1 at (1,2), so invalid. Try 2: row 0 already has 2, invalid. Try 3: no conflict in row, column, or box, so place 3 at (0,2). Board is now [1,2,3,4] and recurses. Next empty is (1,0). Try 1: row 1 has 1, invalid. Try 2: column 0 has 1 and 4, box top-left has 1 and 2, so 2 is valid? Wait column 0 currently has 1 at (0,0) and 4 at (3,0), so 2 is valid. Place 2 at (1,0).

Step 3: Next empty is (1,1). Try 1: box top-left now has 1,2,2? Actually box contains (0,0)=1, (0,1)=2, (1,0)=2 - duplicate 2 already indicates our previous placement may lead to dead end, but validation would have caught it? Let's see more systematically: After placing 2 at (1,0), the box top-left has 1,2,2 - but our is_valid for (1,0) checked column and row and box before placing, and box had only 1 and 2, so it seemed valid. However, the next cell (1,1) now has no valid candidates: 1 conflicts with row, 2 conflicts with row/box, 3 conflicts with column (0,2)=3, 4 conflicts with box/column. So all digits fail.

Step 4: The solver returns False for (1,1), triggering backtrack. It resets (1,0) from 2 to 0 and tries the next digit for (1,0), which is 3. Check validity: row 1 has 1, so 3 is valid (row has no 3, column 0 has 1,4, box has 1,2). Place 3 at (1,0). Now (1,1) is next. Try 1: invalid (row has 1), 2: valid? Row 1 has 1,3, column 1 has 2,1, box has 1,2,3 - 2 not in row/col/box? Actually column 1 has 2 at (0,1) so 2 invalid. Try 3 invalid (row), 4 valid. Place 4 at (1,1). The search continues successfully from this new branch, eventually filling the board to a valid solution: [1,2,3,4], [3,4,1,2], [2,1,4,3], [4,3,2,1]. This demonstrates how backtracking abandons a locally valid but globally impossible prefix and recovers.

Key Takeaways from the Trace

This trace highlights that early pruning is not enough to avoid all dead ends; some conflicts only become apparent several levels deeper. The algorithm's strength is that it systematically explores and recovers without manual intervention. The MRV heuristic would have avoided this dead end entirely by picking the most constrained cell first, rather than strictly row-major order.

5. Complexity Analysis

Analyzing the sudoku solver algorithm requires distinguishing between theoretical worst-case bounds and practical performance on typical puzzles. Sudoku is NP-complete when generalized to NxN grids, so no known polynomial-time algorithm exists for all cases. Backtracking is essentially an optimized brute-force search with pruning.

In the worst case, where the board is empty or has very few clues, the algorithm may explore an exponential number of states. For a 9x9 board with m empty cells, the naive upper bound is O(9^m), since each empty cell has up to 9 candidates. With m=60 for a hard puzzle, this is astronomically large. However, constraint propagation prunes most branches early, so the effective branching factor is far lower than 9. The best case occurs when the puzzle is already solved or nearly solved, requiring only O(m) time to verify and fill the last few cells.

Space complexity is much more favorable. The board itself is O(81) = O(1) for a fixed 9x9 size, or O(N^2) for NxN. The recursion depth is at most m (the number of empty cells), so the call stack uses O(m) space. When using auxiliary sets for rows, columns, and boxes, we add O(N) additional space, which remains constant for standard Sudoku. Thus, backtracking is highly space-efficient compared to breadth-first search, which would need to store exponentially many boards.

For generalized NxN Sudoku where N = n² (e.g., 9 = 3², 16 = 4²), the worst-case time is O(N^(N²)) and more precisely O(n^(n² * m)). In practice, puzzles designed for humans with 17-30 clues are solved by optimized backtracking in well under a millisecond on modern hardware. The hardest known 17-clue puzzles may still require millions of recursive calls without heuristics, but with MRV and forward checking they become tractable.

6. Variations and Optimizations

While naive backtracking is sufficient for easy puzzles, production solvers and competitive programming solutions employ several powerful optimizations that can yield 10x to 1000x speedups. These techniques do not change the worst-case complexity class but dramatically reduce the average-case search space.

Constraint propagation is the most impactful improvement. Before or during search, the solver repeatedly applies human-like deduction rules: if a cell has only one candidate (naked single), fill it; if a digit can only go in one place in a row, column, or box (hidden single), fill it. This is often implemented as forward checking or maintaining arc consistency (AC-3). By interleaving propagation with backtracking, many cells are filled deterministically without branching at all.

Heuristics for variable and value ordering also matter enormously. The Minimum Remaining Values (MRV) heuristic, as shown earlier, selects the empty cell with the fewest legal candidates. The related Degree heuristic breaks ties by choosing the cell involved in the most constraints. For value ordering, the Least Constraining Value (LCV) heuristic tries digits that eliminate the fewest candidates from neighboring cells first, increasing the chance of finding a solution early. Together, MRV + LCV can reduce search nodes by orders of magnitude.

Common Optimized Variants

• Backtracking + Forward Checking: After each assignment, remove the assigned value from the candidate sets of peers (same row/col/box). If any peer's candidate set becomes empty, backtrack immediately.
• Backtracking + Arc Consistency (AC-3): Enforce that for every pair of unassigned cells sharing a constraint, each value in one cell's domain has a compatible value in the other's domain. More expensive but stronger pruning.
• Dancing Links (DLX) / Algorithm X: Model Sudoku as an exact cover problem and solve with Knuth's Algorithm X using doubly linked lists. Extremely fast and elegant, often the fastest for 9x9.
• Bitmasking: Represent candidate sets as 9-bit integers (bit i set means digit i+1 is possible). Validity checks and updates become single bitwise operations, which are blazingly fast in Python or C.
• Iterative Deepening & Memoization: Use iterative stack instead of recursion to avoid recursion limits, and memoize dead-end board hashes to avoid revisiting the same failed state via different paths.

For extremely large or hard puzzles, stochastic methods like simulated annealing or genetic algorithms are sometimes used, but they are incomplete and not guaranteed to find a solution. For standard 9x9 Sudoku, deterministic backtracking with propagation remains the gold standard.

7. Real-World Applications

Although Sudoku itself is a puzzle, the underlying backtracking and constraint satisfaction techniques are foundational to many real-world systems. Any problem that involves assigning values to variables under constraints can be mapped to the same search paradigm.

In scheduling and resource allocation, the sudoku solver algorithm pattern is directly applicable. University timetabling, where courses, rooms, professors, and time slots must be assigned without conflicts, is a large-scale Sudoku-like CSP. Airline crew scheduling, job-shop scheduling in manufacturing, and sports tournament scheduling all use backtracking with constraint propagation to find feasible schedules. The rows, columns, and boxes become resources and time constraints.

In electronic design automation (EDA), circuit board layout and graph coloring for register allocation in compilers rely on similar search. Assigning frequencies to cell towers so that nearby towers do not interfere is a graph coloring problem isomorphic to Sudoku. Similarly, in databases, query optimization and dependency resolution use backtracking to explore plan spaces. Even web servers use backtracking for routing and middleware resolution when multiple handlers could match a request.

Beyond these, Sudoku solvers are widely used as benchmarks for SAT solvers and AI research. Modern SAT solvers can solve Sudoku by translating it to conjunctive normal form (CNF) and applying highly optimized backtracking (DPLL/CDCL). Studying Sudoku thus provides intuition for how industrial solvers handle problems with millions of variables.

8. Comparison with Alternatives

Backtracking is not the only way to solve Sudoku. Depending on requirements for speed, guarantee of solution, and implementation complexity, other approaches may be preferable. Understanding the trade-offs helps you choose the right tool for interviews, production code, or research.

Brute force without pruning generates every possible completion and tests validity at the end. It is conceptually simple but hopelessly slow, with 9^81 checks. Backtracking improves this by pruning early. Constraint propagation with backtracking adds deterministic deduction to reduce branching. Dancing Links (DLX) reframes Sudoku as an exact cover problem and uses an efficient data structure to make covering and uncovering constraints extremely fast. Stochastic local search methods like simulated annealing start with a random complete board and iteratively fix conflicts by swapping values; they are fast for many puzzles but incomplete and may get stuck in local minima.

For coding interviews, naive or MRV backtracking is almost always expected because it demonstrates recursion and pruning clearly in a short amount of code. For building a high-performance Sudoku service that solves millions of puzzles per day, DLX or bitmask-optimized backtracking with propagation is the industry choice. For research on extremely large Sudoku (e.g., 25x25), hybrid SAT/CSP solvers outperform pure backtracking.

9. Common Mistakes and Best Practices

Even experienced developers introduce subtle bugs when implementing a sudoku solver algorithm. The recursive nature and in-place mutation of the board make it easy to create errors that pass simple tests but fail on harder puzzles or edge cases.

A classic mistake is forgetting to backtrack correctly. After a recursive call fails, you must reset the cell to 0 and also revert any auxiliary data structures like row/col/box sets. Omitting the undo step leaves phantom constraints that incorrectly prune valid branches later. Another frequent error is shallow copying the board when counting solutions or trying multiple branches; using board_copy = board in Python copies the reference, not the data, so mutations leak across branches. Always use [row[:] for row in board] or copy.deepcopy when you need an independent copy.

Performance pitfalls are equally common. Scanning the entire board for the next empty cell on every recursion is wasteful; precomputing the list of empties or using MRV avoids repeated O(N²) scans. Similarly, recomputing validity by scanning rows and columns each time is slower than maintaining sets or bitmasks. Not handling invalid initial boards is another oversight: if the input already has duplicate digits in a row, the solver should immediately return failure rather than searching fruitlessly.

Pitfalls to Avoid

• Mutating without undoing: Always pair board[r][c] = num with a corresponding board[r][c] = 0 on backtrack, and keep auxiliary sets in sync.
• Incorrect box index: The box index is (r // 3) * 3 + c // 3, not r // 3 + c // 3 or 3 * r + c. Test this formula thoroughly.
• Off-by-one in digit range: Digits are 1-9 inclusive, so use range(1, 10), not range(9) or range(1, 9).
• Recursion depth: Python's default recursion limit is ~1000, which is safe for 9x9 (max depth 81) but may be exceeded for larger variants. Consider iterative stack for NxN with N > 16.
• Not validating input: Validate that the board is 9x9 and contains only 0-9 before solving to avoid index errors.

Best Practices

• Use bitmasks or sets for O(1) checks: Maintain rows, cols, boxes sets and update them incrementally.
• Implement MRV: Always pick the most constrained cell next; it is a few extra lines and yields massive speedups.
• Separate solver from I/O: Keep the solver pure (takes board, returns bool) and handle parsing/printing outside. This makes unit testing trivial.
• Write deterministic tests: Test on easy, hard, empty, already solved, and unsolvable boards, and verify that the solution satisfies all constraints.
• Profile before optimizing: For 9x9, even naive backtracking is often fast enough. Only add AC-3 or DLX if profiling shows a bottleneck.

10. Interview Questions

Sudoku solver is a staple of backtracking interviews at top technology companies. Interviewers use it to assess recursion, pruning, complexity analysis, and clean code. Below are common questions and how to approach them.

Q1: Write a function to solve a 9x9 Sudoku board in-place. How do you handle backtracking?

This is the core coding task. Start by explaining the algorithm in words: find empty cell, try 1-9, validate, recurse, backtrack. Then code the naive version first for clarity, mentioning that you would optimize with sets or MRV if time permits. Emphasize the undo step and base case (no empty cells). Complexity to mention: O(9^m) time worst-case, O(m) space for recursion depth where m is number of empties. Be prepared to walk through a small example and to discuss why you chose recursion over an explicit stack.

Q2: How would you check if a Sudoku board is valid (not necessarily solvable) before solving it?

This tests constraint checking in isolation. The answer is to verify that no row, column, or 3x3 box contains duplicate digits 1-9, ignoring empty cells. The optimal solution uses three arrays of sets and a single pass over the board: for each filled cell, check if its value is already in the corresponding row/col/box set; if so, invalid, otherwise add it. This is O(N²) time and O(N) space. Mention that this validation should be the first step of any solver to fail fast on invalid input.

Q3: How can you optimize the solver to handle the hardest puzzles faster?

Interviewers look for knowledge of heuristics and propagation. Discuss MRV (choose cell with fewest candidates), forward checking (maintain candidate sets and prune peers), and bitmasking for fast operations. Explain that MRV reduces branching factor and forward checking detects dead ends earlier. You can also mention constraint propagation like naked singles and hidden singles, and that DLX is the ultimate optimization but more complex to implement under interview time constraints. Provide a brief sketch of how you would implement MRV with candidate sets.

Q4: How would you generate a Sudoku puzzle with a unique solution?

This flips the problem from solving to generation. The standard approach is: start with a complete valid board (generate by solving an empty board with randomized digit order), then repeatedly remove a random clue and use the solver's counting variant to check if the puzzle still has exactly one solution. If it becomes multiple solutions, revert the removal. Continue until you reach desired difficulty (number of clues). This demonstrates understanding of both solving and solution counting, and the importance of uniqueness checking via backtracking that explores the full search tree up to two solutions.

Q5: What is the time and space complexity for a generalized NxN Sudoku solver? Can it be solved in polynomial time?

This tests theoretical depth. Answer: Generalized NxN Sudoku (where N = n²) is NP-complete, so no known polynomial-time algorithm exists, and it is believed none exists (P != NP). Backtracking takes O(N^(N²)) worst-case time and O(N²) space. For 9x9, this is exponential in empty cells O(9^m). Space is linear in board size plus recursion depth. Mention that while 9x9 is trivial for computers due to small constant size, the asymptotic hardness matters for large N, and practical solvers rely on pruning and heuristics to be fast on typical instances despite worst-case exponential behavior.