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.