Solving Sudoku Using Backtracking

Backtracking on a 9x9 Sudoku grid is a standard DSA interview question in placement drives at TCS, Infosys, and Cognizant. The recursive structure here is the same template used in N-Queens, Rat-in-a-Maze, and graph colouring.

How Backtracking Works on a Sudoku Grid

A Sudoku puzzle is a 9x9 grid where each cell must contain a digit from 1 to 9 such that every row, every column, and every 3x3 subgrid contains each digit exactly once. Cells already filled (the clues) are fixed. Empty cells, represented as 0 in code, are what the solver must determine.

Backtracking is a depth-first search with constraint-based pruning. The algorithm follows this sequence:

• Scan the grid to find the next cell where grid[row][col] equals 0.
• If no such cell exists, the puzzle is solved: return true.
• Try each digit from 1 to 9 for that cell.
• Call is_safe() to verify the digit does not conflict with existing placements.
• If safe, place the digit and recurse on the remaining grid.
• If the recursive call returns true, propagate success upward.
• If it returns false, restore grid[row][col] to 0 and try the next digit.
• If all 9 digits fail for this cell, return false to trigger a backtrack.

This guarantees that every valid combination is explored without ever accepting an invalid state.

The is_safe() Function

The is_safe() function is where the three Sudoku constraints are enforced. Per the rules documented in Sudoku solving algorithms, each digit must be unique across three scopes for any given cell placement.

Row check

Scan all 9 positions in row. If the candidate digit already appears, return false immediately.

Column check

Scan all 9 positions in col. If the candidate digit already appears, return false.

3x3 box check

Compute the top-left corner of the enclosing 3x3 subgrid:

• box_row = row - row % 3 maps any row to its box origin: rows 0, 1, 2 map to 0; rows 3, 4, 5 map to 3; rows 6, 7, 8 map to 6.
• box_col = col - col % 3 applies the same mapping to columns.

Scan all 9 cells in that 3x3 block. If the candidate digit appears, return false.

Only when all three checks pass does is_safe() return true and allow the placement. Placement interviewers frequently ask candidates to trace this function for a specific cell and explain why each of the three checks is independently necessary.

Sudoku Solver in C++

#include <iostream>
using namespace std;

const int N = 9;

bool is_safe(int grid[N][N], int row, int col, int num) {
    // Row check
    for (int j = 0; j < N; j++)
        if (grid[row][j] == num) return false;

    // Column check
    for (int i = 0; i < N; i++)
        if (grid[i][col] == num) return false;

    // 3x3 box check
    int box_row = row - row % 3;
    int box_col = col - col % 3;
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            if (grid[box_row + i][box_col + j] == num) return false;

    return true;
}

bool solve_sudoku(int grid[N][N]) {
    for (int row = 0; row < N; row++) {
        for (int col = 0; col < N; col++) {
            if (grid[row][col] == 0) {
                for (int num = 1; num <= 9; num++) {
                    if (is_safe(grid, row, col, num)) {
                        grid[row][col] = num;
                        if (solve_sudoku(grid)) return true;
                        grid[row][col] = 0;  // backtrack
                    }
                }
                return false;  // no valid digit for this cell
            }
        }
    }
    return true;  // no empty cell found: puzzle solved
}

void print_grid(int grid[N][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            cout << grid[i][j] << " ";
        cout << "\n";
    }
}

int main() {
    int grid[N][N] = {
        {5, 3, 0, 0, 7, 0, 0, 0, 0},
        {6, 0, 0, 1, 9, 5, 0, 0, 0},
        {0, 9, 8, 0, 0, 0, 0, 6, 0},
        {8, 0, 0, 0, 6, 0, 0, 0, 3},
        {4, 0, 0, 8, 0, 3, 0, 0, 1},
        {7, 0, 0, 0, 2, 0, 0, 0, 6},
        {0, 6, 0, 0, 0, 0, 2, 8, 0},
        {0, 0, 0, 4, 1, 9, 0, 0, 5},
        {0, 0, 0, 0, 8, 0, 0, 7, 9}
    };

    if (solve_sudoku(grid))
        print_grid(grid);
    else
        cout << "No solution\n";

    return 0;
}

Key observations in the C++ version:

• The outer for loops find the first cell where grid[row][col] == 0.
• After placing num, the recursive solve_sudoku() call attempts to fill the remaining cells.
• If that call returns false, grid[row][col] = 0 restores the cell before the next digit is tried.
• When the outer loops complete without finding a 0, all cells are filled and the function returns true.

Sudoku Solver in Python

def is_safe(grid, row, col, num):
    # Row check
    if num in grid[row]:
        return False
    # Column check
    if num in [grid[i][col] for i in range(9)]:
        return False
    # 3x3 box check
    box_row, box_col = 3 * (row // 3), 3 * (col // 3)
    for i in range(3):
        for j in range(3):
            if grid[box_row + i][box_col + j] == num:
                return False
    return True


def solve_sudoku(grid):
    for row in range(9):
        for col in range(9):
            if grid[row][col] == 0:
                for num in range(1, 10):
                    if is_safe(grid, row, col, num):
                        grid[row][col] = num
                        if solve_sudoku(grid):
                            return True
                        grid[row][col] = 0  # backtrack
                return False
    return True


def print_grid(grid):
    for row in grid:
        print(" ".join(str(x) for x in row))


grid = [
    [5, 3, 0, 0, 7, 0, 0, 0, 0],
    [6, 0, 0, 1, 9, 5, 0, 0, 0],
    [0, 9, 8, 0, 0, 0, 0, 6, 0],
    [8, 0, 0, 0, 6, 0, 0, 0, 3],
    [4, 0, 0, 8, 0, 3, 0, 0, 1],
    [7, 0, 0, 0, 2, 0, 0, 0, 6],
    [0, 6, 0, 0, 0, 0, 2, 8, 0],
    [0, 0, 0, 4, 1, 9, 0, 0, 5],
    [0, 0, 0, 0, 8, 0, 0, 7, 9]
]

if solve_sudoku(grid):
    print_grid(grid)
else:
    print("No solution")

The Python version is functionally identical to the C++ version. The row check uses Python’s in operator on grid[row], which is more concise than an explicit loop. The box anchor uses integer division (//) which maps identically to row - row % 3 in C++: 3 * (row // 3) gives 0 for rows 0, 1, 2; gives 3 for rows 3, 4, 5; gives 6 for rows 6, 7, 8.

Time Complexity and Optimisations

Metric	Value
Worst-case time	O(9^m) where m = empty cell count
Average case	Much better due to is_safe() pruning
Space (stack)	O(m) recursion depth
Space (grid)	O(1) additional (modified in place)

The O(9^m) bound treats every empty cell as having 9 independent choices. In practice, the is_safe() constraint check eliminates most branches early: a typical 30-clue puzzle is solved in milliseconds. For a thorough breakdown of how recursion depth and in-place modification affect algorithm space usage, see the space complexity of algorithms guide.

MRV Optimisation

The standard solver picks the next empty cell by scanning left-to-right and top-to-bottom. A faster strategy is MRV (Minimum Remaining Values): scan all empty cells, count how many digits pass is_safe() for each, and pick the cell with the smallest count.

Why this helps: a cell with only one valid digit gets filled immediately, eliminating a branch point without any recursion. A cell with zero valid digits triggers an immediate return-false before the recursion goes deeper. Most production Sudoku solvers combine MRV with a naked-singles pass, filling any cell that has exactly one candidate digit without recursing at all.

The pattern of scanning all candidates to select the most constrained position first appears in many DSA problems beyond Sudoku. The same left-to-right scanning logic with running constraint tracking shows up in problems like the equilibrium index problem.

Constraint Propagation

Constraint propagation goes one step further: after placing a digit, it immediately updates the set of remaining valid digits for every cell in the same row, column, and box. The most common form is AC-3 (arc consistency algorithm). Combined with MRV, a propagation-based solver handles even the hardest published Sudoku puzzles in under a millisecond.

The recursive backtracking solver above is the version that appears in placement coding rounds. MRV and AC-3 are the follow-up discussion points interviewers use to assess depth of understanding.

The recursive backtracking solver built here is also close in structure to how AI planning agents approach constrained search. Engineers at Tier-2 and Tier-3 colleges who want to extend this DSA foundation toward deployed AI applications can start at TinkerLLM for ₹299, where constrained problem-solving logic connects directly to LLM-powered projects.