Posted by Stuck on a Sudoku Puzzle? Python can solve it for you!
Sudoku is a logic-based number-placement game. Below is an example of a sudoku puzzle from Wikipedia
As you can see, there are 9 rows and 9 columns (81 boxes), some boxes are filled with a number while most are empty. The goal of the game is to fill the empty boxes with numbers such that all the constraints are satisfied. The rules of the games are below
- Each box must have a digit between 1 to 9 (inclusive)
- Each row should contain all the digits from 1 to 9 with no repeating digits
- Each column should contain all the digits from 1 to 9 with no repeating digits
- Each sub-grid ( the 9 smaller boxes) must also contain all the digits from 1 to 9 with no repeating digits
- A box can have only one digit
We will be using the PuLP library in Python to solve the above sudoku puzzle, if you are unfamiliar with PuLP, I recommend you to check out my tutorial below
Setting Up the Problem
In each box, only one value can be present and the other values won’t be present. Therefore we can think of it as a binary variable having a value 0 if the number is not present and 1 if it is present. The variables will be in a format as below
(value, row, col)
Suppose we select a box, i.e we set the row and col as constant, the value can range from 1 to 9
In the below example, in the top left corner box (1,1 in a 1-indexed array), the value of ‘5’ would be 1 while the rest of the digits from 1–9 would have the value 0.
(value = 1, row =1 , col=1) = 0 ,(value = 2, row =1 , col=1) = 0 ,
(value = 3, row =1 , col=1) = 0 ,(value = 4, row =1 , col=1) = 0 ,
(value = 5, row =1 , col=1) = 1,(value = 6, row =1 , col=1) = 0 ,
(value = 7, row =1 , col=1) = 0 ,(value = 8, row =1 , col=1) = 0 ,
(value = 9, row =1 , col=1) = 0 ,
Since the row and the column can both range from 1 to 9, there can be 81 different combinations of (row, col). Each combination will have 9 binary variables. Therefore, there are a total of 729 different combinations or variables
Out of these 729 different combinations, only 81 of them will have the value 1 while the rest will have a value 0. Since we are already given some of the values on the board, we already know which variable will have a value 1 in those boxes. We are given the values for 30 of the boxes, which means we already know the values for 270 of the variables. We need to find the values for the other 459 variables.
'''
Defining Rows, Cols and Values of Sudoku Board
'''
numbers = [str(i) for i in range(1,10)]
Rows = numbers
Cols = numbers
Values = numbers
'''
729 Different combinations
'''
choices = LpVariable.dicts("Choice",(Values,Rows,Cols),0,1,LpInteger)
Objective Functions
A sudoku puzzle doesn’t have an optimal solution, i.e we do not have to maximize or minimize any functions. Therefore we can define our problem as Lp.maximize or Lp.minimize and set our objective function to 0.
'''
Creating the Problem
'''
prob = LpProblem("Sudoku Problem",LpMinimize)
'''
Objective Function, set to 0 since Sudoku doesn't have an optimal solution
'''
prob += 0, "Arbitrary Objective Function"
Constraint 1: Each box can only have one value
As I mentioned before, our variables are formatted as below:
(value , row ,col)
To ensure that each box has only value, we can keep the row, col constant and vary the value from 1 to 9. The sum of the binary values should be equal to 1 since only one variable will be equal to 1 and others must be 0.
(value = 1, row =1, col =1) + (value = 2, row =1, col =1) + (value = 3, row =1, col =1) + (value = 4, row =1, col =1) + (value = 5, row =1, col =1) + (value = 6, row =1, col =1) + (value = 7, row =1, col =1) +(value = 8, row =1, col =1) +(value = 9, row =1, col =1) == 1
We will need to perform this check for all different combinations of row, col
'''
Constraint: Only One number can be present in a box
'''
for r in Rows:
for c in Cols:
prob += lpSum([choices[v][r][c] for v in Values]) == 1, ""
Constraint 2: Each row must have all values from 1 to 9 and no number can be present more than once
For this case, we can keep the value and row constant while varying the col from 1 to 9
For Example, we want to check the number 1 is present only once in the first row
(value = 1, row =1, col =1) + (value = 1, row =1, col =2) + (value = 1, row =1, col =3) + (value = 1, row =1, col =4) + (value = 1, row =1, col =5) + (value = 1, row =1, col =6) + (value = 1, row =1, col =7) + (value = 1, row =1, col =8 )+ (value = 1, row =1, col =9)== 1
Similarly, we set the value = 1 and row = 2 and repeat the process, we need to do this for all possible combinations of value, row
'''
Constraint: A row should have all the numbers from 1-9 and
no number can be repeated
'''
for v in Values:
for r in Rows:
prob += lpSum([choices[v][r][c] for c in Cols]) == 1, ""
Constraint 3: Each column must have all values from 1 to 9 and no number can be present more than once
This is really similar to our previous constraint and instead of keeping value and row constant, we keep value and col constant.
'''
Constraint: A column should have all the numbers from 1-9 and no
number can be repeated
'''
for v in Values:
for c in Cols:
prob += lpSum([choices[v][r][c] for r in Rows]) == 1, ""
Constraint 4: Each of the 9 subgrids must have all values from 1 to 9 and no number can be present more than once
Our sudoku board has 9 smaller boxes and similar to the row and column constraint, each value from 1 to 9 must be present in the subgrid and no number can be repeating
First, we will create a variable to store the 9 boxes
'''
Sub Grids, i.e the 9 boxes inside the sudoku Board
'''
Subgrids =[]
for i in range(3):
for j in range(3):
Subgrids += [[(Rows[3*i+k],Cols[3*j+l]) for k in range(3) for l in range(3)]]
The code looks complicated but it essentially divides our board into 9 subgrids. The variable Subgrids will have 9 lists each representing one of the subgrids. Each list will have the list of the co-ordinates of the boxes in it.
For example, Subgrids[0] represents the first subgrid and contains the coordinates of the boxes in it.
print(Subgrids[0])
''' output '''
[('1', '1'), ('1', '2'), ('1', '3'),
('2', '1'), ('2', '2'), ('2', '3'),
('3', '1'), ('3', '2'), ('3', '3')]
For Subgrid 0 , we keep the value constant and iterate over the list to get the row, col co-ordinates and check the binary value. The sum should be equal to 1 for each value from 1 to 9
(value = 1, row =1, col =1) + (value = 1, row =1, col =2) + (value = 1, row =1, col =3) + (value = 1, row =2, col =1) + (value = 1, row =2, col =2) + (value = 1, row =2, col =3) + (value = 1, row =3, col =1) + (value = 1, row =3, col =2 )+ (value = 1, row =3, col =3) == 1
'''
Constraint: The sub-grids, i.e the 9 boxes, should have all the
numbers from 1-9 and no number can be repeated
'''
for v in Values:
for b in Subgrids:
prob += lpSum([choices[v][r][c] for (r, c) in b]) == 1, ""
Constrain 5: Set the variables with numbers given to 1
We are already given the nunbers in 30 boxes, we will need to add this to our constraint as well.
First we will create a variable to store the given numbers in the format [value , row , col ]
sudoku_problem = [
["5","1","1"],
["6","2","1"],
["8","4","1"],
["4","5","1"],
["7","6","1"],
["3","1","2"],
["9","3","2"],
["6","7","2"],
["8","3","3"],
["1","2","4"],
["8","5","4"],
["4","8","4"],
["7","1","5"],
["9","2","5"],
["6","4","5"],
["2","6","5"],
["1","8","5"],
["8","9","5"],
["5","2","6"],
["3","5","6"],
["9","8","6"],
["2","7","7"],
["6","3","8"],
["8","7","8"],
["7","9","8"],
["3","4","9"],
["1","5","9"],
["6","6","9"],
["5","8","9"]
]
Now we add them to our constraints
# The starting numbers are entered as constraints
for num in sudoku_problem:
prob += choices[num[0]][num[1]][num[2]] == 1, ""
Finally , we solve the problem
You can use the below function to store the solved sudoku in a text file
def display_sudoku(matrix , sudokuout , numbers):
for r in numbers:
if r == "1" or r == "4" or r == "7":
sudokuout.write("+-------+-------+-------+\n")
for c in numbers:
for v in numbers:
if value(matrix[v][r][c]) == 1:
if c == "1" or c == "4" or c == "7":
sudokuout.write("| ")
sudokuout.write(v + " ")
if c == "9":
sudokuout.write("|\n")
sudokuout.write("+-------+-------+-------+")
It takes in our Lp variable, the file object to write the sudoku into and the a range of numbers from 1 to 9.
Note: the numbers be in a string format
# The problem is solved using PuLP's choice of Solver
prob.solve()
# The status of the solution is printed to the screen
print ("Status:", LpStatus[prob.status])
''' Content of the output File ''' +-------+-------+-------+ | 5 3 4 | 6 7 8 | 9 1 2 | | 6 7 2 | 1 9 5 | 3 4 8 | | 1 9 8 | 3 4 2 | 5 6 7 | +-------+-------+-------+ | 8 5 9 | 7 6 1 | 4 2 3 | | 4 2 6 | 8 5 3 | 7 9 1 | | 7 1 3 | 9 2 4 | 8 5 6 | +-------+-------+-------+ | 9 6 1 | 5 3 7 | 2 8 4 | | 2 8 7 | 4 1 9 | 6 3 5 | | 3 4 5 | 2 8 6 | 1 7 9 | +-------+-------+-------+
The solution for the sudoku is wikipedia is below
You can cofirm that our solution matches that given on wiki 😃
Conclusion
Ways to further build on top of this
- Reformat the code so the given number can be accepted as a parameter of a function
- Use OpenCV and the new function to create an app that takes in the picture of a sudoku and solves it (I will be writing a tutorial related to this soon)
Thank You for reading the article, do let me know if you have any questions 🙂
Resources
https://www.coin-or.org/PuLP/CaseStudies/a_sudoku_problem.html
3 comments
Comments are closed.