Sudoku Solver Using Backtracking in DSA C++

Mental Model

Try placing numbers one by one in empty cells and backtrack if a number breaks Sudoku rules until the board is solved.

Analogy: Like solving a maze by trying paths and going back when hitting a dead end, we try numbers and undo if they don't fit.

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

_ means empty cell

Dry Run Walkthrough

Input: Partially filled 9x9 Sudoku board with some empty cells (represented by 0 or _).

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 1.

5 3 [1] | _ 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 smallest number to see if it fits in the empty cell.

Step 2: Check if 1 is valid in row 0, col 2; it is valid, so place it.

5 3 1 | _ 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 1 does not violate Sudoku rules here.

Step 3: Move to next empty cell at row 0, col 3; try number 1.

5 3 1 | [1] 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 placing 1 in next empty cell.

Step 4: Check if 1 is valid in row 0, col 3; it conflicts with 1 in row 1, col 3, so try next number 2.

5 3 1 | [2] 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 1 conflicts, so try next number.

Step 5: Check if 2 is valid in row 0, col 3; it is valid, so place it.

5 3 1 | 2 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 2 fits without breaking rules.

Step 6: Continue this process recursively for all empty cells, backtracking when no number fits.

Fully filled valid Sudoku board:
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: Backtracking ensures all possibilities are explored to find the solution.

Result:

Fully solved Sudoku board:
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

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

class SudokuSolver {
public:
    bool solveSudoku(vector<vector<int>>& board) {
        int row, col;
        if (!findEmptyCell(board, row, col))
            return true; // no empty cell means solved

        for (int num = 1; num <= 9; num++) {
            if (isValid(board, row, col, num)) {
                board[row][col] = num; // place num

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

                board[row][col] = 0; // backtrack
            }
        }
        return false; // trigger backtracking
    }

private:
    bool findEmptyCell(const vector<vector<int>>& board, int& row, int& col) {
        for (row = 0; row < 9; row++) {
            for (col = 0; col < 9; col++) {
                if (board[row][col] == 0)
                    return true; // found empty
            }
        }
        return false; // no empty cell
    }

    bool isValid(const vector<vector<int>>& board, int row, int col, int num) {
        // check row
        for (int x = 0; x < 9; x++) {
            if (board[row][x] == num)
                return false;
        }
        // check column
        for (int x = 0; x < 9; x++) {
            if (board[x][col] == num)
                return false;
        }
        // check 3x3 box
        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;
            }
        }
        return true;
    }
};

void printBoard(const vector<vector<int>>& board) {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cout << board[i][j] << " ";
            if ((j + 1) % 3 == 0 && j != 8) cout << "| ";
        }
        cout << endl;
        if ((i + 1) % 3 == 0 && i != 8) cout << "------+-------+------" << endl;
    }
}

int main() {
    vector<vector<int>> board = {
        {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}
    };

    SudokuSolver solver;
    if (solver.solveSudoku(board)) {
        printBoard(board);
    } else {
        cout << "No solution exists" << endl;
    }
    return 0;
}

if (!findEmptyCell(board, row, col)) return true;

Check if no empty cells remain, meaning puzzle solved

for (int num = 1; num <= 9; num++) {

Try numbers 1 through 9 in the empty cell

if (isValid(board, row, col, num)) { board[row][col] = num;

Place number if it does not break Sudoku rules

if (solveSudoku(board)) return true;

Recursively solve rest of board after placing number

board[row][col] = 0;

Backtrack by resetting cell if no number leads to solution

return false;

Trigger backtracking if no number fits current cell

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^(m)) where m is number of empty cells, because each empty cell tries up to 9 numbers recursively

Space: O(m) for recursion stack where m is number of empty cells

vs Alternative: Backtracking is more efficient than brute force checking all 9^81 boards; it prunes invalid paths early.

Edge Cases

Empty board (all zeros)

Solver tries many possibilities but eventually finds a valid solution or reports none

DSA C++

if (!findEmptyCell(board, row, col)) return true;

Already solved board

Solver immediately returns true without changes

DSA C++

if (!findEmptyCell(board, row, col)) return true;

Board with no valid solution

Solver backtracks fully and returns false, printing "No solution exists"

DSA C++

return false;

When to Use This Pattern

When you see a problem requiring filling a grid with constraints and trial/error, reach for backtracking because it tries options and undoes wrong choices systematically.

Common Mistakes

Mistake: Not resetting the cell to empty (0) when backtracking
Fix: Set board[row][col] = 0 before returning false to undo the choice

Mistake: Checking only row or column but forgetting 3x3 box validity
Fix: Add check for 3x3 box to ensure no duplicates in that subgrid

Summary

It fills empty Sudoku cells by trying numbers and backtracking on conflicts.

Use it when you need to solve puzzles with constraints and multiple choices.

The key insight is to try a choice, recurse, and undo if it leads to no solution.

Practice

1. What is the main idea behind the backtracking technique used in a Sudoku solver?

easy

A. Use a fixed pattern to fill the board

B. Fill the board randomly without checking rules

C. Try placing numbers and undo if they lead to conflicts

D. Only fill cells with a single possible number

Solution

1. Step 1: Understand backtracking in Sudoku

   Backtracking tries numbers in empty cells and checks if they fit the Sudoku rules.

2. Step 2: Undo if conflict arises

   If a number causes a conflict later, it is removed (backtracked) and another number is tried.

3. Final Answer:

   Try placing numbers and undo if they lead to conflicts -> Option C

4. Quick Check:

   Backtracking = Try and undo [OK]

Hint: Backtracking means try, check, and undo if needed [OK]

Common Mistakes:

• Thinking backtracking fills randomly
• Assuming backtracking fills only once without undo
• Believing backtracking uses fixed patterns

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(board, row, col, num)) { board[row][col] = num; }

