Solving Valid Sudoku Puzzles in Python - Step-by-Step Coding Guide

Updated: at 04:34 AM

Sudoku is a popular number placement puzzle that rose to worldwide fame in the 2000s. The classic 9x9 grid consists of 9 subgrids called “regions” that each contain 9 cells. The puzzle begins with some cells prefilled with numbers between 1-9. To solve a Sudoku, you must fill the empty cells with numbers so that each row, column, and region contains the numbers 1-9 exactly once without repeating any numbers within those units.

In this comprehensive guide, we will walk through the steps to code a Python program that takes a valid, partially completed 9x9 Sudoku puzzle as input and outputs the solved puzzle by filling in the missing values. We will use techniques like recursion and backtracking to systematically place numbers while adhering to the Sudoku rules.

Table of Contents

Open Table of Contents

Prerequisites

To follow along with this Sudoku solver tutorial, you should have:

If you need to brush up on any Python basics, reviewing the Python documentation can help prepare you for this tutorial. Let’s get started building our Sudoku solver!

Validating the Sudoku Puzzle Input

The first step is to check that the initial puzzle we want to solve is a valid Sudoku board. This ensures we are not trying to solve an impossible or incorrectly formatted puzzle.

We will represent the 9x9 Sudoku grid as a 2D list of lists in Python. Empty cells will be filled with 0 while pre-filled cells will have numbers 1-9:

puzzle = [[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]]

We will write a validate_sudoku() function that returns True if the puzzle is valid and False otherwise. For a valid puzzle:

Here is the complete function to validate these rules:

def validate_sudoku(puzzle):

    # Create sets for rows, cols and regions
    rows = [set() for i in range(9)]
    cols = [set() for i in range(9)]
    regions = [[set() for _ in range(3)] for _ in range(3)]

    for r in range(9):
        for c in range(9):
            val = puzzle[r][c]

            # Check row
            if val in rows[r]:
                return False
            rows[r].add(val)

            # Check column
            if val in cols[c]:
                return False
            cols[c].add(val)

            # Check region
            region_index = (r // 3, c // 3)
            if val in regions[region_index[0]][region_index[1]]:
                return False
            regions[region_index[0]][region_index[1]].add(val)

    # Puzzle is valid
    return True

The validate_sudoku() function above returns True if the input puzzle passes all the validity checks. We create sets to track the row, column, and 3x3 region values and check for any duplicates which would make the puzzle invalid.

Let’s test it on a valid and invalid puzzle:

puzzle1 = [[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]]

print(validate_sudoku(puzzle1)) # True

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

print(validate_sudoku(puzzle2)) # False (Duplicate 2 in 8th row)

This validation will prevent us from wasting time trying to solve invalid puzzles. Next, let’s focus on the solver!

Solving the Sudoku Puzzle

Now we can start building the Sudoku solver using a recursive backtracking algorithm. The steps will be:

  1. Find an empty cell on the puzzle
  2. Try placing digits 1-9 in that cell
  3. Check if that digit is valid in the current spot based on Sudoku rules
  4. If valid, recursively call the solver on the updated puzzle to solve further
  5. If we find a conflict (digit not valid), backtrack and try a new number in the cell instead
  6. Repeat until the puzzle is solved!

Finding the Next Empty Cell

We will need a helper function find_next_empty() that scans the puzzle and returns the row and column index tuple (r, c) of the next cell that is empty (has a value 0). This will be used to determine where to fill a number next.

def find_next_empty(puzzle):
    # Get dimensions
    n = len(puzzle)

    # Scan row by row, col by col
    for r in range(n):
        for c in range(n):
            if puzzle[r][c] == 0:
                return r, c

    # No empty cells left
    return None, None

This scans the puzzle in order and returns the first empty cell found. If no empty cells remain, it returns None, None indicating the puzzle is completely filled.

Checking Validity of a Number in Cell

To check if a number is valid in a given cell, we can reuse parts of our validate_sudoku() function earlier. We will make a is_valid() helper that takes the puzzle, row, column, and value to check and returns True if placing that value in the cell is valid:

def is_valid(puzzle, r, c, val):

    # Check if value in row
    if val in puzzle[r]:
        return False

    # Check if value in column
    if val in [puzzle[i][c] for i in range(9)]:
        return False

    # Get region indexes
    r_start = (r // 3) * 3
    c_start = (c // 3) * 3

    # Check region
    for i in range(3):
        for j in range(3):
            if puzzle[r_start + i][c_start + j] == val:
                return False

    # If no conflicts, valid
    return True

This checks the row, column and 3x3 region to make sure val does not already exist in any of those locations.

Putting it Together in the Solver

Now we can use find_next_empty() and is_valid() in our recursive backtracking solver function:

def solve_sudoku(puzzle):

    # Find next empty cell
    r, c = find_next_empty(puzzle)

    # Base case: no more empty cells
    if r is None:
        return True

    # Try digits 1-9 in cell
    for digit in range(1, 10):

        # Check if valid
        if is_valid(puzzle, r, c, digit):

            # Set value and recursively solve rest of board
            puzzle[r][c] = digit
            if solve_sudoku(puzzle):
                return True

        # Undo and try again if failed
        puzzle[r][c] = 0

    # Could not solve with any number
    return False

The recursive logic:

  1. Find the next empty cell with find_next_empty()
  2. Try each digit 1-9 in that cell, using is_valid() to check
  3. If we can set a valid digit without causing any conflicts, recursively call solve_sudoku() on the updated puzzle to progress forward
  4. If the recursive call succeeds in fully solving the puzzle, return True for success!
  5. If conflict found, reset the cell and try next digit
  6. If no valid digits work in cell, reset it and return False backtracking

This recursive depth-first search with backtracking allows us to systematically try all combinations until we find a solution that works!

Testing the Solver

Let’s test the complete solver on some sample puzzles:

puzzle1 = [[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]]

print(solve_sudoku(puzzle1))
print(puzzle1)

# Prints:
# True
# [[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]]

Our Sudoku solver successfully solved the puzzle! The solve_sudoku() function can work on any valid 9x9 puzzle, making it a flexible and reusable component for Sudoku implementations.

Optimizing the Solver

There are further enhancements we can add to improve the efficiency and performance of the basic solver above:

Trying Most Constrained Cells First

Instead of scanning the puzzle sequentially, we can prioritize empty cells that have the fewest possible digit options. This helps prune the search tree earlier.

We can count the number of allowed digits in each cell upfront using a helper function:

def count_allowed_values(puzzle, r, c):

    # Initialize counter
    counter = 0

    # Check digits 1-9
    for val in range(1,10):
        if is_valid(puzzle, r, c, val):
            counter += 1

    return counter

Then find the cell with the minimum allowed values:

# Return cell (r, c) with fewest options
def find_most_constrained(puzzle):

    n = len(puzzle)
    min_options = 10

    for r in range(n):
        for c in range(n):
           if puzzle[r][c] == 0:
               num_options = count_allowed_values(puzzle, r, c)
               if num_options < min_options:
                   min_r, min_c = r, c
                   min_options = num_options

    return min_r, min_c

We replace our find_next_empty() call with find_most_constrained() to start with the most limited cell.

Adding heuristics

We can add other heuristics like:

This can significantly reduce the search tree and improve performance.

Conclusion

In this guide, we implemented a Sudoku solver in Python step-by-step using a backtracking algorithm. Key points included:

Sudoku puzzles have been mathematically proven to have only one valid solution. By using algorithms like this backtracking solver, we can systematically work towards the single solution without needing to guess. Mastering Sudoku solving is a great way to improve your logical thinking and programming abilities.