Sudoku Solver 🎯

Sudoku is a popular logic-based number placement puzzle. This lesson will guide you on how to create a Sudoku solver using Python, one of the most beginner-friendly programming languages. Let's dive in!

Understanding Sudoku 📝

Sudoku is a 9x9 grid filled with numbers from 1 to 9, with no repeating numbers in any row, column, or 3x3 sub-grid (also known as a box). The goal is to fill in the missing numbers following these simple rules.

Sudoku Grid Example

Data Structures for Sudoku Solver 💡

To create a Sudoku solver, we'll use two primary data structures: lists and dictionaries.

List: A collection of items in a specific order, which can be modified.
Dictionary: A collection of key-value pairs, similar to a map or an object in other programming languages.

Creating a Sudoku Board ✅

First, let's create a Sudoku board using a list of lists:

python

board = [
    [3, 0, 6, 5, 0, 8, 4, 0, 0],
    [5, 2, 0, 0, 0, 0, 0, 0, 0],
    [0, 8, 7, 0, 0, 0, 0, 3, 1],
    [0, 0, 3, 0, 6, 0, 2, 8, 0],
    [0, 5, 0, 9, 3, 0, 1, 0, 0],
    [8, 0, 0, 0, 0, 7, 0, 0, 0],
    [0, 0, 1, 0, 0, 5, 9, 6, 3],
    [0, 6, 0, 0, 0, 0, 0, 2, 8],
    [4, 0, 8, 0, 0, 9, 7, 5, 0]
]

Solving Sudoku - Brute Force Method 💡

The brute force method tries every possible combination for the empty cells to find a solution. While it works, it's not the most efficient approach for large Sudoku grids due to its high time complexity.

python

def solve_sudoku(board):
    find_empty = lambda board: [(i, j) for i, row in enumerate(board) for j, cell in enumerate(row) if cell == 0]

    if not find_empty(board):
        return True  # Board is already solved

    x, y = find_empty(board)[0]

    for num in range(1, 10):
        if is_safe(board, x, y, num):
            board[x][y] = num

            if solve_sudoku(board):
                return True

            board[x][y] = 0  # Backtracking

    return False

def is_safe(board, x, y, num):
    row_check = all(cell != num for cell in board[x])
    col_check = all(cell != num for cell in board[:, y])

    box_x = x - x % 3
    box_y = y - y % 3

    for i in range(box_x, box_x + 3):
        for j in range(box_y, box_y + 3):
            if board[i][j] == num:
                return False

    return True

Solving Sudoku - Backtracking with Constraints 💡

The backtracking with constraints method tries to place the next number in an empty cell, ensuring that it doesn't violate any Sudoku rules. This approach is more efficient than the brute force method for larger Sudoku grids.

python

def solve_sudoku(board):
    def find_next(board, values):
        for x, y in find_empty(board):
            if values[x][y] != 0:
                continue

            for num in range(1, 10):
                if is_safe(board, x, y, num):
                    board[x][y] = num

                    if solve_sudoku(board, values):
                        return True

                    board[x][y] = 0
                    values[x][y] = 0

            if not values[x][y]:
                return False

        return True

    values = [[0]*9 for _ in range(9)]
    for i, row in enumerate(board):
        for j, cell in enumerate(row):
            if cell != 0:
                values[i][j] = cell

    return find_next(board, values)

Quiz Time 🎯

By the end of this lesson, you should have a good understanding of how to create and solve Sudoku puzzles using Python. Happy coding! 🚀💻🎲