Sudoku Solver Using Backtracking in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the backtracking technique used in Sudoku solving?

Backtracking tries to fill the Sudoku grid by placing numbers one by one. If a number breaks the rules, it goes back (backtracks) and tries a different number until the puzzle is solved.

beginner

Which three conditions must be checked before placing a number in a Sudoku cell?

1. The number is not already in the same row.
2. The number is not already in the same column.
3. The number is not already in the 3x3 subgrid containing the cell.

beginner

What does it mean if the backtracking algorithm reaches a cell where no number can be placed?

It means the current path is wrong. The algorithm must go back to the previous cell and try a different number there.

intermediate

Why is backtracking a good fit for solving Sudoku puzzles?

Because Sudoku requires trying many possibilities and undoing wrong choices, backtracking naturally explores all options efficiently until it finds the correct solution.

advanced

What is the time complexity of the Sudoku solver using backtracking in the worst case?

The worst-case time complexity is very high, roughly O(9^(n*n)) where n is the size of the grid (usually 9). This is because each empty cell can try up to 9 numbers.

What is the first step in the backtracking Sudoku solver?

A Check if the puzzle is already solved

B Find an empty cell to fill

C Fill all cells with 1

D Fill the last cell first

The solver starts by finding an empty cell to try placing numbers.

Which of these is NOT a rule to check before placing a number in Sudoku?

A Number must not be in the same row

B Number must not be in the same column

C Number must be even

D Number must not be in the same 3x3 box

Sudoku numbers can be odd or even; being even is not a rule.

What happens if no number fits in the current empty cell during backtracking?

A The algorithm stops and returns failure

B The algorithm fills the cell with zero

C The algorithm skips the cell

D The algorithm backtracks to the previous cell

Backtracking means going back to try different numbers in previous cells.

How does the algorithm know when the Sudoku puzzle is solved?

A When all cells are filled without breaking rules

B When the first row is filled

C When the first column is filled

D When the middle cell is filled

The puzzle is solved when every cell is filled correctly.

Which data structure is commonly used to represent the Sudoku board in code?

A 2D array or list of lists

B Queue

C Stack

D Linked list

A 2D array or list of lists matches the grid layout of Sudoku.

Explain how backtracking helps solve a Sudoku puzzle step-by-step.

Think about trying and undoing choices.

List the three main checks needed before placing a number in a Sudoku cell.

Sudoku rules prevent duplicates in these areas.

Practice

1. What is the main purpose of backtracking in a Sudoku solver?

easy

A. To count how many empty cells are in the Sudoku grid

B. To randomly fill the Sudoku grid without checking rules

C. To sort the numbers in each row before solving

D. To try possible numbers and undo choices if they lead to conflicts

Solution

1. Step 1: Understand backtracking role

   Backtracking tries numbers in empty cells and removes them if they cause conflicts.

2. Step 2: Compare other options

   Other options do not describe backtracking's trial and error approach.

3. Final Answer:

   To try possible numbers and undo choices if they lead to conflicts -> Option D

4. Quick Check:

   Backtracking = Try and undo choices [OK]

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

Common Mistakes:

• Thinking backtracking fills randomly without checks
• Confusing backtracking with sorting or counting
• Ignoring the undo step in backtracking

2. Which of the following is the correct Python syntax to check if a number is safe to place in a Sudoku cell using backtracking?

easy

A. if is_safe(board, row, col, num):

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

C. if is_safe(board, row, col, num)

D. if is_safe board, row, col, num:

Solution

1. Step 1: Identify correct function call syntax

   Python requires parentheses and a colon after the if condition, so 'if is_safe(board, row, col, num):' is correct.

2. Step 2: Check other options for syntax errors

   if isSafe(board, row, col, num); uses semicolon instead of colon; C misses colon; D misses parentheses.

3. Final Answer:

   if is_safe(board, row, col, num): -> Option A

4. Quick Check:

   Python if syntax = condition + colon [OK]

