How to Implement a Sudoku Solver Using Backtracking in Python

etd_admin,

Sudoku is a popular puzzle game that challenges players to fill a 9×9 grid so that each row, column, and 3×3 sub-grid contains all digits from 1 to 9 without repetition. Writing a program to solve Sudoku using backtracking is an excellent way to understand recursive algorithms and constraint satisfaction.

This article will guide you through implementing a Sudoku solver using backtracking in Python, providing a clear explanation and sample code.

Backtracking is a recursive algorithm used to solve constraint satisfaction problems. It explores all possibilities for solving a problem by making one choice at a time and backtracking when a choice leads to a dead end. In Sudoku, backtracking systematically fills the grid by testing each possible number until it finds a valid solution.

Steps to Implement the Sudoku Solver

To implement a Sudoku solver using backtracking in Python, we follow these steps:

  1. Create a function to check validity: Verify if placing a number in a cell complies with Sudoku rules.
  2. Find an empty cell: Identify the next empty cell in the grid.
  3. Recursive backtracking: Attempt to fill the cell with a valid number. If it leads to a solution, continue; otherwise, backtrack.
  4. Print the solution: Display the solved grid.

Python Code Implementation

def is_valid(board, row, col, num):
    """Check if a number can be placed in the cell."""
    # Check the row
    if num in board[row]:
        return False

    # Check the column
    if num in [board[i][col] for i in range(9)]:
        return False

    # Check the 3x3 sub-grid
    start_row, start_col = 3 * (row // 3), 3 * (col // 3)
    for i in range(start_row, start_row + 3):
        for j in range(start_col, start_col + 3):
            if board[i][j] == num:
                return False

    return True


def find_empty_cell(board):
    """Find the next empty cell in the board."""
    for row in range(9):
        for col in range(9):
            if board[row][col] == 0:
                return row, col
    return None


def solve_sudoku(board):
    """Solve the Sudoku puzzle using backtracking."""
    empty_cell = find_empty_cell(board)
    if not empty_cell:
        return True  # No empty cells, puzzle solved!

    row, col = empty_cell

    for num in range(1, 10):  # Numbers 1 to 9
        if is_valid(board, row, col, num):
            board[row][col] = num

            if solve_sudoku(board):
                return True

            # Backtrack
            board[row][col] = 0

    return False


def print_board(board):
    """Print the Sudoku board."""
    for row in board:
        print(" ".join(str(num) if num != 0 else "." for num in row))


# Example Sudoku puzzle (0 represents empty cells)
sudoku_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(sudoku_board):
    print("Solved Sudoku:")
    print_board(sudoku_board)
else:
    print("No solution exists.")
  1. Validation Function
    • The is_valid function ensures that a number can be safely placed in a given cell, considering the row, column, and 3×3 sub-grid constraints.
  2. Finding Empty Cells
    • The find_empty_cell function scans the board for the next empty cell (represented as 0).
  3. Backtracking Algorithm
    • The solve_sudoku function applies backtracking by trying numbers 1 to 9 in each empty cell. If a number doesn’t fit, it resets the cell (backtracking) and tries the next number.
  4. Printing the Solution
    • The print_board function formats the grid for easy visualization.

Use the given code to effectively implement a Sudoku solver using backtracking in Python. This algorithm demonstrates the power of recursion and systematic problem-solving in programming.

Python