Sudoku Solver-Python using Backtracking
sudoku = input("Enter Soduku")
# 070000009510420600080300700008001370023080040400900100962800030000010400700203096
puz = [[int(sudoku[(i+j)-1]) for i in range(1,10)] for j in range(0,81,9)]
def check(puzzle, i, row, col):
rows = puzzle[int(row)]
column = [puzzle[r][col] for r in range(0,9,1)]
if i in rows:
return False
if i in column:
return False
SquareRow = (row // 3)*3
squareColumn = (col // 3)*3
Square = [puzzle[y][z] for y in range(SquareRow, SquareRow+3) for z in range(squareColumn, squareColumn+3)]
if i in Square:
return False
return True
def find(puzzle):
for i in range(0,9,1):
for j in range(0,9,1):
if puzzle[i][j]==0:
return i,j
return None
def solve(board):
finds = find(board)
if not finds:
return True
else:
row, col = finds
for i in range(1,10):
if check(board, i, row, col):
board[row][col] = i
if solve(board):
return True
board[row][col] = 0
return False
print(solve(puz))
print(puz)Welcome to the tutorial on making a sudoku solver in python. I am going to warn you all, that this involves backtracking which is a pretty complex topic to get a grasp on if you are an absolute beginner/ rookie so I would advice looking at getting the grips of loops, functions and the basic instructions of python before you come to trying to understand this code. I am still an intermediate programmer in my eyes and it took me 5 hours to code this with a lot of guidance from the internet so you have been warned!
If you want a list of everything you need to know before looking at this, here is a checklist:
- List comprehension
- recursion
- indexing and the use of range in loops
- functions and how parameters are used
- 2D arrays and how to index from them
- Comparison statements
Thats about all the complicated topics so if you understand what all of those are, then we can begin!!
I’ll start by explaining sudoku:
In a sudoku board, there is a 9x9 grid which are split into 9, 3x3 squares. Your objective is to fill in the grid so that every row, column and individual grid has the numbers 1–9 going through it. This means each column, row and 3x3 grid aren’t allowed to have repeated numbers in them.
Now that we understand the concept, then let’s start explaining this code.
sudoku = input("Enter Soduku")
# 070000009510420600080300700008001370023080040400900100962800030000010400700203096this is simply used to input the sudoku you want to solve, this would have the sudoku input in rows where 0 is any tile that we don’t know. I commented out my test data for my program which is the long string of integers, that integer corresponds to the sudoku below which as you can see, is identical if you put al the rows next to each other from top to bottom and replace the blanks with 0. We choose 0 as it is easy to index as it has a length of 1 character while also not being part of the possible numbers(1–9) which makes it a lot easier to index.
After that we do a list comprehension:
puz = [[int(sudoku[(i+j)-1]) for i in range(1,10)] for j in range(0,81,9This is a list comprehension. It takes the input of the sudoku variable from before and splits it up into the 9 rows like in the diagram above. We need this in a 2D array so we have to list comprehend a list in a list comprehension. This works the same way as:
puz = []
for i in range(0,81,9):
append = []
for j in range(1,10):
append.append(i+j)
puz.append(append)
print(puz)This basically shortens that code into one line where we can split the code into the same layout as a sudoku which is important when we want to check that a number is valid in a position ie. the number isn’t repeated in it’s row, column or the 3x3 square that it is in. We use this puz variable for everything we do in this program.
When abstracting this problem, you’d realise this program only really revolves around 3 real tasks: finding the 0, finding what values are possible, checking if it leads to a working sudoku solution, if not we can easily just backtrack and try a different possibility. This makes it very efficient to use functions and more importantly recursion. Recursion is a self calling function which allows us to continuously run through a possible solution for our solution and if it fails, we can return false and therefore backtrack. Therefore the next 3 sections will all be about the 3 functions.
Note: These are functions so they won’t run unless we specifically call them which is the last 2 lines are print(solve(puz)),print(puz) as they will both run the functions. I nested some functions inside other functions so they are all run.
def check(puzzle, i, row, col):
rows = puzzle[int(row)]
column = [puzzle[r][col] for r in range(0,9,1)]
if i in rows:
return False
if i in column:
return False
SquareRow = (row // 3)*3
squareColumn = (col // 3)*3
Square = [puzzle[y][z] for y in range(SquareRow, SquareRow+3) for z in range(squareColumn, squareColumn+3)]
if i in Square:
return False
return True
def find(puzzle):
for i in range(0,9,1):
for j in range(0,9,1):
if puzzle[i][j]==0:
return i,j
return None
def solve(board):
finds = find(board)
if not finds:
return True
else:
row, col = finds
for i in range(1,10):,
if check(board, i, row, col):
board[row][col] = i
if solve(board):
return True
board[row][col] = 0
return FalseThese functions are pretty difficult to explain without the context of each other so I’m going to explain them in the order that the computer(interpreter) would run them so you can understand why it happens. So, as you saw in the print statement, we call the function solve. This would run:
def solve(board):
finds = find(board)
if not finds:
return True
else:
row, col = findsthe first line assigns the variable finds to the values returned by the function find which I will explain once I explain the rest of this. There are 2 possibilities from the find function, it will have either found an empty position on the sudoku and in this case it would have returned the index for that position, or the entire board would have been filled, meaning that the entire sudoku has been solved, and in this case, we would need the program to react to end the loop. Therefore, we say if not finds(which basically means if there is no value assigned to find) return True which would break us out of the solve function else, we would assign the values of the finds variable to row, col which represent the row index and column index of the 2D array.
def find(puzzle):
for i in range(0,9,1):
for j in range(0,9,1):
if puzzle[i][j]==0:
return i,j
return NoneThis code is going to iterate through every index in the puzzle and if we find a 0 in the index of our puz array, then we return the row and column index. You may be asking how I’ve changed from the array name being puz to puzzle, basically in functions, we may use of local variables which means these variables only exist inside the function and can’t be accessed outside of it. Similarly, we can’t use variables outside the function inside it. So, to use external variables, we use parameters which are the variables in the brackets where we declare the function find. This means when we call the function, if we pass into the function so eg find(s), this would assign the value of s to puzzle and the iterate through the function and then assign the result of the function to whatever variable we have it with.
for i in range(1,10):,
if check(board, i, row, col):Now that we have found a blank spot where we need to add an integer, we need to find out what numbers we could possibly put into that position. This means we do the loop for i in range(1,10) which would iterate from 1 to 9 which are all the possible numbers and then we would run this possible number into the check function to check whether it is possible to put that number into that position considering the rules of sudoku.
def check(puzzle, i, row, col):
rows = puzzle[int(row)]
column = [puzzle[r][col] for r in range(0,9,1)]
if i in rows:
return False
if i in column:
return False
SquareRow = (row // 3)*3
squareColumn = (col // 3)*3
Square = [puzzle[y][z] for y in range(SquareRow, SquareRow+3) for z in range(squareColumn, squareColumn+3)]
if i in Square:
return False
return TrueThis code is going to use list comprehension to check that the number we want to put into the sudoku is valid to the rules of the game ie no number in its row, column and square is the same. The rows variable simply indexes out the entire row that the position we are deciding from. We know the the row to check since we have passed in the index of the position of the blank space from the find function into this function. We use a list comprehension for the column as we can’t simply index a column, we do that by changing r, the row, while keeping the column constant effectively moves down a straight line on the array pulling the column.
We now need to check that the values in these rows and columns don’t match the value we are checking the validity of, we do this by doing if i in rows which basically checks if the value of i is in the list of specified so in this case rows and column, this would run the if statement if the statement is true and won’t if its false. So if i is in either list, then we return false which tells the program that the number we are trying isn’t possible to be placed in the position and so we would check a new value. This checks the rows and columns which now only leaves us with the 3x3 square which is the hardest part of this.
SquareRow = (row // 3)*3
squareColumn = (col // 3)*3
Square = [puzzle[y][z] for y in range(SquareRow, SquareRow+3) for z in range(squareColumn, squareColumn+3)]
if i in Square:
return False
return TrueWe want to get the 3x3 square and we know that each of these 3x3 grids indexes will start at a multiple of 3 so the index of the first grid on the top left will be 0,0 and then the first position in the middle square of the top row would be 0,3 etc. This means if we want to iterate through each square, we want to find the 3x3 square which holds this value and we can very easily do this by using the div function which is written as // which returns the division without remainders. We then need to multiply this by 3 to get the starting index of the square. We can see this works if you sub in test data such as (5,5) which would return (3,3) which is the correct starting index of the square. Now, using these indexes, I decide to list comprehend the values in the square. The logic behind the list comprehension should be very self explanatory, it will increment through the first row so the y values before increasing the z value and then running through that 3 times to pull out all 9 values in the square. We now do a similar check to before where if the value is in the list, therefore the square, we return false as we aren’t allowed to place the number in. At this point if all these 3 conditions have been met, this means it is possible for us to put the number in the position which means we can return True. We can put return True without any if statement because when we execute a return method, it stops all processing in the function which means the rest of the function won’t be run so when we return from all the 3 possibilities, any values that aren’t allowed will have returned False and it wouldn’t reach the return True line.
for i in range(1,10):,
if check(board, i, row, col):
board[row][col] = i
if solve(board):
return True
board[row][col] = 0
return FalsePrepare your brains for some mind blowing ideas. This is truly big brain.
We are at the point where we have run the if check(…): statement and from the function, we have returned either true or false, if true, we run the if statement. In the if statement, we use the indexes we have gotten from the find function and assign the value of we have tested to work in that position. This has morphed the board so that it is now updated. We then do the recursion portion of the program which is the if solve(board) which will use this updated board to now run the solve function again. As you will note, this means that each time we run through the function, we are adding values onto the puz array which would be the program attempting to solve the solution. This is a form of brute force to solve the method. This recursion will continuously run unless we solve(board) becomes false or as we saw before, when the find function can’t find any 0s, so the sudoku has been solved, then we return True.
So this function is going to run through the sudoku constantly adding number but eventually you’re going to notice that we are going to run into the issue that we may be adding wrong values into a square which means that while the board is partially solved may mean more than 1 number is possible for the same position. This is very backtracking is used:
In the situation where all the possible values of i(so the number we want to put into the sudoku) are not possible(meaning one of our older values are wrong), the if statement above won’t run and instead we are going to return False. This is going to quite us out of the current solve function into the last value that we have changed and now run its next iteration of i and therefore change its value of i in the index on the sudoku. You’ll realise we first reset the index by using board[row][col] = 0. This means every time we reach an error where we can’t put any values into a blank spot in the sudoku, the program will automatically backtrack and try resolve the error in the values it has previously written onto the blank spaces in an attempt to allow it to put a value in the blank space which it had prior not been allowed to write in. The repeat process of this will eventually brute force its way through the entire sudoku until it solves out the entire sudoku. A truly big brain way of backtracking to solve the problem. I understand that backtracking is a hard concept to grasp(I only learned about it when writing this program and it took me a few hours to fully grasp it so don’t expect to get it straight away) so watch these videos if you need extra guidance.
At this point, the puz variable is going to be morphed to the solution and we would have True returned to the solve() function which is why initially it will print True on the terminal before the list of the solution.
You are going to note that I’ve specifically have had the solution to be still printed as a list rather than it being printed in the sudoku 9x9 grid format which is my challenge to you.
Challenge: Take the solved sudoku list and print it in the sudoku 9x9 format.
Well done! You have made a sudoku solver using backtracking on python!
