Cracking Sudoku — How to Explore Backtracking Algorithms With Python

Understanding the power of backtracking algorithms through the lens of Sudoku

Patrick Kalkman

Jun 19, 2023 — 16 min read

Sudoku. Image generated by Midjourney, prompt by author.

This article is designed to guide you through the intricacies of the Sudoku puzzle, the concept of backtracking in algorithms, and how the two intersect.

Whether you’re an experienced Python programmer or a beginner eager to improve your problem-solving skills, this exploration is for you.

Sudoku, a logic-based number placement puzzle, has swept the globe with its elegant blend of simplicity and mental challenge. The puzzle consists of a 9x9 grid subdivided into nine 3x3 subgrids.

The objective is to fill each empty cell so that each digit from 1 to 9 appears once in every row, every column, and every 3x3 subgrid. The puzzle begins with some cells filled, providing a unique starting point for each game.

This seemingly simple game requires strategy and problem-solving skills — much like programming. As you delve into the depths of Sudoku, you’ll find that it mirrors many aspects of programming, from the need for logic and precise rules to the importance of breaking down larger problems into manageable parts.

Throughout this article, we’ll explore the world of Sudoku puzzles, delve into the realm of backtracking algorithms, and ultimately implement a Python program that can solve any given Sudoku puzzle.

We’ll examine why Sudoku is a fitting problem for backtracking and how the algorithm systematically navigates the potential solutions, moving forward and backtracking when necessary.

Whether you’re an avid Sudoku player hoping to understand the game better or a programmer seeking to understand backtracking, this article offers a unique perspective on problem-solving, programming, and the art of logical thinking.

All the coding examples this article covers are available for exploration and modification. You can find them in our dedicated GitHub repository.

· Understanding Sudoku as a problem-solving exercise
∘ Sudoku as a logic puzzle
∘ Importance of problem-solving skills in programming
· Introduction to Backtracking
∘ What is Backtracking?
∘ How Backtracking Works
· The Theory Behind Using Backtracking to Solve Sudoku
∘ Why Backtracking is Suitable for Sudoku
∘ Applying Backtracking to Sudoku
· Implementing a Sudoku Solver in Python
∘ Representing the Board
∘ Checking Validity
∘ Finding Empty Spaces
∘ Implementing Backtracking
· Optimizing the Sudoku Solver
∘ Intelligent Cell Selection: Heuristics
∘ Reducing the Search Space
· Generating Sudoku Boards
∘ The Algorithm
∘ Creating Puzzles
· Validating Our Code with Unit Tests
∘ Leveraging Test Cases
∘ Testing with External Sudoku Puzzles
· Conclusion
· References and Further Reading

Understanding Sudoku as a problem-solving exercise

Sudoku is a logic-based number placement puzzle that has gained worldwide popularity due to its simplicity and depth. The objective of Sudoku is to fill a 9×9 grid with digits so that each column, each row, and 3×3 sub-grids that compose the grid contain all of the numbers from 1 to 9.

A photo that shows a part of a filled Sudoku — Sudoko, photo by Bozhin Karaivanov on Unsplash

Sudoku as a logic puzzle

Unlike many puzzles that require guesswork, Sudoku puzzles are pure logic puzzles. They have definitive solutions that can be reached by applying deductive reasoning, with no need for trial-and-error approaches.

The initial partially completed grid provides a unique starting point for the deductive process. It’s akin to a detective starting an investigation with a few pieces of evidence, then following the clues to unravel the complete picture.

Each correctly placed number provides more evidence, making it easier to put other numbers. The core of Sudoku’s appeal lies in its cognitive load. It requires enough thinking to be engaging but isn’t so complex that it becomes overwhelming.

It’s a perfect test of logic and pattern recognition, with each completed puzzle providing a satisfying resolution.

Importance of problem-solving skills in programming

Drawing a parallel between Sudoku and programming involves using logic and problem-solving skills to find solutions. Programming, like Sudoku, is all about problem-solving.

The programmer is given a problem, often not fully specified, and needs to devise a solution within certain constraints, just like filling numbers in a Sudoku grid.

