Sudoku Solver (Backtracking) 🎯

Welcome to this comprehensive guide on solving Sudoku puzzles using the Backtracking algorithm! This lesson is designed for both beginners and intermediates, so let's get started.

What is Sudoku? 📝

Sudoku is a popular logic-based number puzzle. The goal is to fill a 9x9 grid with digits so that each row, column, and 3x3 box contains all of the digits from 1 to 9.

What is Backtracking? 💡

Backtracking is a depth-first search (DFS) algorithm used for solving problems that can be divided into smaller sub-problems. It's an efficient way to explore all possible solutions in a systematic manner.

Implementing Sudoku Solver with Backtracking

Step 1: Initialization ✅

First, let's create a 9x9 2D array (grid) to represent the Sudoku puzzle and a helper function (isValid()) to check if a number can be placed at a specific location.

python

def isValid(grid, row, col, num):
    # Check row, column, and box for duplicates
    for i in range(9):
        if grid[row][i] == num or grid[i][col] == num or grid[3*(row - row % 3) + i/3][3*(col - col % 3) + i%3] == num:
            return False
    return True

Step 2: Recursion 🎯

Now, let's implement the main function (solveSudoku()) that recursively solves the Sudoku puzzle using backtracking.

python

def solveSudoku(grid):
    def backtrack(row, col):
        if row == 9:
            return True

        if col == 9:
            return backtrack(row + 1, 0)

        if grid[row][col] != 0:
            return backtrack(row, col + 1)

        for num in range(1, 10):
            if isValid(grid, row, col, num):
                grid[row][col] = num

                if backtrack(row, col + 1):
                    return True

            grid[row][col] = 0

        return False

    if not grid:
        return False

    return backtrack(0, 0)

Step 3: Usage 💡

Now you can use the solveSudoku() function to solve a Sudoku puzzle. Here's an example:

python

grid = [
    [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, 1, 0, 0, 8, 0],
    [9, 0, 0, 8, 6, 3, 0, 0, 5],
    [0, 5, 0, 0, 9, 0, 7, 6, 0],
    [1, 3, 0, 0, 0, 0, 2, 5, 0],
    [0, 0, 0, 0, 0, 0, 0, 7, 4],
    [0, 0, 5, 2, 0, 6, 3, 0, 0]
]

solveSudoku(grid)
print(grid)

Quiz 💡

With this guide, you now have the knowledge to create a Sudoku solver using the Backtracking algorithm. Happy coding! 🎉