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.

Practice

1. What is the main purpose of backtracking in a Sudoku solver?

easy

A. To sort the Sudoku grid before solving

B. To try possible numbers and undo choices if they lead to conflicts

C. To fill all empty cells with zeros

D. To randomly assign numbers to cells

Solution

1. Step 1: Understand backtracking role

   Backtracking tries numbers in empty cells and removes them if they cause conflicts.

2. Step 2: Compare other options

   Sorting or random assignment does not solve Sudoku logically; filling zeros is incorrect.

3. Final Answer:

   To try possible numbers and undo choices if they lead to conflicts -> Option B

4. Quick Check:

   Backtracking = Try and undo choices [OK]

Hint: Backtracking means try and undo wrong moves [OK]

Common Mistakes:

• Thinking backtracking sorts the grid
• Assuming backtracking fills zeros
• Believing numbers are assigned randomly

2. Which of the following is the correct way to check if a number can be placed in a Sudoku cell in C?

easy

A. if (isSafe(row, col, num)) { place num; }

B. if isSafe(row, col, num) { place num; }

C. if isSafe(row, col, num); { place num; }

D. if (isSafe[row, col, num]) { place num; }

Solution

1. Step 1: Understand C syntax for if condition

   In C, conditions must be inside parentheses and followed by braces for blocks.

2. Step 2: Analyze options

   if (isSafe(row, col, num)) { place num; } uses correct syntax: if(condition) { ... }. Others miss parentheses or use wrong brackets.

3. Final Answer:

   if (isSafe(row, col, num)) { place num; } -> Option A

4. Quick Check:

   C if syntax = if(condition) { } [OK]

Hint: Use parentheses around conditions in C if statements [OK]

Common Mistakes:

• Omitting parentheses in if condition
• Using square brackets instead of parentheses
• Adding semicolon after if condition

3. What will be the output of the following code snippet that tries to solve a Sudoku puzzle using backtracking?

int board[9][9] = {
  {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");
}

medium

A. Infinite loop occurs

B. No solution exists

C. Compilation error due to missing function

D. The completed Sudoku board printed correctly

Solution

1. Step 1: Understand the given board and solveSudoku function

   The board is a valid Sudoku puzzle with empty cells as 0. solveSudoku uses backtracking to fill it.

2. Step 2: Predict output of solveSudoku

   Since the puzzle is solvable, solveSudoku returns true and printBoard prints the completed board.

3. Final Answer:

   The completed Sudoku board printed correctly -> Option D

4. Quick Check:

   Solvable board = completed print [OK]

Hint: Valid puzzles print solved board, else print no solution [OK]

Common Mistakes:

• Assuming no solution exists for valid puzzles
• Expecting compilation error without full code
• Thinking infinite loop happens without base case

4. Identify the bug in this backtracking Sudoku solver snippet:

bool solveSudoku(int board[9][9]) {
  int row, col;
  if (!findEmptyCell(board, &row, &col))
    return true;
  for (int num = 1; num <= 9; num++) {
    if (isSafe(board, row, col, num)) {
      board[row][col] = num;
      if (solveSudoku(board))
        return true;
      board[row][col] = 0;
    }
  }
  return false;
}

medium

A. Incorrect loop range for numbers (should be 0 to 9)

B. Not resetting cell to 0 after backtracking

C. No bug; code works correctly

D. Missing base case to stop recursion

Solution

1. Step 1: Check base case and recursion

   Base case returns true if no empty cell found, stopping recursion correctly.

2. Step 2: Verify backtracking steps

   After trying a number, if it fails, cell resets to 0, allowing other tries.

3. Step 3: Confirm loop range

   Loop runs from 1 to 9, which is correct for Sudoku numbers.

4. Final Answer:

   No bug; code works correctly -> Option C

5. Quick Check:

   Backtracking code correct = no bug [OK]

Hint: Check base case, reset cell, and loop range carefully [OK]

Common Mistakes:

• Forgetting to reset cell after failed attempt
• Wrong loop range including 0
• Missing base case causing infinite recursion

5. Given a partially filled Sudoku board, which strategy improves backtracking efficiency the most?

hard

A. Use constraint propagation to reduce possible numbers before backtracking

B. Always try numbers 1 to 9 in order for each empty cell

C. Fill empty cells randomly and backtrack if conflict occurs

D. Skip checking row and column constraints to save time

Solution

1. Step 1: Understand backtracking efficiency

   Trying all numbers blindly is slow; skipping checks causes wrong solutions.

2. Step 2: Analyze constraint propagation

   Constraint propagation narrows choices before backtracking, reducing search space and speeding solving.

3. Step 3: Evaluate other options

   Random filling is inefficient; skipping constraints breaks Sudoku rules.

4. Final Answer:

   Use constraint propagation to reduce possible numbers before backtracking -> Option A

5. Quick Check:

   Constraint propagation = faster solving [OK]

Hint: Reduce choices first, then backtrack for speed [OK]

Common Mistakes:

• Trying numbers in fixed order without pruning
• Random filling wastes time
• Ignoring constraints breaks puzzle rules