But unlike Sudoku, which has a well-defined 9x9 grid and rules, programming problems can be open-ended, and the constraints often need clarification. This requires a high level of creativity and an ability to deal with ambiguity.

One of the most valuable skills a programmer can develop is breaking down complex problems into smaller, more manageable subproblems.

This process, decomposition, is also crucial for solving Sudoku puzzles. Each 9x9 Sudoku grid can be broken down into 3x3 grids, rows, and columns, which can be solved independently.

Another important aspect is algorithmic thinking, the ability to devise a step-by-step procedure or a sequence of instructions to solve a problem.

Algorithms are at the heart of programming, and they’re also key to solving Sudoku puzzles, where a systematic approach can help fill in the grid more efficiently.

Lastly, both Sudoku and programming require resilience. They’re about facing challenges head-on, finding and fixing errors, and being persistent until you find a solution.

In Sudoku, as in programming, every mistake is a learning opportunity, and every problem is a new puzzle to solve.

In the next section, we’ll start looking at how to solve Sudoku using a backtracking algorithm, a powerful method for solving problems like Sudoku that involve searching through a large space of potential solutions.

Like programmers, we’ll solve it step by step, learning from our errors and honing our problem-solving skills.

Introduction to Backtracking

Backtracking is a strategy for solving certain computational problems, most notably constraint satisfaction problems.

In a constraint satisfaction problem, we’re asked to find a solution that meets a specific set of constraints.

As we’ve seen, Sudoku is an example of such a problem: we need to fill the grid so that every row, column, and 3x3 subgrid contains all digits from 1 to 9. In this case, the constraints are the rules of the Sudoku game itself.

What is Backtracking?

At its core, backtracking is an algorithmic approach that involves exploring all possible solutions to a problem by incrementally building candidates and abandoning a candidate (“backtracking”) as soon as it’s determined that the candidate cannot possibly be extended to a good solution.

This approach is commonly used in problems related to decision-making, where the sequence of choices leads to a set of conditions. Backtracking tends to check all possible combinations to find the solution, yet it is more efficient than a brute-force approach since it eliminates many candidates with a single test.

How Backtracking Works

The general algorithmic process of backtracking involves several steps:

Choose: Select a potential option from the remaining possibilities.
Constrain: Apply constraints to eliminate any unfeasible options.
Solve: Try to solve the problem after the option has been selected. If the problem is solved, then the solution has been found. If not, continue with the next steps.
Backtrack: If no solutions are possible after the option has been selected, or all options for the current possibility have been exhausted, then “undo” the decision and backtrack to a previous step, allowing the algorithm to make a new decision in the next iteration.
Iterate: Repeat the process until a solution is found or all possibilities have been exhausted.

The beauty of backtracking lies in its efficiency in finding the solution without needing to explore all possibilities. If a partial solution is deemed invalid, it doesn’t continue down that path. Instead, it “backs up” to a previous step and tries differently.

While the algorithm may seem straightforward, the power of backtracking is unleashed when it’s applied to complex problems where the solution space can be vast. In the next sections, we will see how this algorithm can be implemented in Python and used to solve a Sudoku puzzle.

The Theory Behind Using Backtracking to Solve Sudoku

As we delve into the idea of solving Sudoku using a backtracking algorithm, it’s essential to understand why this algorithm fits the puzzle-solving situation so well and how it works specifically in the context of Sudoku.

Why Backtracking is Suitable for Sudoku

Sudoku is a constraint satisfaction problem where each decision we make, i.e., filling a cell with a number, places constraints on what numbers we can put in the neighboring cells. The goal is to find a solution where all conditions are satisfied simultaneously.

Backtracking is particularly well-suited to such problems, where the solution involves a sequence of decisions that can be made correctly only in the context of previous findings. A reasonable choice at one step can be unworkable in light of subsequent decisions.

The beauty of backtracking is that it allows us to “undo” decisions. In the context of Sudoku, we can tentatively fill in cells. When we find that a choice leads us to an impossible situation (a dead end where there’s no valid number that can be placed in a particular cell), we can “undo” or “backtrack” on our choices, going back to a previous cell and trying a different number.

