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.

Practice

1. What is the main idea behind using backtracking to solve a Sudoku puzzle?

easy

A. Use a sorting algorithm to arrange numbers in each row

B. Try placing numbers one by one and backtrack if a conflict occurs

C. Fill all empty cells randomly and check if the puzzle is solved

D. Replace all zeros with the number 9 directly

Solution

1. Step 1: Understand backtracking approach

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

2. Step 2: Handle conflicts by undoing choices

   If a number causes a conflict later, backtracking removes it and tries the next number.

3. Final Answer:

   Try placing numbers one by one and backtrack if a conflict occurs -> Option B

4. Quick Check:

   Backtracking = Try and undo choices [OK]

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

Common Mistakes:

• Thinking backtracking fills cells randomly
• Assuming sorting solves Sudoku
• Replacing zeros without checks

2. Which of the following TypeScript function signatures correctly represents a function to check if placing a number is valid in Sudoku?

easy

A. function isValid(board: number[][], row: number, col: number, num: number): boolean

B. function isValid(board: number[], row: number, col: number): number

C. function isValid(board: string[][], num: string): void

D. function isValid(board: number[][], num: number): string

Solution

1. Step 1: Analyze function parameters

   The function needs the board (2D array), row, column, and number to check validity.

2. Step 2: Check return type

   It should return a boolean indicating if placing the number is valid or not.

3. Final Answer:

   function isValid(board: number[][], row: number, col: number, num: number): boolean -> Option A

4. Quick Check:

   Correct parameters and boolean return [OK]

Hint: Check function inputs and boolean output for validity [OK]

Common Mistakes:

• Using wrong parameter types
• Missing row or column parameters
• Returning wrong data type

3. Given the following partial Sudoku board and the backtracking function call solveSudoku(board), what will be the value at board[0][2] after the first successful placement?

const 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]
];

medium

A. 4

B. 2

C. 1

D. 7

Solution

1. Step 1: Identify empty cell and possible numbers

   At position (0,2), possible numbers are those not in row 0, column 2, or 3x3 box. Candidates: 1, 2, 4.

2. Step 2: Check numbers 1 to 9 for validity

   1, 2, 4 are initially valid. Backtracking tries 1 first, recurses but backtracks due to later conflicts; tries 2, same; 4 succeeds and solves the puzzle.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   First successful number placed = 4 [OK]

Hint: Check row, column, box for smallest valid number [OK]

Common Mistakes:

• Choosing a number already in the same column
• Ignoring 3x3 box constraints
• Assuming first empty cell is filled with 1 always

4. Identify the bug in this TypeScript snippet for checking if a number can be placed in a Sudoku cell:

function isValid(board: number[][], row: number, col: number, num: number): boolean {
  for (let i = 0; i < 9; i++) {
    if (board[row][i] === num) return false;
    if (board[i][col] === num) return false;
  }
  const startRow = row - row % 3;
  const startCol = col - col % 3;
  for (let i = startRow; i < startRow + 3; i++) {
    for (let j = startCol; j < startCol + 3; j++) {
      if (board[i][j] === num) return false;
    }
  }
  return true;
}

medium

A. The function does not check the entire row correctly

B. The calculation of startRow and startCol is incorrect

C. The function checks the row and column twice causing errors

D. No bug; the function correctly checks validity

Solution

1. Step 1: Review row and column checks

   The loop checks all cells in the given row and column for the number.

2. Step 2: Review 3x3 box check

   startRow and startCol correctly find the top-left cell of the 3x3 box; nested loops check all 9 cells.

3. Final Answer:

   No bug; the function correctly checks validity -> Option D

4. Quick Check:

   All constraints checked properly [OK]

Hint: Check row, column, and box loops carefully [OK]

Common Mistakes:

• Miscomputing startRow or startCol
• Forgetting to check 3x3 box
• Returning false too early

5. You want to optimize the Sudoku solver by stopping early when the puzzle is solved. Which modification to the backtracking function is best to achieve this?

hard

A. Only check rows and columns, skip 3x3 box checks

B. Continue trying all numbers in all cells even after solution found

C. Return true immediately when a valid number is placed in the last empty cell

D. Remove the base case and let recursion run fully

Solution

1. Step 1: Understand base case in backtracking

   The base case returns true when all cells are filled correctly, stopping recursion.

2. Step 2: Modify to return true immediately on last cell

   Returning true immediately when the last empty cell is filled avoids unnecessary further checks.

3. Final Answer:

   Return true immediately when a valid number is placed in the last empty cell -> Option C

4. Quick Check:

   Stop recursion early by returning true [OK]

Hint: Return true at last cell to stop recursion early [OK]

Common Mistakes:

• Ignoring base case and continuing recursion
• Skipping box checks causing wrong solutions
• Trying all numbers even after solution