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

↓

All cells filled?

Yes→Solved

No↓

Backtrack if stuck

↓

Remove number and try next

The solver tries numbers 1-9 in empty cells, checks validity, places valid numbers, moves forward, and backtracks if stuck until the puzzle is solved.

Execution Sample

DSA C++

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

This code tries to fill empty cells (0) with numbers 1 to 9 checking if placement is valid.

Execution Table

Step	Operation	Cell (row,col)	Number Tried	Is Valid?	Action	Board State Snapshot
1	Find empty cell	(0,2)	-	-	Try numbers 1-9	[5 3 0 | 0 7 0 | 0 0 0] ...
2	Try number	(0,2)	1	No	Try next number	[5 3 0 | 0 7 0 | 0 0 0] ...
3	Try number	(0,2)	2	No	Try next number	[5 3 0 | 0 7 0 | 0 0 0] ...
4	Try number	(0,2)	4	Yes	Place number 4	[5 3 4 | 0 7 0 | 0 0 0] ...
5	Move to next empty	(0,3)	-	-	Try numbers 1-9	[5 3 4 | 0 7 0 | 0 0 0] ...
6	Try number	(0,3)	1	Yes	Place number 1	[5 3 4 | 1 7 0 | 0 0 0] ...
7	Move to next empty	(0,5)	-	-	Try numbers 1-9	[5 3 4 | 1 7 0 | 0 0 0] ...
8	Try number	(0,5)	2	No	Try next number	[5 3 4 | 1 7 0 | 0 0 0] ...
9	Try number	(0,5)	6	Yes	Place number 6	[5 3 4 | 1 7 6 | 0 0 0] ...
10	Move to next empty	(0,6)	-	-	Try numbers 1-9	[5 3 4 | 1 7 6 | 0 0 0] ...
11	Try number	(0,6)	7	No	Try next number	[5 3 4 | 1 7 6 | 0 0 0] ...
12	Try number	(0,6)	8	Yes	Place number 8	[5 3 4 | 1 7 6 | 8 0 0] ...
13	Move to next empty	(0,7)	-	-	Try numbers 1-9	[5 3 4 | 1 7 6 | 8 0 0] ...
14	Try number	(0,7)	9	Yes	Place number 9	[5 3 4 | 1 7 6 | 8 9 0] ...
15	Move to next empty	(0,8)	-	-	Try numbers 1-9	[5 3 4 | 1 7 6 | 8 9 0] ...
16	Try number	(0,8)	2	No	Try next number	[5 3 4 | 1 7 6 | 8 9 0] ...
17	Try number	(0,8)	3	No	Try next number	[5 3 4 | 1 7 6 | 8 9 0] ...
18	Try number	(0,8)	5	No	Try next number	[5 3 4 | 1 7 6 | 8 9 0] ...
19	Try number	(0,8)	7	No	Try next number	[5 3 4 | 1 7 6 | 8 9 0] ...
20	Try number	(0,8)	1	No	Try next number	[5 3 4 | 1 7 6 | 8 9 0] ...
21	Try number	(0,8)	4	No	Try next number	[5 3 4 | 1 7 6 | 8 9 0] ...
22	Try number	(0,8)	6	No	Try next number	[5 3 4 | 1 7 6 | 8 9 0] ...
23	Try number	(0,8)	8	No	Try next number	[5 3 4 | 1 7 6 | 8 9 0] ...
24	Try number	(0,8)	9	No	Backtrack	[5 3 4 | 1 7 6 | 8 9 0] ...
25	Backtrack	(0,7)	Remove 9	N/A	Try next number	[5 3 4 | 1 7 6 | 8 0 0] ...
26	Try number	(0,7)	1	No	Try next number	[5 3 4 | 1 7 6 | 8 0 0] ...
27	Try number	(0,7)	2	Yes	Place number 2	[5 3 4 | 1 7 6 | 8 2 0] ...
28	Move to next empty	(0,8)	-	-	Try numbers 1-9	[5 3 4 | 1 7 6 | 8 2 0] ...
29	Try number	(0,8)	1	No	Try next number	[5 3 4 | 1 7 6 | 8 2 0] ...
30	Try number	(0,8)	3	No	Try next number	[5 3 4 | 1 7 6 | 8 2 0] ...
31	Try number	(0,8)	5	Yes	Place number 5	[5 3 4 | 1 7 6 | 8 2 5] ...
32	Move to next empty	(1,0)	-	-	Try numbers 1-9	[5 3 4 | 1 7 6 | 8 2 5] ...
...	...	...	...	...	...	...
N	All cells filled	-	-	-	Solved	[Complete solved board]

💡 All cells are filled with valid numbers, puzzle solved.

Variable Tracker

Variable	Start	After Step 4	After Step 9	After Step 14	After Step 27	Final
board[0][2]	0	4	4	4	4	4
board[0][5]	0	0	6	6	6	6
board[0][7]	0	0	0	9	2	2
board[0][8]	0	0	0	0	0	5
current cell	(0,2)	(0,5)	(0,7)	(0,8)	(0,8)	(final)
backtrack count	0	0	0	1	1	final count

Key Moments - 3 Insights

Why does the solver backtrack at step 24?

At step 24, all numbers 1-9 were tried for cell (0,8) but none were valid, so the solver removes the last placed number at (0,7) to try a different number, as shown in execution_table rows 24-25.

How does the solver know when the puzzle is solved?

When the solver reaches a point where no empty cells remain (all cells filled), it stops. This is shown in the last row of execution_table where 'All cells filled' leads to 'Solved'.

Why do we check if a number is valid before placing it?

Checking validity ensures the number does not violate Sudoku rules (row, column, box). This prevents wrong placements and reduces backtracking, as seen in multiple 'Is Valid?' checks in execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at step 4. What number was placed in cell (0,2)?

A 4

B 1

C 2

D 3

💡 Hint

Check the 'Number Tried' and 'Action' columns at step 4 in execution_table.

At which step does the solver backtrack for the first time?

A Step 14

B Step 24

C Step 9

D Step 27

💡 Hint

Look for the 'Backtrack' action in the execution_table.

If the number 9 was valid at cell (0,8) at step 16, what would happen?

A The solver would place 9 and move to next cell

B The solver would backtrack immediately

C The solver would skip cell (0,8)

D The solver would try number 1 next

💡 Hint

Refer to the flow in concept_flow and actions in execution_table for valid placements.

Concept Snapshot

Sudoku Solver Using Backtracking
- Find empty cell
- Try numbers 1-9
- Check if number is valid (row, column, box)
- Place valid number and move forward
- If stuck, backtrack and try next number
- Repeat until all cells filled

Full Transcript

The Sudoku solver uses backtracking to fill empty cells. It scans the board for empty cells, tries numbers 1 to 9, and checks if placing a number is valid according to Sudoku rules. If valid, it places the number 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. This process repeats until the entire board is filled correctly, solving the puzzle.

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