Applying Backtracking to Sudoku

To understand how backtracking works with Sudoku, imagine you’re solving a Sudoku puzzle. You start at the top left cell and begin filling in numbers, moving from left to right, top to bottom.

With each cell, you first check if the current number you want to place can be placed in the cell. You put it in the cell if it’s valid (meaning it doesn’t violate Sudoku’s rules).

If not, you try the next number. If no numbers can be placed in the cell, you know you’ve made an error somewhere. This is the point where backtracking shines.

You “undo” your last choice (i.e., the number you placed in the current cell is removed) and backtrack to the previous cell. Now, you try the next number for this cell.

If it’s valid, you move forward to the next cell again and repeat the process. If it’s not, you continue trying new numbers in the current cell.

This process continues, moving through the cells, trying new numbers, and backtracking when you hit a dead end. The algorithm continues until you’ve filled in all cells (which means you’ve found a solution) or exhausted all possibilities.

This approach mirrors many people's mental processes to solve Sudoku puzzles, making progress where possible and backtracking to revise earlier decisions when they lead to an impasse.

It’s systematic, logical, and efficient — much like good programming. In the next sections, we’ll see how to translate this process into Python code to create a Sudoku-solving program.

Implementing a Sudoku Solver in Python

Creating a Sudoku solver in Python can be broken down into a few straightforward steps. Here’s a step-by-step walkthrough of the process.

Representing the Board

The first step is to represent the Sudoku board in Python. An easy way to represent the board is with a two-dimensional list (a list of lists) where each sub-list represents a row. Here’s an example of an empty 9x9 board:

board = [[0 for _ in range(9)] for _ in range(9)]

We replaced some zeros with the given numbers for a partially filled board. For example:

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

Checking Validity

Next, we need a function that checks if a particular number can be placed in a given cell. This function must check the row, column, and 3x3 grid for the same number.

def is_valid(board, row, col, num): 
    # Check the row 
    for x in range(9): 
        if board[row][x] == num: 
            return False 
             
    # Check the column 
    for x in range(9): 
        if board[x][col] == num: 
            return False 
 
    # Check the box 
    start_row = row - row % 3 
    start_col = col - col % 3 
    for i in range(3): 
        for j in range(3): 
            if board[i + start_row][j + start_col] == num: 
                return False 
    return True

Finding Empty Spaces

We also need a function to check for an empty space on the board. We’ll traverse the board from top to bottom, left to right.

We return its position once we find an empty space (0). If no spaces are found, we’ll return (-1, -1), which signifies that the board is full.

def find_empty(board): 
    for i in range(len(board)): 
        for j in range(len(board[0])): 
            if board[i][j] == 0: 
                return i, j  # row, column 
    return -1, -1  # No spaces left

Implementing Backtracking

With these helper functions, we can now implement the main backtracking process. This function will take the current state of the board as input, find an empty cell, and try to place numbers 1–9 in it, checking the validity each time.

If a number can be placed, it places the number and recursively attempts to fill in the rest of the board. If it hits a dead end (it can’t place a number in the current empty cell), it backtracks by setting the cell to empty (0) and continues to the last cell.

def solve(board): 
    row, col = find_empty(board) 
 
    if row == -1:  # No more empty spaces, we've solved it! 
        return True 
     
    for num in range(1, 10):  # Try numbers 1-9 
        if is_valid(board, row, col, num): 
            board[row][col] = num 
            if solve(board):  # Recursively try to fill in the rest 
                return True 
            board[row][col] = 0  # Undo if this branch didn't lead to a solution 
 
    return False  # If no number can be placed, start backtracking

With these functions, we’ve built a Python program to solve any Sudoku puzzle! This basic implementation of a backtracking algorithm provides a good foundation for understanding how these algorithms work. For now, congratulations on your Sudoku solver!

Optimizing the Sudoku Solver

While our basic backtracking algorithm is sufficient for solving any solvable Sudoku puzzle, there’s always room for improvement.

Solving some of the more complex Sudoku puzzles might take time with our current implementation. Let’s discuss a couple of ways to optimize our Sudoku solver: using heuristics to choose the next cell to fill and reducing our search space.

Intelligent Cell Selection: Heuristics

Our current algorithm chooses the next cell to fill by scanning the Sudoku board from top to bottom, left to right, until it encounters an empty cell. While this brute-force approach is simple and guaranteed to find an empty cell, it might not be the most efficient strategy.

We can optimize this process by using a heuristic, or a rule of thumb, to guide our selection of the next cell. One such heuristic is the “Most Constrained Variable” or “Minimum Remaining Values” strategy. This method prioritizes the cell with the fewest possible legal values left.

The rationale behind this strategy is first to address the cell with the most constraints, often those with fewer legal values to choose from. By doing so, we can potentially reduce the number of times we have to backtrack, thereby improving the algorithm's time complexity.

Reducing the Search Space

Another way to optimize our solver is to reduce the search space or the set of all possible solutions our solver needs to search through. One approach is using the “Least Constraining Value” heuristic.

When choosing a number to place in a cell, we choose the one with maximum flexibility for filling in the other cells.

We can also use techniques like constraint propagation to update our board to reflect the constraints imposed by placing a number in a cell.

A simple form of constraint propagation is to keep track of the possible numbers for each empty cell and update these possibilities whenever we place a new number.

This can drastically reduce our search space by allowing us to skip numbers that can no longer be placed in a particular cell.

Here’s an elementary example of how to implement constraint propagation in our solver:

def propagate_constraints(board, row, col, num): 
    possible_nums = [set(range(1, 10)) for _ in range(81)]  # List of sets of possible numbers for each cell 
 
    # When we place a number, we remove it from the set of possible numbers for all other cells in the same row, column, and box 
    for x in range(9): 
        possible_nums[row * 9 + x].discard(num) 
        possible_nums[x * 9 + col].discard(num) 
        box_row = (row // 3) * 3 + x // 3 
        box_col = (col // 3) * 3 + x % 3 
        possible_nums[box_row * 9 + box_col].discard(num)

Generating Sudoku Boards

Creating a playable Sudoku board might appear complex, given the constraints that each row, column, and 3x3 box must contain unique numbers ranging from 1 to 9.

However, we can use the power of algorithms to facilitate this process. In this section, we will discuss one of the possible ways to generate a valid Sudoku board.

The Algorithm

One straightforward approach to generating a valid Sudoku board is to start with an empty grid and fill it up one cell at a time, ensuring we always follow the Sudoku rules.

Here’s a simplified version of the process:

Start filling from the top left: Begin at the top left cell and move right, row by row, filling in the numbers.
Select a random number: For each cell, choose a number between 1 and 9 at random.
Check for validity: Check if this number can be placed in the current cell. Suppose it can’t pick another number and try again. If no number can be placed, we’ve made a mistake somewhere and need to backtrack.
Backtrack if needed: If we can’t place a number in the current cell, we backtrack to the previous cell and try to put a different number.
Repeat until the board is filled: Continue this process until the entire board is filled.

This is essentially the same backtracking algorithm we’ve used for solving Sudoku puzzles, just with random number selection instead of sequential trying from 1 to 9.

We define a new class SudokuGenerator which derives from SudokuBoard. It first creates an empty board and lets the solve() method fill the board with the correct numbers.

Then it calls the create_puzzle method to remove numbers from the board.

class SudokuGenerator(SudokuBoard): 
    def __init__(self, difficulty='medium'): 
        """ 
        Initializes a new instance of the SudokuGenerator class. 
        :param difficulty: The difficulty of the generated Sudoku puzzle. 
        """ 
        # Start with a blank board 
        self.board = [[0 for _ in range(9)] for _ in range(9)] 
        self.solve()  # This will fill the board with a valid solution 
        self.create_puzzle(difficulty)

Creating Puzzles

Once we have a filled Sudoku board, we can create a puzzle by removing some numbers. The difficulty of the puzzle can be adjusted by changing the number of cells we empty. Fewer numbers make for a harder puzzle.

class SudokuGenerator(SudokuBoard): 
    def create_puzzle(self, difficulty): 
        """ 
        Creates a Sudoku puzzle with the specified difficulty. 
        :param difficulty: The difficulty of the puzzle. 
        """ 
        difficulties = { 
            'easy': 20, 
            'medium': 30, 
            'hard': 40, 
        } 
 
        # Ensure difficulty is valid 
        if difficulty not in difficulties: 
            raise ValueError('Invalid difficulty. ' + 
                             f'Choose from {list(difficulties.keys())}.') 
 
        # Remove numbers from filled board to create the puzzle 
        for _ in range(difficulties[difficulty]): 
            while True: 
                row, col = random.randint(0, 8), random.randint(0, 8) 
                if self.board[row][col] != 0: 
                    self.board[row][col] = 0 
                    break

However, ensuring the puzzle has a unique solution is important. This can be quite complex, as it requires checking that every number removed doesn’t result in multiple possible solutions.

One way to check this is to use our Sudoku solver. We know we can’t remove that number if it finds multiple solutions.

Validating Our Code with Unit Tests

As we draw closer to the completion of our Sudoku solver and generator, it is essential to ensure the reliability of our program through the incorporation of unit tests.

These tests serve as a quality check, confirming that our solver operates as expected and can successfully solve various Sudoku puzzles from different sources.

Leveraging Test Cases

With our generator in place, we can readily conduct an integration test of our Sudoku-solving routine. These tests will verify that our solver can handle diverse challenges.

In the test case below, we iterate over various difficulty levels (easy, medium, and hard), generating and solving 10 Sudoku puzzles for each level. This process ensures that our solver can tackle Sudoku puzzles of any difficulty.

def test_sudoku_solver(): 
    for difficulty in ['easy', 'medium', 'hard']: 
        for _ in range(10): 
            sudoku = SudokuGenerator(difficulty) 
            assert sudoku.solve(), f"{difficulty} Sudoku puzzle couldn't be solved"

Testing with External Sudoku Puzzles

While our generator allows us to test various puzzles, it’s also important to ensure that our solver can handle Sudoku puzzles from other sources.

In the test case below, we validate our solver using a Sudoku puzzle not generated by our SudokuGenerator. This puzzle, a 2D list, is loaded into an instance of our SudokuBoard class. We then assert that our solver can successfully solve this puzzle.

def test_solve(): 
    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] 
    ] 
    sudoku = SudokuBoard(board) 
    assert sudoku.solve()

