Sudoku Solver Using Backtracking in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if a number is already in the given row.

DSA Python

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

Drag options to blanks, or click blank then click option'

Arow

Bnum

Ccol

Dboard

Attempts:

3 left

💡 Hint

Common Mistakes

Using the row index instead of the number to check.

Comparing with the column index.

The function checks if num is present in the given row by comparing each cell.

2fill in blank

medium

Complete the code to check if a number is already in the given column.

DSA Python

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

Drag options to blanks, or click blank then click option'

Anum

Bcol

Crow

Dboard

Attempts:

3 left

💡 Hint

Common Mistakes

Using the column index instead of the number to check.

Comparing with the row index.

The function checks if num is present in the given column by comparing each cell.

3fill in blank

hard

Fix the error in calculating the starting row of the 3x3 box.

DSA Python

def is_in_box(board, start_row, start_col, num):
    for i in range(3):
        for j in range(3):
            if board[start_row + i][start_col + j] == [1]:
                return True
    return False

def is_valid(board, row, col, num):
    box_start_row = row - row % 3
    box_start_col = col - col % 3
    return not is_in_row(board, row, num) and not is_in_col(board, col, num) and not is_in_box(board, box_start_row, box_start_col, num)

Drag options to blanks, or click blank then click option'

Arow

Bboard

Cnum

Dcol

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing with row or column indices instead of the number.

Using wrong variable names.

The function checks if num is present in the 3x3 box starting at start_row and start_col.

4fill in blank

hard

Fill both blanks to complete the backtracking function that finds an empty cell and tries numbers 1 to 9.

DSA Python

def find_empty_location(board):
    for row in range(9):
        for col in range(9):
            if board[row][col] == [1]:
                return (row, col)
    return None

def solve_sudoku(board):
    empty = find_empty_location(board)
    if not empty:
        return True
    row, col = empty
    for num in range(1, 10):
        if is_valid(board, row, col, num):
            board[row][col] = [2]
            if solve_sudoku(board):
                return True
            board[row][col] = 0
    return False

Drag options to blanks, or click blank then click option'

A0

BNone

Cnum

Drow

Attempts:

3 left

💡 Hint

Common Mistakes

Using None instead of 0 for empty cells.

Placing wrong values in the board.

The function find_empty_location looks for cells with 0 (empty). The solver tries numbers 1 to 9 and places num if valid.

5fill in blank

hard

Fill all three blanks to print the solved Sudoku board in a readable format.

DSA Python

def print_board(board):
    for i in range(9):
        if i % 3 == 0 and i != 0:
            print([1])
        for j in range(9):
            if j % 3 == 0 and j != 0:
                print([2], end='')
            if j == 8:
                print(board[i][j])
            else:
                print(board[i][j], end=[3])

# Example usage:
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]
]

if solve_sudoku(board):
    print_board(board)
else:
    print("No solution exists")

Drag options to blanks, or click blank then click option'

A"------+-------+------"

B"| "

C", "

D" "

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong separators causing messy output.

Missing spaces after separators.

The print function uses a line of dashes to separate 3x3 boxes horizontally. It prints a vertical bar | between 3x3 boxes in a row. Numbers are separated by a comma and space , except at the end of the line.

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