Sudoku Solver Using Backtracking in DSA C - Execution Trace

Concept Flow - Sudoku Solver Using Backtracking

Start with empty cell

↓

Try number 1 to 9

↓

Is number valid?

No→Try next number

Yes↓

Place number

↓

Move to next empty cell

↓

Repeat until board full

↓

If stuck, backtrack

↓

Remove last number

↩Back to Try number 1 to 9

The solver tries numbers 1-9 in empty cells, places valid ones, moves forward, and backtracks if stuck.

Execution Sample

DSA C

for (int num = 1; num <= 9; num++) {
  if (valid(board, row, col, num)) {
    board[row][col] = num;
    if (solve(board)) {
      return true;
    }
    board[row][col] = 0;
  }
}
return false;

This code tries numbers 1-9 in a cell, places a valid number, recurses, and backtracks if needed.

Execution Table

Step	Operation	Cell (row,col)	Number Tried	Valid?	Action	Board State Snapshot
1	Find empty cell	(0,0)	-	-	Empty cell found	[0,0,0,...] (rest of row 0)
2	Try number	(0,0)	1	Yes	Place 1	[1,0,0,...]
3	Find empty cell	(0,1)	-	-	Empty cell found	[1,0,0,...]
4	Try number	(0,1)	1	No	Try next number	[1,0,0,...]
5	Try number	(0,1)	2	Yes	Place 2	[1,2,0,...]
6	Find empty cell	(0,2)	-	-	Empty cell found	[1,2,0,...]
7	Try number	(0,2)	1	No	Try next number	[1,2,0,...]
8	Try number	(0,2)	3	Yes	Place 3	[1,2,3,...]
9	Find empty cell	(0,3)	-	-	Empty cell found	[1,2,3,0,...]
10	Try number	(0,3)	1	No	Try next number	[1,2,3,0,...]
11	Try number	(0,3)	4	Yes	Place 4	[1,2,3,4,...]
12	Find empty cell	(0,4)	-	-	Empty cell found	[1,2,3,4,0,...]
13	Try number	(0,4)	1	No	Try next number	[1,2,3,4,0,...]
14	Try number	(0,4)	5	Yes	Place 5	[1,2,3,4,5,...]
15	Find empty cell	(0,5)	-	-	Empty cell found	[1,2,3,4,5,0,...]
16	Try number	(0,5)	1	No	Try next number	[1,2,3,4,5,0,...]
17	Try number	(0,5)	6	Yes	Place 6	[1,2,3,4,5,6,...]
18	Find empty cell	(0,6)	-	-	Empty cell found	[1,2,3,4,5,6,0,...]
19	Try number	(0,6)	1	No	Try next number	[1,2,3,4,5,6,0,...]
20	Try number	(0,6)	7	Yes	Place 7	[1,2,3,4,5,6,7,...]
21	Find empty cell	(0,7)	-	-	Empty cell found	[1,2,3,4,5,6,7,0,...]
22	Try number	(0,7)	1	No	Try next number	[1,2,3,4,5,6,7,0,...]
23	Try number	(0,7)	8	Yes	Place 8	[1,2,3,4,5,6,7,8,...]
24	Find empty cell	(0,8)	-	-	Empty cell found	[1,2,3,4,5,6,7,8,0]
25	Try number	(0,8)	1	No	Try next number	[1,2,3,4,5,6,7,8,0]
26	Try number	(0,8)	9	Yes	Place 9	[1,2,3,4,5,6,7,8,9]
27	Find empty cell	None	-	-	No empty cells, puzzle solved	[1,2,3,4,5,6,7,8,9,...]

💡 No empty cells left, puzzle solved successfully

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 8	After Step 11	After Step 14	After Step 17	After Step 20	After Step 23	After Step 26	Final
board[0][0]	0	1	1	1	1	1	1	1	1	1	1
board[0][1]	0	0	2	2	2	2	2	2	2	2	2
board[0][2]	0	0	0	3	3	3	3	3	3	3	3
board[0][3]	0	0	0	0	4	4	4	4	4	4	4
board[0][4]	0	0	0	0	0	5	5	5	5	5	5
board[0][5]	0	0	0	0	0	0	6	6	6	6	6
board[0][6]	0	0	0	0	0	0	0	7	7	7	7
board[0][7]	0	0	0	0	0	0	0	0	8	8	8
board[0][8]	0	0	0	0	0	0	0	0	0	9	9

Key Moments - 3 Insights

Why do we try numbers 1 to 9 in each empty cell?

Because Sudoku rules allow numbers 1-9 only, and we must find a valid number that fits without conflicts, as shown in steps 2, 4, 5, etc.

What happens when no number is valid for a cell?

We backtrack by removing the last placed number and trying the next number, as implied in the concept flow and seen when 'Try number' results in 'No' and we try next numbers.

How do we know when the puzzle is solved?

When there are no empty cells left to fill, as in step 27 where 'Find empty cell' returns None and the puzzle is complete.

Visual Quiz - 3 Questions

Look at the execution table, what number is placed in cell (0,5) at step 17?

A 6

B 5

C 1

D 0

💡 Hint

Check the 'Number Tried' and 'Action' columns at step 17 in the execution table.

At which step does the solver find no empty cells and conclude the puzzle is solved?

A Step 26

B Step 27

C Step 25

D Step 24

💡 Hint

Look for the row where 'Find empty cell' operation returns 'None' in the execution table.

If the number 1 was invalid in cell (0,1), what does the solver do next according to the execution table?

A Places number 1 anyway

B Tries the next number

C Backtracks immediately

D Stops solving

💡 Hint

See steps 4 and 5 where number 1 is invalid and the solver tries number 2 next.

Concept Snapshot

Sudoku Solver Using Backtracking:
- Find an empty cell
- Try numbers 1 to 9
- Check if number is valid (no conflicts in row, column, box)
- Place number if valid and recurse
- If stuck, backtrack by removing number
- Repeat until board is full

Full Transcript

This visualization shows how a Sudoku solver uses backtracking to fill empty cells. It tries numbers 1 to 9 in each empty cell, checks if the number fits Sudoku rules, places it if valid, and moves to the next empty cell. If no number fits, it backtracks by removing the last placed number and tries the next possible number. The process repeats until the board is completely filled with valid numbers. The execution table tracks each step, the cell being filled, the number tried, whether it was valid, the action taken, and the board state snapshot. Variable tracking shows how the board cells change over time. Key moments clarify why numbers 1-9 are tried, what backtracking means, and how the solver knows when the puzzle is solved. The quiz tests understanding of specific steps and solver behavior.

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