Solving Sudoku with Dynamic Programming: A Step-by-Step Guide

· 8 min read

Hey everyone, it’s alanturrr1703 back again! 😄 Today, we’re diving into one of the most popular puzzle challenges—Sudoku—and how we can solve it using Dynamic Programming (DP). While the traditional way to solve Sudoku involves backtracking, we can optimize the process using DP principles.

In this blog, I’ll walk you through the problem, explain how DP can be applied to Sudoku, and provide a comprehensive pseudocode solution.

Let’s get started! 🚀

What is Sudoku?

Sudoku is a classic puzzle where you are given a 9x9 grid, partially filled with numbers. The objective is to fill the empty cells with digits (1 to 9) such that:

  1. Each row contains the numbers 1 to 9 without repetition.
  2. Each column contains the numbers 1 to 9 without repetition.
  3. Each 3x3 subgrid (also called a “box”) contains the numbers 1 to 9 without repetition.

A typical unsolved Sudoku puzzle looks like this:

5 3 _ | _ 7 _ | _ _ _
6 _ _ | 1 9 5 | _ _ _
_ 9 8 | _ _ _ | _ 6 _
------+------+------
8 _ _ | _ 6 _ | _ _ 3
4 _ _ | 8 _ 3 | _ _ 1
7 _ _ | _ 2 _ | _ _ 6
------+------+------
_ 6 _ | _ _ _ | 2 8 _
_ _ _ | 4 1 9 | _ _ 5
_ _ _ | _ 8 _ | _ 7 9

The goal is to fill all the blanks while respecting the constraints of the game.

Approach to Solving Sudoku with Backtracking and DP

Problem Breakdown:

The problem can be broken down into multiple decision-making steps:

  • At each step, we choose a number (1–9) for a specific empty cell.
  • After choosing a number, we move on to the next empty cell and make another decision.

Why Backtracking Works:

Backtracking involves placing a number in an empty cell and recursively trying to solve the rest of the puzzle. If at any point we hit a dead-end (i.e., no number can be placed in a cell without violating Sudoku rules), we backtrack and try a different number in the previous cell.

How DP Helps:

Dynamic Programming (DP) can optimize the backtracking solution by avoiding redundant computations. In Sudoku, this means storing the state of the puzzle (which numbers can be placed in certain cells) and reusing this information to minimize unnecessary checks.

Solving Sudoku Step-by-Step

Step 1: Identifying Possible Values for Each Cell

For each empty cell, we need to determine the possible numbers that can be placed in it without violating the Sudoku rules (rows, columns, and subgrids).

Step 2: Use Recursion with Backtracking

We start by placing a valid number in the first empty cell, then recursively solve the rest of the puzzle. If we encounter an invalid state, we backtrack and try a different number.

Step 3: Optimization with DP

We can optimize by storing which numbers are available for each row, column, and subgrid in a DP-like structure, reducing the need to recompute constraints repeatedly.

Comprehensive Pseudocode for Sudoku Solver

Function Definitions:

  1. isValid(num, row, col): Checks if placing num in the cell (row, col) is valid.
  2. findEmptyCell(grid): Finds the next empty cell in the grid.
  3. solveSudoku(grid): Main function to solve the Sudoku puzzle using recursion and backtracking.

Pseudocode:

# Check if placing 'num' in the (row, col) is valid according to Sudoku rules
Function isValid(grid, num, row, col):
    # Check the row
    For c = 0 to 8:
        If grid[row][c] == num:
            Return False

    # Check the column
    For r = 0 to 8:
        If grid[r][col] == num:
            Return False

    # Check the 3x3 subgrid
    startRow = row - (row % 3)
    startCol = col - (col % 3)
    For r = 0 to 2:
        For c = 0 to 2:
            If grid[startRow + r][startCol + c] == num:
                Return False

    Return True

# Find the next empty cell in the grid (returns None if no empty cells)
Function findEmptyCell(grid):
    For row = 0 to 8:
        For col = 0 to 8:
            If grid[row][col] == 0:  # 0 represents an empty cell
                Return (row, col)
    Return None

