Sudoku Solver Using Backtracking in DSA C

Mental Model

Try placing numbers one by one in empty cells and backtrack if a number leads to a conflict.

Analogy: Like trying keys on a locked door one by one; if a key doesn't fit, you go back and try another key until the door opens.

5 3 . | . 7 . | . . .
6 . . | 1 9 5 | . . .
. 9 8 | . . . | . 6 .
------+-------+------
8 . . | . 6 . | . . 3
4 . . | 8 . 3 | . . 1
7 . . | . 2 . | . . 6
------+-------+------
. 6 . | . . . | 2 8 .
. . . | 4 1 9 | . . 5
. . . | . 8 . | . 7 9

Dry Run Walkthrough

Input: Partially filled 9x9 Sudoku board with empty cells as 0

Goal: Fill all empty cells with digits 1-9 so that each row, column, and 3x3 box contains all digits without repetition

Step 1: Find first empty cell at row 0, col 2; try number 3

5 3 [3] | . 7 . | . . .
6 . . | 1 9 5 | . . .
. 9 8 | . . . | . 6 .
------+-------+------
8 . . | . 6 . | . . 3
4 . . | 8 . 3 | . . 1
7 . . | . 2 . | . . 6
------+-------+------
. 6 . | . . . | 2 8 .
. . . | 4 1 9 | . . 5
. . . | . 8 . | . 7 9

Why: Try number 3 to see if it fits in the empty cell

Step 2: Check if 3 is valid in row 0, col 2; conflict found in row, so try next number 4

5 3 [4] | . 7 . | . . .
6 . . | 1 9 5 | . . .
. 9 8 | . . . | . 6 .
------+-------+------
8 . . | . 6 . | . . 3
4 . . | 8 . 3 | . . 1
7 . . | . 2 . | . . 6
------+-------+------
. 6 . | . . . | 2 8 .
. . . | 4 1 9 | . . 5
. . . | . 8 . | . 7 9

Why: Number 3 conflicts, so try next number

Step 3: Number 4 is valid in row 0, col 2; place 4 and move to next empty cell

5 3 4 | . 7 . | . . .
6 . . | 1 9 5 | . . .
. 9 8 | . . . | . 6 .
------+-------+------
8 . . | . 6 . | . . 3
4 . . | 8 . 3 | . . 1
7 . . | . 2 . | . . 6
------+-------+------
. 6 . | . . . | 2 8 .
. . . | 4 1 9 | . . 5
. . . | . 8 . | . 7 9

Why: Valid placement allows moving forward

Step 4: Continue recursively trying numbers for next empty cells; if no valid number found, backtrack

Partial board with some cells filled, backtracking occurs when stuck

Why: Backtracking undoes wrong choices to try alternatives

Step 5: Eventually all cells filled with valid numbers satisfying Sudoku rules

5 3 4 | 6 7 8 | 9 1 2
6 7 2 | 1 9 5 | 3 4 8
1 9 8 | 3 4 2 | 5 6 7
------+-------+------
8 5 9 | 7 6 1 | 4 2 3
4 2 6 | 8 5 3 | 7 9 1
7 1 3 | 9 2 4 | 8 5 6
------+-------+------
9 6 1 | 5 3 7 | 2 8 4
2 8 7 | 4 1 9 | 6 3 5
3 4 5 | 2 8 6 | 1 7 9

Why: All constraints satisfied, puzzle solved

Result:

5 3 4 -> 6 7 8 -> 9 1 2 -> null
6 7 2 -> 1 9 5 -> 3 4 8 -> null
1 9 8 -> 3 4 2 -> 5 6 7 -> null
8 5 9 -> 7 6 1 -> 4 2 3 -> null
4 2 6 -> 8 5 3 -> 7 9 1 -> null
7 1 3 -> 9 2 4 -> 8 5 6 -> null
9 6 1 -> 5 3 7 -> 2 8 4 -> null
2 8 7 -> 4 1 9 -> 6 3 5 -> null
3 4 5 -> 2 8 6 -> 1 7 9 -> null

Annotated Code

DSA C

#include <stdio.h>
#include <stdbool.h>

#define N 9

// Check if num can be placed at board[row][col]
bool isSafe(int board[N][N], int row, int col, int num) {
    for (int x = 0; x < N; x++) {
        if (board[row][x] == num) return false; // check row
        if (board[x][col] == num) return false; // check column
    }
    int startRow = row - row % 3;
    int startCol = col - col % 3;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (board[startRow + i][startCol + j] == num) return false; // check box
        }
    }
    return true;
}

// Recursive function to solve Sudoku using backtracking
bool solveSudoku(int board[N][N]) {
    for (int row = 0; row < N; row++) {
        for (int col = 0; col < N; col++) {
            if (board[row][col] == 0) { // empty cell found
                for (int num = 1; num <= 9; num++) {
                    if (isSafe(board, row, col, num)) {
                        board[row][col] = num; // place num
                        if (solveSudoku(board)) return true; // recurse
                        board[row][col] = 0; // backtrack
                    }
                }
                return false; // no valid number found
            }
        }
    }
    return true; // solved
}

// Print the Sudoku board
void printBoard(int board[N][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            printf("%d ", board[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int board[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 (solveSudoku(board)) {
        printBoard(board);
    } else {
        printf("No solution exists\n");
    }
    return 0;
}

if (board[row][col] == 0) { // empty cell found

find next empty cell to fill

if (isSafe(board, row, col, num)) {

check if placing num is valid

board[row][col] = num; // place num

place number tentatively

if (solveSudoku(board)) return true; // recurse

recurse to solve rest of board

board[row][col] = 0; // backtrack

undo placement if dead end

return false; // no valid number found

trigger backtracking

Output

5 3 4 6 7 8 9 1 2 

6 7 2 1 9 5 3 4 8 

1 9 8 3 4 2 5 6 7 

8 5 9 7 6 1 4 2 3 

4 2 6 8 5 3 7 9 1 

7 1 3 9 2 4 8 5 6 

9 6 1 5 3 7 2 8 4 

2 8 7 4 1 9 6 3 5 

3 4 5 2 8 6 1 7 9 

Complexity Analysis

Time: O(9^(N*N)) because in worst case each cell tries 9 numbers recursively

Space: O(N*N) for recursion stack and board storage

vs Alternative: Backtracking is more efficient than brute force trying all combinations blindly because it prunes invalid paths early

Edge Cases

Empty board (all zeros)

Solver tries all possibilities; may take longer but still finds solution

DSA C

if (board[row][col] == 0) { // empty cell found

Already solved board

Solver quickly returns true without changes

DSA C

return true; // solved

No solution board

Solver backtracks fully and returns false

DSA C

return false; // no valid number found

When to Use This Pattern

When you need to fill a grid with constraints and try all options systematically, use backtracking to explore and undo choices efficiently.

Common Mistakes

Mistake: Not resetting the cell to zero when backtracking
Fix: Set board[row][col] = 0 after recursive call fails to undo the choice

Mistake: Checking only row or column but not 3x3 box for validity
Fix: Include 3x3 box check in isSafe function

Summary

Solves Sudoku by trying numbers in empty cells and backtracking on conflicts.

Use when you must fill a grid with constraints and no direct formula exists.

The key is to try a choice, move forward, and undo if it leads to a dead end.