Sudoku Solver Using Backtracking in DSA Typescript - 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 number, try next

↩Back to Try number 1 to 9

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

Execution Sample

DSA Typescript

function solve(board: number[][]): boolean {
  for (let row = 0; row < 9; row++) {
    for (let col = 0; col < 9; col++) {
      if (board[row][col] === 0) {
        for (let num = 1; num <= 9; num++) {
          if (isValid(board, row, col, num)) {
            board[row][col] = num;
            if (solve(board)) return true;
            board[row][col] = 0;
          }
        }
        return false;
      }
    }
  }
  return true;
}

This code tries to fill empty cells with valid numbers using backtracking until the board is solved.

Execution Table

Step	Operation	Cell (row,col)	Number Tried	Is Valid?	Action	Board State (partial)
1	Find empty cell	(0,2)	-	-	Try numbers 1 to 9	[5 3 0 | ...]
2	Try number	(0,2)	1	No	Try next number	[5 3 0 | ...]
3	Try number	(0,2)	2	No	Try next number	[5 3 0 | ...]
4	Try number	(0,2)	4	Yes	Place 4	[5 3 4 | ...]
5	Move to next empty	(0,3)	-	-	Try numbers 1 to 9	[5 3 4 | 0 ...]
6	Try number	(0,3)	1	Yes	Place 1	[5 3 4 1 ...]
7	Move to next empty	(0,5)	-	-	Try numbers 1 to 9	[5 3 4 1 7 0 ...]
8	Try number	(0,5)	2	No	Try next number	[5 3 4 1 7 0 ...]
9	Try number	(0,5)	9	Yes	Place 9	[5 3 4 1 7 9 ...]
10	Move to next empty	(1,1)	-	-	Try numbers 1 to 9	[6 0 0 ...]
11	Try number	(1,1)	1	No	Try next number	[6 0 0 ...]
12	Try number	(1,1)	7	Yes	Place 7	[6 7 0 ...]
13	Backtrack	(1,2)	No valid number	-	Remove 0, backtrack	[6 7 0 ...]
14	Backtrack	(0,5)	No valid number after 9	-	Remove 9, try next	[5 3 4 1 7 0 ...]
15	Try number	(0,5)	3	Yes	Place 3	[5 3 4 1 7 3 ...]
...	...	...	...	...	...	...
N	Board complete	-	-	-	Return true	[Solved board]

💡 All cells filled with valid numbers, backtracking complete, board solved.

Variable Tracker

Variable	Start	After Step 4	After Step 9	After Step 12	After Step 15	Final
board[0][2]	0	4	4	4	4	4
board[0][5]	0	0	9	9	3	3
board[1][1]	0	0	0	7	7	7
current cell	(0,2)	(0,3)	(0,5)	(1,1)	(0,5)	board complete
number tried	-	4	9	7	3	-

Key Moments - 3 Insights

Why do we backtrack when no valid number fits in a cell?

Because the current path leads to no solution, so we remove the last placed number and try a different number (see steps 13 and 14 in execution_table).

How do we know a number is valid to place in a cell?

We check the row, column, and 3x3 box for duplicates before placing (referenced in 'Is Valid?' column in execution_table).

Why do we return true only after all cells are filled?

Because only a fully filled board with valid numbers means the puzzle is solved (see final step N in execution_table).

Visual Quiz - 3 Questions

Look at the execution_table, what number was placed in cell (0,5) after backtracking?

A 9

B 3

C 2

D 7

💡 Hint

Check steps 14 and 15 in execution_table where backtracking removes 9 and places 3.

At which step does the solver first place number 7 in cell (1,1)?

A Step 10

B Step 11

C Step 12

D Step 13

💡 Hint

Look at the 'Action' and 'Number Tried' columns for cell (1,1) in execution_table.

If the number 4 was invalid at cell (0,2), what would happen next?

A Try number 5 next

B Backtrack immediately

C Try number 1 next

D Try number 3 next

💡 Hint

Refer to the flow: after invalid number, try next number (see steps 2 and 3).

Concept Snapshot

Sudoku Solver Using Backtracking:
- Find empty cell
- Try numbers 1-9
- Check if number is valid (row, col, box)
- Place number if valid and move forward
- If stuck, backtrack by removing last number
- Repeat until board is complete

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 is valid by ensuring no duplicates in the row, column, or 3x3 box. 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 board is fully solved.