# The main function to solve the Sudoku puzzle using backtracking
Function solveSudoku(grid):
    emptyCell = findEmptyCell(grid)
    
    # If no empty cells are found, the puzzle is solved
    If emptyCell == None:
        Return True

    row, col = emptyCell

    # Try placing numbers 1 to 9 in the current empty cell
    For num = 1 to 9:
        If isValid(grid, num, row, col):
            # Place the number in the cell
            grid[row][col] = num

            # Recursively attempt to solve the rest of the grid
            If solveSudoku(grid):
                Return True

            # If the current placement doesn't lead to a solution, backtrack
            grid[row][col] = 0

    # If no number can be placed in the current cell, return False to backtrack
    Return False

Explanation of the Pseudocode:

  1. isValid(): This function checks whether placing a particular number in a specific row and column is valid. It verifies the current row, column, and 3x3 subgrid for any conflicts.
  2. findEmptyCell(): This function scans the grid for the first empty cell (represented by 0), indicating that a number needs to be placed there.
  3. solveSudoku(): This is the main backtracking function that uses recursion to solve the puzzle. It finds the next empty cell, tries placing numbers from 1 to 9, and recurses until the puzzle is solved. If a dead end is reached, it backtracks and tries a different number.

Example of Solving Sudoku

Let’s walk through solving a small part of a Sudoku puzzle to illustrate how the algorithm works.

Initial Sudoku Puzzle:

5 3 _ | _ 7 _ | _ _ _
6 _ _ | 1 9 5 | _ _ _
_ 9 8 | _ _ _ | _ 6 _
------+------+------
8 _ _ | _ 6 _ | _ _ 3
4 _ _ | 8 _ 3 | _ _ 1
7 _ _ | _ 2 _ | _ _ 6
------+------+------
_ 6 _ | _ _ _ | 2 8 _
_ _ _ | 4 1 9 | _ _ 5
_ _ _ | _ 8 _ | _ 7 9
  1. The algorithm starts by finding the first empty cell, which is (0, 2).
  2. It tries placing the number 1 in this cell and checks if it’s valid:
    • The number 1 is not in the row, column, or subgrid, so it’s valid.
  3. The algorithm places 1 in (0, 2) and recursively attempts to solve the rest of the puzzle.
  4. It continues this process, backtracking when necessary, until the entire grid is filled.

Solved Puzzle:

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

How DP Optimizes the Solution

Dynamic Programming principles come into play in the way we optimize constraints checking (which numbers are valid in each row, column, and subgrid).

Optimized Structure:

  • Row Constraints: Track which numbers are already used in each row.
  • Column Constraints: Track which numbers are used in each column.
  • Subgrid Constraints: Track which numbers are used in each 3x3 subgrid.

By maintaining these structures, we can quickly check whether placing a number is valid without having to scan the entire grid every time.

Optimization with Bitmasking:

We can further optimize using bitmasking. Instead of storing row

, column, and subgrid constraints in arrays, we can use bitmasks to represent which numbers are available or used. This reduces the overhead and speeds up the constraint checking process.

Time Complexity

The time complexity of the backtracking algorithm depends on the number of empty cells and how many options (numbers) need to be tried for each cell. In the worst case, the algorithm has to try 9 possibilities for each of the 81 cells:

  • Worst-case Time Complexity: O(9^81) (though this is rarely encountered in practice).
  • With constraints optimization using DP, this reduces the time spent on redundant checks.

Wrapping It Up

In this blog, we explored how to solve Sudoku using backtracking and how Dynamic Programming (DP) principles can be applied to optimize the solution by storing and reusing information about valid placements. We walked through a comprehensive pseudocode solution that shows how recursion and backtracking work together to fill the puzzle.

Understanding how to solve Sudoku with these techniques will help you tackle similar constraint-based problems and improve your algorithmic problem-solving skills.

That’s all for today! I hope this post helped you understand how to solve Sudoku efficiently. Until next time, happy coding! 🚀