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!
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 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:
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.
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.
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)]
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...
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.
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.
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.
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.
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]
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]
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!
Starting out with general purpose computing on the GPU, we are going to write a WebGPU compute shader to compute Morton Codes from an array of 3-D coordinates. This is the first step to detecting collisions between pairs of points.
Read More
In this post, I am dipping my toes into the world of compute shaders in WebGPU. This is the first of a series on building a particle simulation with collision detection using the GPU.
Read More
Finding the Lowest Common Ancestor of a pair of nodes in a tree can be helpful in a variety of problems in areas such as information retrieval, where it is used with suffix trees for string matching. Read on for the basics of this in Python.
Read More