B. if (board[row][col] == num) { placeNumber(); }

C. if (num > 9) { board[row][col] = num; }

D. if (board[row][col] != 0) { board[row][col] = num; }

Solution

1. Step 1: Understand the safety check function

   The function isSafe checks if placing num at board[row][col] follows Sudoku rules.

2. Step 2: Place number only if safe

   Only if isSafe returns true, the number is placed in the cell.

3. Final Answer:

   if (isSafe(board, row, col, num)) { board[row][col] = num; } -> Option A

4. Quick Check:

   Use isSafe before placing number [OK]

Hint: Always check safety before placing number [OK]

Common Mistakes:

• Placing number without checking rules
• Checking if cell already has the number incorrectly
• Using invalid conditions for placement

3. What will be the output of the following code snippet when solving a Sudoku board?

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}
};
solveSudoku(board);

Assuming solveSudoku correctly solves the puzzle, what will be the value at board[0][2] after solving?

medium

A. 9

B. 4

C. 7

D. 1

Solution

1. Step 1: Identify the empty cell at (0,2)

   The cell at row 0, column 2 is initially 0 (empty).

2. Step 2: Solve Sudoku and find correct number

   After solving, the number 4 fits at (0,2) without conflicts in row, column, or box.

3. Final Answer:

   4 -> Option B

4. Quick Check:

   board[0][2] = 4 after solve [OK]

Hint: Check solved board cell for correct number [OK]

Common Mistakes:

• Guessing without checking Sudoku rules
• Confusing row and column indices
• Assuming initial zeros remain zeros

4. Consider this buggy code snippet for checking if a number can be placed in a Sudoku cell:

bool isSafe(int board[9][9], int row, int col, int num) {
  for (int x = 0; x < 9; x++) {
    if (board[row][x] == num || board[x][col] == num)
      return false;
  }
  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[i][j] == num)
        return false;
    }
  }
  return true;
}

What is the bug in this code?

medium

A. The 3x3 box check uses wrong indices; should use startRow + i and startCol + j

B. The row and column checks are missing

C. The function does not return false when number is found

D. The modulo operation is incorrect

Solution

1. Step 1: Analyze 3x3 box checking loop

   The inner loop checks board[i][j] instead of board[startRow + i][startCol + j], so it checks wrong cells.

2. Step 2: Correct indices for box check

   To check the correct 3x3 box, add startRow and startCol offsets to i and j.

3. Final Answer:

   The 3x3 box check uses wrong indices; should use startRow + i and startCol + j -> Option A

4. Quick Check:

   Box check indices must include startRow/startCol [OK]

Hint: Add startRow/startCol offsets when checking 3x3 box [OK]

Common Mistakes:

• Checking wrong cells in 3x3 box
• Ignoring row or column checks
• Incorrect modulo usage

5. You want to optimize a Sudoku solver using backtracking by adding a heuristic. Which of the following strategies best reduces the search space?

hard

A. Fill cells row-wise ignoring constraints until stuck

B. Try numbers in random order for each empty cell

C. Always fill the first empty cell found without checking possibilities

D. Choose the empty cell with the fewest possible valid numbers first

Solution

1. Step 1: Understand heuristic to reduce search space

   Choosing the cell with the fewest valid options first reduces branching and speeds up solving.

2. Step 2: Compare other strategies

   Filling first empty cell or random tries increase backtracking steps; ignoring constraints causes errors.

3. Final Answer:

   Choose the empty cell with the fewest possible valid numbers first -> Option D

4. Quick Check:

   Minimum remaining values heuristic = choose cell with fewest options [OK]

Hint: Pick cell with least options first to speed solving [OK]

Common Mistakes:

• Filling cells without checking possibilities
• Trying numbers randomly wastes time
• Ignoring constraints leads to wrong solutions