Day 50: Sudoku Solver #

Welcome to Day 50 of our 60 Days of Coding Algorithm Challenge! Today, we’ll tackle the Sudoku Solver problem, another classic application of backtracking algorithms.

What is Sudoku? #

Sudoku is a logic-based number-placement puzzle. The objective is to fill a 9×9 grid with digits so that each column, row, and 3×3 sub-grid contains all digits from 1 to 9 without repetition.

Understanding the Problem #

We have a 9×9 grid, partially filled with digits from 1 to 9.
Empty cells are represented by 0 or ‘.’.
We need to fill all empty cells following Sudoku rules.
A valid Sudoku solution must satisfy:
1. Each row contains digits 1-9 without repetition.
2. Each column contains digits 1-9 without repetition.
3. Each of the nine 3×3 sub-grids contains digits 1-9 without repetition.

Backtracking Approach #

We’ll use a backtracking approach to solve this problem:

Find an empty cell.
Try placing digits 1-9 in this cell.
Check if the digit is valid in the current cell.
If valid, recursively try to fill the rest of the grid.
If the recursive call is successful, return true.
If not successful, backtrack and try the next number.
If all numbers (1-9) have been tried and nothing worked, return false to trigger backtracking.

Implementation #

Here’s a Python implementation of the Sudoku Solver:

def solve_sudoku(board):
    def is_valid(num, pos):
        # Check row
        for i in range(9):
            if board[pos[0]][i] == num and pos[1] != i:
                return False

        # Check column
        for i in range(9):
            if board[i][pos[1]] == num and pos[0] != i:
                return False

        # Check 3x3 box
        box_x = pos[1] // 3
        box_y = pos[0] // 3

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

        return True

    def find_empty():
        for i in range(9):
            for j in range(9):
                if board[i][j] == 0:
                    return (i, j)
        return None

    def solve():
        find = find_empty()
        if not find:
            return True
        else:
            row, col = find

        for i in range(1, 10):
            if is_valid(i, (row, col)):
                board[row][col] = i

                if solve():
                    return True

                board[row][col] = 0

        return False

    solve()
    return board

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

solved_board = solve_sudoku(board)
for row in solved_board:
    print(row)

Time Complexity #

The time complexity of the Sudoku solver is O(9^(nn)), where n is the size of the board (9 in standard Sudoku). This is because for each empty cell, we try up to 9 numbers, and there are nn cells.

Space Complexity #

The space complexity is O(nn) to store the board, plus the space used by the recursion stack, which can go up to O(nn) in the worst case.

Optimizations #

Constraint Propagation: Reduce the number of possibilities for each cell based on the current state of the board.
Minimum Remaining Values (MRV): Choose the cell with the fewest possible values to fill next.
Bitmasking: Use bitwise operations to efficiently check and update valid numbers for each cell.

Variations of the Problem #

Solve different Sudoku variants: Like 16×16 Sudoku, Killer Sudoku, or Jigsaw Sudoku.
Sudoku Generator: Create a program that generates valid Sudoku puzzles.
Optimize for Minimal Clues: Find the minimum number of filled cells needed to ensure a unique solution.

Real-world Applications #

While Sudoku solving itself is primarily a puzzle, the techniques used have applications in:

Constraint satisfaction problems
Timetable scheduling
Resource allocation problems
Configuration problems in artificial intelligence

Exercise #

Modify the solver to work with different sized Sudoku grids (e.g., 4x4, 16x16).
Implement a Sudoku generator that creates valid, solvable Sudoku puzzles.
Extend the solver to handle Killer Sudoku, where cells are grouped and must sum to a given value.

Summary #

Today, we explored the Sudoku Solver problem, another classic application of backtracking algorithms. We implemented a solution, discussed its time and space complexity, and looked at possible optimizations and variations of the problem.

The Sudoku Solver demonstrates the power of backtracking in solving complex constraint satisfaction problems. The techniques we’ve learned here can be applied to a wide range of problems in computer science and beyond.

Tomorrow, we’ll dive into dynamic programming with the “Longest Common Subsequence” problem. Stay tuned!