Sudoku Solver — Backtracking

What does it solve?

Fills the empty cells of a 9×9 Sudoku grid so that every row, column, and 3×3 box contains the digits 1–9 exactly once, while respecting the given clues.

We scan for the next empty cell, try digits 1–9, check if each is safe (no conflicts), and recurse. If no digit works, we backtrack and undo the previous placement.

The core idea

// find next empty cell (r, c):
for digit 1..9:
  if isSafe(r, c, digit):
    place(r, c, digit)
    solve(next cell)
    unplace(r, c) // backtrack

Complexity

Time complexity

O(9^M)

Worst case is exponential in M, the number of empty cells — heavily pruned in practice by the row/column/box safety check.

Space complexity

O(M)

Recursion depth scales with the number of empty cells; the 9×9 board itself is O(1) extra space.

Examples & edge cases

Live animation

Given clue Trying this cell Conflict / rejected Just placed Solved

Step — of —

Cell

—

Action

—

Cells filled

—

of 81

Backtracks

—

so far

Select a puzzle and press Play to start.

✓ Solved ✗ No solution

Speed Fast

Step-by-step table (scrollable)

Step	Row	Col	Digit	Action	Note

C++ implementation

sudoku_solver.cpp

#include <bits/stdc++.h>
using namespace std;

bool isSafe(int grid[9][9], int row, int col, int num) {
    for (int x = 0; x < 9; x++)
        if (grid[row][x] == num || grid[x][col] == num)
            return false;                       // row / column conflict

    int br = row - row % 3, bc = col - col % 3;
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            if (grid[br+i][bc+j] == num)
                return false;                   // 3x3 box conflict

    return true;
}

bool solve(int grid[9][9]) {
    int row = -1, col = -1;
    bool empty = false;
    for (int r = 0; r < 9 && !empty; r++)
        for (int c = 0; c < 9 && !empty; c++)
            if (grid[r][c] == 0) { row=r; col=c; empty=true; }

    if (!empty) return true;             // no empty cells left -- solved

    for (int num = 1; num <= 9; num++) {
        if (isSafe(grid, row, col, num)) {
            grid[row][col] = num;            // place
            if (solve(grid)) return true;
            grid[row][col] = 0;            // backtrack
        }
    }
    return false;                       // trigger backtracking
}

int main() {
    int grid[9][9] = { /* ... puzzle, 0 = empty ... */ };
    if (solve(grid)) cout << "Solved!\n";
    else cout << "No solution exists.\n";
    return 0;
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars