Generating and solving Sudoku puzzles with Python

You may be familiar with Sudoku puzzles and possibly have even solved a few in your day.

If not, the standard Sudoku puzzle is a 9 x 9 grid that is divided into 9 boxes of 3 x 3 squares - 81 squares total.

It will have a variable number of clues, or numbers that have been filled in.

Then you fill in the rest of the numbers to solve the puzzle.

There are rules to this, of course!

• Each square must contain a number between 1 and 9.
• Each number 1-9 can only appear once in each row, column and box.

A proper Sudoku has only one unique solution.

There must be at least 17 clues in order to have a puzzle with one unique solution.

Check out this article to read more about how puzzles with fewer than 17 clues will have more than one unique solution.

There are a few algorithms that can be used to solve Sudoku puzzles, and in this post I'm going to use a backtracking algorithm to generate and solve Sudoku puzzles.

The code for this post can be found here.

Backtracking algorithm

Backtracking is a type of depth-first search algorithm that can be used to find some or all solutions to a problem, and is often used for constraint satisfaction problems such as Sudoku or crossword puzzles, or the eight queens puzzle.

In Sudoku the constraints are:

• each square must contain a number from 1-9
• each number 1-9 can only occur once in a column, row, or 3x3 box

Backtracking is a brute force search algorithm that incrementally builds a solution, and backtracks when it takes a direction in the search path that will not lead to a solution.

Instead of starting all over again each time it realizes that a solution will not be viable, it takes a step back and then continues in a different direction.

The best explanation I've heard for backtracking is using the choose -> explore -> unchoose pattern. I learned about it from a video of a lecture at Stanford University, and the lecture notes can be found here.

Generating Sudoku puzzles

We're going to use the backtracking algorithm to generate Sudoku puzzles, and pretty much the same algorithm will be used to solve the puzzles as well.

Steps to generate a Sudoku puzzle

1. Start with an empty grid.
2. Generate a complete solution using backtracking that fills up the grid.
3. Remove numbers from the grid, while making sure the solution is still unique.

Empty grid

The empty grid will be represented with a 2-D matrix of zeroes, where a zero indicates an empty square.

grid = [[0 for i in range(9)] for j in range(9)]

Generate a complete solution

To generate a complete solution, we will use backtracking to go through each square in the board and check each number in each square to see if we can generate a valid solution with it.

It's a recursive function that goes through each square in the board and tries each number 1-9 to see if a solution can be built from it.

def generate_solution(self, grid):
    """generates a full solution with backtracking"""
    number_list = [1,2,3,4,5,6,7,8,9]
    for i in range(0,81):
        row=i//9
        col=i%9
        #find next empty cell
        if grid[row][col]==0:
            shuffle(number_list)      
            for number in number_list:
                if self.valid_location(grid,row,col,number):
                    self.path.append((number,row,col))
                    grid[row][col]=number
                    if not self.find_empty_square(grid):
                        return True
                    else:
                        if self.generate_solution(grid):
                            #if the grid is full
                            return True
            break
    grid[row][col]=0  
    return False

In this code you can see the choose -> explore -> unchoose pattern as we iterate through the squares in the grid.

For each square...

• Choose a number 1-9 that could go in the square, and if it's valid(not already in the same row/column/box), assign it to that square.
• Now explore recursively to find out if putting a the chosen number in that square will lead to a valid, unique solution.
• If it doesn't lead to a solution, then you unchoose by removing that number from the square and trying the next number choice.

So we test each number in each square and recursively check the rest of the board until we find a solution, which is why it's a brute force algorithm.

The number choices 1-9 are shuffled(a random permutation of their order is generated) because otherwise the same solution grid would be generated each time.

The function returns True if there are no more empty squares.

If there is a partial solution grid and the algorithm gets through all of the rest of the squares without reaching a full solution, then the function returns False and backtracks by replacing the last square in the partial solution with a 0 and starting over.

The function valid_location checks whether or not a number choice can legally be put in a square.

It calls other functions to determine whether or not the current number choice already exists in the same row, column, or box.

Remove numbers

After generating a complete solution grid, it's time to start removing numbers to create the puzzle.

We can't just remove a few numbers, willy nilly, and call it a day.

If we just randomly remove some numbers, the puzzle we end up with might not have one unique solution.

Instead we start removing numbers one at a time, and after removing each number check to make sure the solution is still unique.

1. Remove a random non-empty square.
2. Solve the new grid with backtracking, but count the solutions and make sure there is only one unique solution.
3. If there is only one solution, then continue on and remove another empty square and repeat the process, or if there is more than one solution, put the number back in the grid and either try again removing more squares, or stop and keep the generated puzzle.

