Sudoku Solver Using Backtracking in DSA Javascript - Execution Trace

Concept Flow - Sudoku Solver Using Backtracking

Start at first empty cell

↓

Try numbers 1 to 9

↓

Check if number is safe

↓

Place number

↓

Move to next empty cell

↓

Repeat until board full

↓

If stuck, backtrack

↓

Remove number, try next

Back to Try numbers 1 to 9↓

Done when all cells filled

↩Back to Try numbers 1 to 9

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

Execution Sample

DSA Javascript

function solve(board) {
  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 (isSafe(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 (0) with numbers 1-9 safely, recursively solving the Sudoku board using backtracking.

Execution Table

Step	Operation	Cell (row,col)	Number Tried	Is Safe?	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)	4	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)	3	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)	2	Yes	Place number 2	[5,3,4,1,7,6,8,2,0] ...
27	Move to next empty	(0,8)	-	-	Try numbers 1-9	[5,3,4,1,7,6,8,2,0] ...
28	Try number	(0,8)	1	Yes	Place number 1	[5,3,4,1,7,6,8,2,1] ...
29	Move to next empty	(1,0)	-	-	Continue solving	[5,3,4,1,7,6,8,2,1] ...
30	All cells filled	-	-	-	Solved	[5,3,4,1,7,6,8,2,1] ...

💡 All cells filled with safe numbers, Sudoku solved

Variable Tracker

Variable	Start	After Step 4	After Step 9	After Step 14	After Step 24	After Step 28	Final
row	0	0	0	0	0	0	1
col	0	2	5	7	8	8	0
num	-	4	6	9	-	1	-
board snapshot	Initial board	[5,3,4,...]	[5,3,4,1,7,6,...]	[5,3,4,1,7,6,8,9,...]	[5,3,4,1,7,6,8,0,...]	[5,3,4,1,7,6,8,2,1,...]	Solved board

Key Moments - 3 Insights

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

When no number 1-9 is safe in a cell (see step 24), we remove the last placed number and try the next possible number in the previous cell. This is backtracking to fix earlier choices.

How do we know if a number is safe to place?

A number is safe if it does not appear in the same row, column, or 3x3 box. This check happens before placing the number (see 'Is Safe?' column in execution table).

What happens when all cells are filled?

When no empty cells remain (step 30), the algorithm stops and returns true, meaning the Sudoku is solved.

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 9

💡 Hint

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

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

A Step 14

B Step 24

C Step 18

D Step 30

💡 Hint

Look for the first 'Backtrack' action in the 'Operation' column of the execution table.

According to the variable tracker, what is the value of 'col' after step 14?

A 8

B 5

C 7

D 2

💡 Hint

Check the 'col' row and the 'After Step 14' column in the variable tracker.

Concept Snapshot

Sudoku Solver Using Backtracking:
- Find first empty cell
- Try numbers 1-9
- Check if safe (row, col, box)
- Place number if safe
- Move to next empty cell
- If stuck, backtrack by removing last number
- Repeat until board is full and solved

Full Transcript

The Sudoku solver uses backtracking to fill empty cells. It starts at the first empty cell and tries numbers 1 through 9. For each number, it checks if placing it is safe by ensuring no conflicts in the row, column, or 3x3 box. If safe, 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 all cells are filled, solving the Sudoku puzzle.

Practice

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

easy

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

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

C. Use a sorting algorithm to arrange numbers in order

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 backtracking

   If a number causes a conflict, the algorithm removes it and tries the next number, going back if needed.

3. Final Answer:

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

4. Quick Check:

   Backtracking = Try and undo [OK]

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

Common Mistakes:

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

2. Which of the following is the correct way to check if a number can be placed in a Sudoku cell in JavaScript?

easy

A. if isSafe(board, row, col, num) { placeNumber(); }

B. if isSafe(board, row, col, num) then placeNumber();

C. if (isSafe board, row, col, num) { placeNumber(); }

D. if (isSafe(board, row, col, num)) { placeNumber(); }

Solution

1. Step 1: Understand JavaScript if syntax

   JavaScript requires parentheses around the condition in an if statement.

2. Step 2: Check function call syntax

   Function calls need parentheses with arguments inside, like isSafe(board, row, col, num).

3. Final Answer:

   if (isSafe(board, row, col, num)) { placeNumber(); } -> Option D

4. Quick Check:

   if(condition) with parentheses [OK]

Hint: Use parentheses around conditions in if statements [OK]

Common Mistakes:

• Missing parentheses in if condition
• Using 'then' keyword in JavaScript
• Incorrect function call syntax

3. What will be the output of the following code snippet when solving a Sudoku board?

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]
];
solveSudoku(board);
console.log(board);

medium

A. An error because solveSudoku is not defined

B. The original board unchanged with zeros intact

C. A fully solved Sudoku board with no zeros

D. A partially solved board with some zeros replaced

Solution

1. Step 1: Understand solveSudoku function purpose

   solveSudoku uses backtracking to fill all empty cells correctly, solving the puzzle.

2. Step 2: Check console.log output after solving

   After solveSudoku runs, the board is fully solved with no zeros remaining.

3. Final Answer:

   A fully solved Sudoku board with no zeros -> Option C

4. Quick Check:

   Backtracking solves all cells [OK]

Hint: Backtracking fills all empty cells correctly [OK]

Common Mistakes:

• Expecting original board unchanged
• Thinking partial fill is final
• Assuming function is undefined

4. Consider this buggy code snippet for checking if a number can be placed in a Sudoku cell:

function isSafe(board, row, col, num) {
  for (let x = 0; x < 9; x++) {
    if (board[row][x] === num || board[x][col] === num) {
      return false;
    }
  }
  // Missing 3x3 box check
  return true;
}

What is the main problem here?

medium

A. It returns false too early

B. It does not check the 3x3 subgrid for duplicates

C. It uses wrong loop variable x

D. It modifies the board inside the function

Solution

1. Step 1: Analyze row and column checks

   The code correctly checks if num exists in the same row or column.

2. Step 2: Identify missing 3x3 subgrid check

   Sudoku rules require checking the 3x3 box; this code does not do that, causing errors.

3. Final Answer:

   It does not check the 3x3 subgrid for duplicates -> Option B

4. Quick Check:

   3x3 box check missing = bug [OK]

Hint: Always check row, column, and 3x3 box [OK]

Common Mistakes:

• Ignoring 3x3 box validation
• Thinking loop variable causes error
• Assuming early return is wrong

5. You want to optimize the Sudoku solver by choosing the next empty cell with the fewest possible valid numbers to try. Which technique does this describe?

hard

A. Heuristic with Minimum Remaining Value (MRV) strategy

B. Random guessing of empty cells

C. Depth-first search without pruning

D. Sorting the board rows before solving

Solution

1. Step 1: Understand MRV heuristic

   MRV chooses the empty cell with the fewest valid options to reduce branching and speed up solving.

2. Step 2: Compare with other options

   Random guessing and depth-first search without pruning are less efficient; sorting rows does not help solving.

3. Final Answer:

   Heuristic with Minimum Remaining Value (MRV) strategy -> Option A

4. Quick Check:

   MRV = choose cell with fewest options [OK]

Hint: Pick cell with fewest choices first [OK]

Common Mistakes:

• Confusing random guessing with heuristics
• Ignoring pruning benefits
• Thinking sorting helps solving