In this test, if the solve method returns False, indicating that the puzzle could not be solved, the test will fail. This aids in identifying any potential limitations or issues with our Sudoku solver.

Conclusion

Throughout this journey, we’ve navigated the intricate process of developing a Sudoku solver and generator from scratch using Python. We began by understanding the logic behind solving a Sudoku puzzle built around the backtracking algorithm, a powerful yet simple technique with vast applications.

We delved into each process component, examining the backtracking approach's step-by-step mechanics. By developing our SudokuBoard class, we constructed a versatile puzzle solver that uses backtracking to solve Sudoku puzzles efficiently.

We then took our project further by constructing the SudokuGenerator class, enabling us to create our own Sudoku puzzles of varying difficulty levels. This allowed us to test our solver and understand the nuances of the Sudoku generation process.

Testing was an integral part of our development process. We employed unit tests to ensure our solver functioned as intended, solving internally generated and external Sudoku puzzles.

This practice underpins the importance of testing in software development, particularly when working with intricate algorithms like backtracking.

The beauty of backtracking lies in its application to many real-world problems. While Sudoku was a beautiful and fun demonstration in this article, the principles and Python skills you’ve acquired can be applied far beyond this realm.

The power of Python has shone through in our journey, from its robust handling of data structures to its simplicity in implementing complex algorithms like backtracking. I hope you now have a deeper appreciation of the algorithm and the language.

As we close, I encourage you to explore further.

Could you optimize our code or use a different data structure to improve efficiency?

Could you extend our generator to produce Sudoku puzzles of even greater difficulties?

How about applying the backtracking algorithm to solve other problems, like the Eight Queens puzzle or maze-solving problems?

Thank you for joining me on this journey. As you continue yours, remember that learning is a path, not a destination.