Sudoku Puzzle Solver — How To Build Your Very First Python Project
A typical path followed by someone new to programming is to get acquainted with the syntax of the programming language to begin with, then head over to practicing loads and loads of challenges through various websites such as HackerRank, HackerEarth, CodeWars, Project Euler etc,.
While these platforms are efficient to help build skills to reason, think, apply logic and help improvise your code to efficiently work on large sets of input data, one thing they lack is to help you build reasonable sized projects. When the task in hand gets more complex it requires lot many lines of code. More the code more the number of repetitive elements in it, hence the need to build essential skills to build your code around functions and classes.
Using functions and classes helps a developer up-skill to the next level of writing effective re-usable code. It requires some brainstorming and loads of practice. Sudoku Puzzle solver is a humble effort to help beginners start off with their first mini project that can be built in an hour or so.
A huge shoutout to Tim from Teach With Tim for helping me understand the backtracking algorithm with ease. My implementation was lot more complex and time consuming compared to his. Do refer to his video to understand the backtracking algorithm with visual representation as well.
Rules of a Sudoku Puzzle
- It contains a 9 x 9 puzzle grid sub-divided into 3 x 3 blocks of 9 numbers.
- Each number of any cell in the 9 x 9 puzzle can only be a number between 1 to 9, both inclusive.
- Each 3 x 3 block should have all the numbers between 1 to 9 in any cell. As a 3 x 3 block has 9 cells, it’s obvious that no number can repeat.
- Similarly each row of the 9 x 9 puzzle must have all the numbers between 1 to 9. Again, as each row has 9 cells, no number can repeat.
- Each column needs to have the numbers between 1 to 9 as well and as above, no number can repeat.
Once we completely filled in a Sudoku Puzzle satisfying all the above criteria, we can safely assume that the puzzle has been solved.
Steps to build the program
- We iterate through the puzzle from left to right from top to bottom
- Iterate through the puzzle till you find an empty cell.
- Fill in a valid number. A valid number is the one that is neither in the row in which the cell exists, the column in which the cell exists and the 3 x 3 block the cell exists. This is because no number can repeat more than once in a row, column and in the 3 x 3 block.
- Once you find a valid number, repeat steps 2 and 3.
- While performing step 4, if we reach a point where no number is valid in the empty cell, we backtrack and move to previous cell filled by the algorithm to find the next valid number and continue repeating the puzzle steps 2 and 3 using backtracking and finding the next valid number. Backtracking might sound a bit complex but I shall take time and explain it along with the code below.
- Repeat process until no empty cell exists in the puzzle.
Now that we have formulated a simple algorithm that helps generate a solution to the sudoku puzzle, let’s take a moment to analyse what are the repetitive steps that need a function to be defined.
- An optional function to help load the puzzle from a .txt file
- A function to find an empty cell
- A function to find if a number is valid to be filled in an empty cell.
- A function to print the board at any moment as and when needed
- A function to solve the puzzle using the above methods
Let’s build the algorithm step-by-step to help understand better.
Task 1: Write a function that helps load the puzzle from a text file
Alternatively, you can pre-define the variable board in your program and store a puzzle as a list of 9 elements with each element representing a row of the sudoku puzzle and hence each element of the list is again a list of 9 numbers.
Do note. For the ease of representation, we fill all the empty spaces of the puzzle with a 0 and filled spaces with respective numbers between 1 and 9.
We will start with the code now. Let me show you the code first and then explain what it does.
def loadPuzzle():
"""
A method to read a file having puzzle in it. The puzzle should have nine lines
of nine numbers each between 0-9 seprated by commas.
Arguments:
None
Output:
A list variable board
"""
board = []
fileHandle = open("SudokuPuzzle.txt", "r")
puzzle = fileHandle.readlines()
for line in range(len(puzzle)):
if line != len(puzzle) - 1:
puzzle[line] = puzzle[line][:-1]
board.append(list(map(int,puzzle[line].split(","))))
else:
board.append(list(map(int,puzzle[line].split(","))))
fileHandle.close()
return boardWe begin with opening a text file in read mode using the code fileHandle = open("SudokuPuzzle.txt", "r"). You can edit this code in accordance with your file name and file path.
The next line of code, puzzle = fileHandle.readlines() reads all the lines from the file.
The for loop iterates through each line in the puzzle variable. The contents of for loop are as follows. For all the lines except last line, read the line, remove the last character which is, \n, a new line character present for all line except last line of the SudokuPuzzle.txt file, split it with , as a separator and convert it into a list. For the last line of SudokuPuzzle.txt file as there is no new line character in the end we directly read the line and split it using , as separator.
We then close the file and return board variable that essentially now stores the sudoku puzzle as a list of 9 elements with each element again as a list of 9 numbers between 0 and 9 with 0 representing an empty cell.
Task 2: A function to find the next empty cell
As explained earlier. We iterate first from left to right and then top to bottom in the puzzle. This basically means we have to iterate through the board elements taking first list in it, iterate through it, then the next list etc. The code for this function is quite simple and self explanatory.
def findEmpty(board):
"""
A method to find the next empty cell of the puzzle.
Iterates from left to right and top to bottom
Arguments:
board - a list of nine sub lists with 9 numbers in each sub list
Output:
A tuple (i, j) which is index of row, column
"""
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j] == 0:
return (i, j) #row, column
return NoneThe function above will basically return a tuple (i, j) which is row number and column number of the empty cell found. If no empty cell is found the function return None variable.
3. A function to find if a number is valid to be filled in an empty cell.
We do not try any complex methods to predict which number fits in an empty cell, all the algorithm does is to check if the number already exists in the respective row, column and the 3 x 3 box. If the number already exists, the function returns a False else it return True.
def valid(board, num, pos):
"""
A method to find if a number num is valid or not
Arguments:
board - a list of nine sub lists with 9 numbers in each sub list
num - a number between 1 to 9 both inclusive
pos - a tuple (i, j) representing row, column
Output:
True if the number is valid in position pos of puzzle else False.
"""
row = pos[0]
column = pos[1] #checking rows
for i in range(len(board[0])):
if board[row][i] == num and column != i:
return False #checking columns
for i in range(len(board)):
if board[i][column] == num and row != i:
return False
#checking box
startRowBox = row//3
startColumnBox= column//3
for i in range(startRowBox*3, (startRowBox*3)+3):
for j in range(startColumnBox*3, (startColumnBox*3)+3):
if board[i][j] == num and row != i and column != j:
return False
return True
The code is pretty straight-forward. In first case, the for loop iterates through every element of row number stored in variable row except for location of the cell which is being tested to fill value num. It returns False if it detects that the number is already present in the row.
Then it moves of to check the column. The column number is stored in the variable column. If the value in variable num is already present in column number column, then the function returns False.
Next comes the 3 x 3 box in which the current empty cell is present. To generate the 3 x 3 code iteration, we assume that the entire puzzle is divided in 9 units of 3 x 3 blocks with index numbers 0, 1 and 2 row wise and 0, 1 and 2 column wise. The first box has position (0, 0), second has position (0, 1) and so on until the last one which has position (2, 2).
The first two lines of code help use detect the position of the box in which the empty cell is present. Then we use these position information to iterate through the 3 x 3 block and check if the value in variable num already is present in the block. If present, the function returns False else the end of the function returns True.
4. A function to print the board at any moment as and when needed
We already are aware that the sudoku puzzle is stored in the variable board as a nested list but having a function that prints out the puzzle in a visually appealing manner helps.
def printBoard(board):
"""
A method to print the sudoku puzzle in a visually appealing format
Arguments:
board - a list of nine sub lists with 9 numbers in each sub list
Output:
Prints a nine x nine puzzle represented as a sudoku puzzle. Returns None.
"""
if not findEmpty(board):
print("Finished puzzle")
else:
print("Unsolved puzzle")
for i in range(len(board)):
if i%3 == 0:
print("-------------------")
for j in range(len(board[0])):
if j%3 == 0:
print("\b|", end ="")
print(str(board[i][j])+" ", end="")
print("\b|")
print("-------------------")Again, on a very basic level, we are iterating through the board variable and printing each line out but we detect position 0, 3, 6 and 9 to print spacers in between so that it looks like a sudoku puzzle.
Unsolved puzzle
-------------------
|7 8 0|4 0 0|1 2 0|
|6 0 0|0 7 5|0 0 9|
|0 0 0|6 0 1|0 7 8|
-------------------
|0 0 7|0 4 0|2 6 0|
|0 0 1|0 5 0|9 3 0|
|9 0 4|0 6 0|0 0 5|
-------------------
|0 7 0|3 0 0|0 1 2|
|1 2 0|0 0 7|4 0 0|
|0 4 9|2 0 6|0 0 7|
-------------------At the beginning of this function, it checks if there are still any empty cells in the puzzle. If yes, it prints a heading as Unsolved puzzle but if no empty cells are presents it means that the solution has been found so the function prints Finished puzzle as heading.
Finished puzzle
-------------------
|7 8 5|4 3 9|1 2 6|
|6 1 2|8 7 5|3 4 9|
|4 9 3|6 2 1|5 7 8|
-------------------
|8 5 7|9 4 3|2 6 1|
|2 6 1|7 5 8|9 3 4|
|9 3 4|1 6 2|7 8 5|
-------------------
|5 7 8|3 9 4|6 1 2|
|1 2 6|5 8 7|4 9 3|
|3 4 9|2 1 6|8 5 7|
-------------------5. A function to solve the puzzle using the above methods
The final and most important part of the solution. I shall first share the entire code and then dive into each and every line/lines to explain it further, including the backtracking part. Do not get intimidated by complex words such as backtracking algorithm, this is just a recursion function like the most basic fibonacci series solution that is often taught using recursion.
def solve(board):
"""
A method to solve the sudoku puzzle using the other functions defined.
We use a simple recursion and backtracking method.
Arguments:
board - a list of nine sub lists with 9 numbers in each sub list
Output:
Returns True once the puzzle is successfully solved else False
"""
find = findEmpty(board)
if not find:
return True
else:
row, col = find
for i in range(1,10):
if valid(board, i, find):
board[row][col] = i
if solve(board):
return True
board[row][col] = 0
return FalseThe first part of the code find = findEmpty(board) basically calls the findEmpty(board) function with argument as board and asks it to find the next empty cell. It either returns a tuple as (row, column) coordinates or None if no empty cell is found.
We then define the base case of recursion
if not find:
return TrueThis says, if find has a value None it means the puzzle has been solved successfully and solve() function returns value True indicating the same. But if the puzzle isn’t solved yet and a tuple is returned by findEmpty() function then we store the variables of find in row and column variables. We could have directly used find[0] and find[1] as well but it makes it easier to understand the code using a better representation of variables.
We then start the part of the algorithm that begins to guess which value will fit in the empty cell represented by find. We start iteration from 1 and go up to 9 calling the valid() function each time until it returns True indicating it to be valid guess. After filling in the guess, we recursively call the solve() function once again with the new filled in value. This time it will get the next empty cell and repeat the process. This recursion will go on until it either successfully fills in all values in this iteration or encounters a situation where it reaches a cell where none of the values from 1 to 9 are valid.
When it reaches a situation when a cell cannot take any number as valid values it implies one of the previous guesses is incorrect so the recursion stops here and the line of code after the recursive call, board[row][column] = 0 for the last guessed recursion depth is called. So this basically means, setting the last guess back to 0 and finding a new guess for it. Example: if the last guess was 5, we set it back to 0 and the for loop goes on to test if 6 is valid guess, then 7, then 8 and then 9 etc. If it finds a valid guess, it goes on to fill next empty cells, if not, then it backtracks even further and fills it with 0 and tries new guess again. So basically, the algorithm keeps backtracking each step through recursion.
Once the board is filled with valid values, it returns True and exits the function.
I am sharing the whole code stitched up a single program here.
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sun Dec 22 12:24:49 2019@author: raghu
"""
#uncomment the code below to initiate a puzzle board
#instead of loading it from a file
# =============================================================================
# board = [
# [7, 8, 0, 4, 0, 0, 1, 2, 0],
# [6, 0, 0, 0, 7, 5, 0, 0, 9],
# [0, 0, 0, 6, 0, 1, 0, 7, 8],
# [0, 0, 7, 0, 4, 0, 2, 6, 0],
# [0, 0, 1, 0, 5, 0, 9, 3, 0],
# [9, 0, 4, 0, 6, 0, 0, 0, 5],
# [0, 7, 0, 3, 0, 0, 0, 1, 2],
# [1, 2, 0, 0, 0, 7, 4, 0, 0],
# [0, 4, 9, 2, 0, 6, 0, 0, 7]
# ]
# =============================================================================# loading the puzzle from a file
#comment the loadPuzzle code below if you want to iniate the board above
def loadPuzzle():
"""
A method to read a file having puzzle in it. The puzzle should have nine lines
of nine numbers each between 0-9 seprated by commas.
Arguments:
None
Output:
A list variable board
"""
board = []
fileHandle = open("SudokuPuzzle.txt", "r")
puzzle = fileHandle.readlines()
for line in range(len(puzzle)):
if line != len(puzzle) - 1:
puzzle[line] = puzzle[line][:-1]
board.append(list(map(int,puzzle[line].split(","))))
else:
board.append(list(map(int,puzzle[line].split(","))))
fileHandle.close()
return boarddef findEmpty(board):
"""
A method to find the next empty cell of the puzzle.
Iterates from left to right and top to bottom
Arguments:
board - a list of nine sub lists with 9 numbers in each sub list
Output:
A tuple (i, j) which is index of row, column
"""
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j] == 0:
return (i, j) #row, column
return Nonedef valid(board, num, pos):
"""
A method to find if a number num is valid or not
Arguments:
board - a list of nine sub lists with 9 numbers in each sub list
num - a number between 1 to 9 both inclusive
pos - a tuple (i, j) representing row, column
Output:
True if the number is valid in position pos of puzzle else False.
"""
row = pos[0]
column = pos[1]
#checking rows
for i in range(len(board[0])):
if board[row][i] == num and column != i:
return False
#checking columns
for i in range(len(board)):
if board[i][column] == num and row != i:
return False
#checking box
startRowBox = row//3
startColumnBox= column//3
for i in range(startRowBox*3, (startRowBox*3)+3):
for j in range(startColumnBox*3, (startColumnBox*3)+3):
if board[i][j] == num and row != i and column != j:
return False
return Truedef printBoard(board):
"""
A method to print the sudoku puzzle in a visually appealing format
Arguments:
board - a list of nine sub lists with 9 numbers in each sub list
Output:
Prints a nine x nine puzzle represented as a sudoku puzzle. Returns None.
"""
if not findEmpty(board):
print("Finished puzzle")
else:
print("Unsolved puzzle")
for i in range(len(board)):
if i%3 == 0:
print("-------------------")
for j in range(len(board[0])):
if j%3 == 0:
print("\b|", end ="")
print(str(board[i][j])+" ", end="")
print("\b|")
print("-------------------")
def solve(board):
"""
A method to solve the sudoku puzzle using the other functions defined.
We use a simple recursion and backtracking method.
Arguments:
board - a list of nine sub lists with 9 numbers in each sub list
Output:
Returns True once the puzzle is successfully solved else False
"""
find = findEmpty(board)
if not find:
return True
else:
row, col = find
for i in range(1,10):
if valid(board, i, find):
board[row][col] = i
if solve(board):
return True
board[row][col] = 0
return False
board = loadPuzzle() #loading the board from puzzle file
printBoard(board) #printing the board before solving the puzzle
solve(board) #solving the puzzle
printBoard(board) #printing the puzzle after solving