Hint: Remember if statements end with a colon in Python [OK]

Common Mistakes:

• Forgetting the colon at the end of if statement
• Missing parentheses around function arguments
• Using semicolon instead of colon

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

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

solve_sudoku(board)
print(board)

medium

A. [[5,3,4,6,7,8,9,1,2],[6,7,2,1,9,5,3,4,8],[1,9,8,3,4,2,5,6,7],[8,5,9,7,6,1,4,2,3],[4,2,6,8,5,3,7,9,1],[7,1,3,9,2,4,8,5,6],[9,6,1,5,3,7,2,8,4],[2,8,7,4,1,9,6,3,5],[3,4,5,2,8,6,1,7,9]]

B. [[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]]

C. SyntaxError

D. RuntimeError

Solution

1. Step 1: Understand solve_sudoku function effect

   The solve_sudoku function fills empty cells (zeros) with correct numbers to complete the Sudoku board.

2. Step 2: Analyze output after solving

   After solving, the board will be fully filled with valid numbers, matching [[5,3,4,6,7,8,9,1,2],[6,7,2,1,9,5,3,4,8],[1,9,8,3,4,2,5,6,7],[8,5,9,7,6,1,4,2,3],[4,2,6,8,5,3,7,9,1],[7,1,3,9,2,4,8,5,6],[9,6,1,5,3,7,2,8,4],[2,8,7,4,1,9,6,3,5],[3,4,5,2,8,6,1,7,9]]'s completed grid.

3. Final Answer:

   Completed Sudoku board with all zeros replaced by correct numbers -> Option A

4. Quick Check:

   Backtracking fills zeros to complete board [OK]

Hint: Backtracking fills zeros to complete Sudoku [OK]

Common Mistakes:

• Expecting the board to remain unchanged after solve
• Confusing syntax or runtime errors with correct output
• Not recognizing that zeros are placeholders for empty cells

4. Identify the error in this backtracking Sudoku solver code snippet:

def solve(board):
    for row in range(9):
        for col in range(9):
            if board[row][col] == 0:
                for num in range(1, 10):
                    if is_safe(board, row, col, num):
                        board[row][col] = num
                        if solve(board):
                            return True
                        board[row][col] = 0
                return False
    return True

# Error: The function is_safe is not defined anywhere.

medium

A. The range for num should be range(0, 9)

B. The board size should be 8 instead of 9

C. The function is_safe is missing, causing NameError

D. The function solve should return False at the end

Solution

1. Step 1: Check for missing functions

   The code calls is_safe but does not define it, causing a NameError at runtime.

2. Step 2: Verify other options

   Board size 9 is correct for Sudoku; num range 1-9 is correct; solve returns True at end which is correct.

3. Final Answer:

   The function is_safe is missing, causing NameError -> Option C

4. Quick Check:

   Undefined function causes NameError [OK]

Hint: Always define helper functions before calling them [OK]

Common Mistakes:

• Assuming board size is 8 instead of 9
• Using wrong range for numbers (should be 1 to 9)
• Forgetting to return True when solved

5. Given a partially filled Sudoku board, which strategy best improves the efficiency of the backtracking solver?

hard

A. Fill cells randomly without checking constraints

B. Always pick the next empty cell with the fewest possible valid numbers

C. Try numbers in ascending order without checking row or column

D. Restart solving from the first cell after each failed attempt

Solution

1. Step 1: Understand backtracking optimization

   Choosing the empty cell with the fewest valid options reduces branching and speeds solving.

2. Step 2: Evaluate other options

   Random filling ignores constraints; trying numbers without checks wastes time; restarting after failure is inefficient.

3. Final Answer:

   Always pick the next empty cell with the fewest possible valid numbers -> Option B

4. Quick Check:

   Minimum options first = faster backtracking [OK]

Hint: Choose cell with fewest options to speed solving [OK]

Common Mistakes:

• Ignoring constraints when filling cells
• Trying numbers in fixed order without pruning
• Restarting solving unnecessarily wastes time