def remove_numbers_from_grid(self):
    """remove numbers from the grid to create the puzzle"""
    #get all non-empty squares from the grid
    non_empty_squares = self.get_non_empty_squares(self.grid)
    non_empty_squares_count = len(non_empty_squares)
    rounds = 3
    while rounds > 0 and non_empty_squares_count >= 17:
        #there should be at least 17 clues
        row,col = non_empty_squares.pop()
        non_empty_squares_count -= 1
        #might need to put the square value back if there is more than one solution
        removed_square = self.grid[row][col]
        self.grid[row][col]=0
        #make a copy of the grid to solve
        grid_copy = copy.deepcopy(self.grid)
        #initialize solutions counter to zero
        self.counter=0      
        self.solve_puzzle(grid_copy)   
        #if there is more than one solution, put the last removed cell back into the grid
        if self.counter!=1:
            self.grid[row][col]=removed_square
            non_empty_squares_count += 1
            rounds -=1
    return

There are a few ways you could go about removing the numbers.

You could indicate a certain number of clues you want to leave in the puzzle - but this might take forever to run because it might have to backtrack a lot in order to have exactly the number of clues. A puzzle might not even exist with a certain exact number of clues.

In this code, numbers are removed one at a time and each time the puzzle is tested to see how many solutions there are.

I've made a copy of the grid for each iteration of removing numbers and testing to see if there is a unique solution.

In the code the rounds variable starts at 3 and is decremented each time we find multiple solutions to a puzzle, so that it won't just stop after the first time it encounters a puzzle with multiple solutions.

When multiple solutions are counted, the last number removed is put back into the puzzle and then it continues on selecting non-empty squares to try to remove.

After completing the rounds, we are left with the puzzle from above.

Solving the puzzle

We can solve the puzzle using the same backtracking algorithm that was used to generate the first full solution from the empty grid.

I'm going to use the SudokuGenerator class here to illustrate both use cases - to generate the puzzle to solve, and then to solve the puzzle.

In case you missed it, the code is here.

Generate a new puzzle

new_puzzle = SudokuGenerator()

We can see the 2-D matrix for this puzzle in the grid attribute.

for row in new_puzzle.grid:
    print(row)

[9, 2, 0, 0, 0, 0, 5, 8, 4]
[0, 0, 0, 5, 0, 0, 0, 0, 3]
[0, 8, 3, 0, 9, 2, 0, 0, 0]
[2, 6, 0, 8, 5, 4, 0, 0, 1]
[0, 0, 5, 3, 6, 1, 0, 9, 0]
[1, 0, 0, 0, 0, 9, 0, 0, 0]
[8, 5, 0, 2, 0, 3, 0, 1, 0]
[4, 1, 2, 9, 8, 0, 0, 3, 0]
[3, 9, 0, 0, 0, 6, 8, 0, 0]

Solve a puzzle

If you initialize the SudokuGenerator class and pass it a puzzle grid, it will solve the puzzle.

solved = SudokuGenerator(grid=new_puzzle.grid)

You can pass any 2-D grid into this, and here I've just passed in the puzzle we generated new_puzzle.grid.

I've implemented a basic check to make sure input is a 9x9 matrix, but if this were being used as a serious project, you would probably want to check the input puzzle to make sure it's a valid Sudoku as well.

The puzzle grid is updated directly, so to view the solved puzzle you can just iterate through solved.grid.

for row in solved.grid:
    print(row)

[9, 2, 1, 6, 3, 7, 5, 8, 4]
[6, 7, 4, 5, 1, 8, 9, 2, 3]
[5, 8, 3, 4, 9, 2, 1, 6, 7]
[2, 6, 9, 8, 5, 4, 3, 7, 1]
[7, 4, 5, 3, 6, 1, 2, 9, 8]
[1, 3, 8, 7, 2, 9, 6, 4, 5]
[8, 5, 6, 2, 7, 3, 4, 1, 9]
[4, 1, 2, 9, 8, 5, 7, 3, 6]
[3, 9, 7, 1, 4, 6, 8, 5, 2]

Thanks for reading!

In this post we generated and solved Sudoku puzzles using a backtracking algorithm.

The main downside of using backtracking is that it can be very slow, which you can likely imagine just thinking about iterating through each number choice 1-9 for each of the 81 squares in the puzzle, and then adding in the backtracking.

The algorithm used in this post doesn't really mimic how humans solve the puzzles either.

You might try to fill in obvious squares that only have one option and then fill in other squares that have fewer options, while this algorithm systematically goes down the rows and columns to examine the possibilities for each square.

How would you implement an algorithm that would more closely mimic the way humans go about solving Sudoku puzzles?

Let me know in the comments, or reach out to me on Twitter @LVNGD!