Solve Sudoku

Tags

Solve Sudoku

Category

Recursion / Backtracking

Difficulty

Hard

Problem Statement

Given a partially filled 9x9 Sudoku board, fill in the empty cells so that every row, every column, and every 3x3 sub-box contains the digits 1 through 9 exactly once. The input board uses 0 (or a special marker) to indicate empty cells. The solution must modify the board in place.

Intuition

Sudoku naturally lends itself to backtracking. We scan through cells and, for each empty cell, try placing digits 1-9. Before placing a digit, we validate that it does not violate the row, column, or sub-box constraint. If a valid placement is found, we recurse to the next empty cell. If we reach a dead end (no valid digit for a cell), we backtrack by resetting the cell and trying the next digit at the previous decision point. Since the board is fixed-size (9x9), the problem space, while large, is bounded.

Approach

  1. Iterate through the board to find the first empty cell.
  2. If no empty cell is found, the board is solved — return true.
  3. For the empty cell, try digits 1 through 9.
  4. For each digit, check if placing it is valid:
    • The digit does not already appear in the same row.
    • The digit does not already appear in the same column.
    • The digit does not already appear in the same 3x3 sub-box.
  5. If the digit is valid, place it and recursively attempt to solve the rest of the board.
  6. If the recursive call returns true, the board is solved — propagate true.
  7. If the recursive call returns false, remove the digit (backtrack) and try the next digit.
  8. If no digit works for this cell, return false to trigger backtracking at a higher level.

Pseudocode

function solveSudoku(board):
    solvePartialSudoku(0, 0, board)
    return board

function solvePartialSudoku(row, col, board):
    if row == 9:
        return true  // solved

    nextRow = row + (1 if col == 8 else 0)
    nextCol = (col + 1) % 9

    if board[row][col] != 0:
        return solvePartialSudoku(nextRow, nextCol, board)

    for digit from 1 to 9:
        if isValidPlacement(digit, row, col, board):
            board[row][col] = digit
            if solvePartialSudoku(nextRow, nextCol, board):
                return true

    board[row][col] = 0  // backtrack
    return false

function isValidPlacement(digit, row, col, board):
    // Check row
    if digit in board[row]:
        return false

    // Check column
    for r from 0 to 8:
        if board[r][col] == digit:
            return false

    // Check 3x3 sub-box
    boxRowStart = (row / 3) * 3
    boxColStart = (col / 3) * 3
    for r from boxRowStart to boxRowStart + 2:
        for c from boxColStart to boxColStart + 2:
            if board[r][c] == digit:
                return false

    return true

Time & Space Complexity

  • Time: O(9^(n)) in the worst case, where n is the number of empty cells. However, constraint checking aggressively prunes the search space, making real-world performance much better. For a standard Sudoku with a unique solution, the effective time is roughly O(9^(n)) with n typically being 40-60 empty cells, but pruning reduces this dramatically.
  • Space: O(n) for the recursion stack, where n is the number of empty cells (at most 81). The board itself is modified in place.

Key Insights

  • Backtracking is essentially a depth-first search through the space of possible digit assignments.
  • Constraint propagation (checking validity before placing) prunes the search tree significantly.
  • The 3x3 sub-box check requires computing the top-left corner of the box using integer division: (row / 3) * 3.
  • Processing cells in order (left to right, top to bottom) simplifies the recursion — no need to track which cells have been filled.
  • For optimization, one can precompute which digits are available for each row, column, and box using sets or bitmasks.

Edge Cases

  • The board is already complete — the algorithm confirms validity and returns immediately.
  • The board has no solution — the algorithm exhausts all possibilities and the board remains in its original state.
  • Multiple solutions exist — the algorithm finds and returns the first one encountered.
  • The board has very few clues (17 is the known minimum for a unique solution) — the search space is larger but backtracking still handles it.
  • Invalid initial board (duplicate digits in a row, column, or box) — should be validated before attempting to solve.

Linked mentions