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 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.
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):
#find next empty cell
for number in number_list:
if not self.find_empty_square(grid):
#if the grid is full
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.
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.
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.
- Remove a random non-empty square.
- Solve the new grid with backtracking, but count the solutions and make sure there is only one unique solution.
- 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.
"""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]
#make a copy of the grid to solve
grid_copy = copy.deepcopy(self.grid)
#initialize solutions counter to zero
#if there is more than one solution, put the last removed cell back into the grid
non_empty_squares_count += 1
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
for row in new_puzzle.grid:
[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
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
for row in solved.grid:
[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!