
Sudoku is a popular Japanese puzzle game that is based on the logical placement of numbers. It doesn’t require any special mathematics skills or calculations. Let’s look at an example below from Wikipedia:

It is a 9×9 grid puzzle (81 squares). At the beginning of the game, some squares are filled with digits, while most of them are empty. The goal of Sudoku is to fill those empty squares with digits so that each row, column, and 3×3 section contains numbers between 1 to 9. The players need to use logic to fill in the missing digits and complete the grid so that all the constraints and rules are satisfied. A move is incorrect if:
- Any row contains more than one of the same digit from 1 to 9.
- Any column contains more than one of the same digit from 1 to 9.
- Any 3×3 grid contains more than one of the same digit from 1 to 9.
In the previous article, I have created a sudoku solver using a recursive function that is similar to using an 81-level nested for
loop. However, it is very inefficient to solve the Hard Sudoku problem which contains much fewer starting numbers than simple or medium ones. If there are very few starting numbers were present, the sudoku problem would have a very large number of feasible solutions, instead of just one. Therefore, it increases the search space and hence increases the computational cost if we use the brute force approach to solve it.
In this article, I would like to show how to use the Linear Programming method, a more efficient way to create a sudoku solver. Before that, let me share a little background about it.
What is Linear Programming?
Linear Programming (LP) is one of the subfields of mathematical optimization. It is a method to find the most optimal solution for a problem given some constraints. Linear programming consists of the following components:
- A Linear objective function which we either want to maximize or minimize
- A set of n variables of x₁,…, xₙ which control the objective function
- A set of constraints expressed by linear inequalities or equations
So, if a problem is able to formulate in terms of the linear objective function with a set of linear inequality constraints, linear programming is a powerful tool to find the best optimal solution.
Sudoku Solver (Linear Programming Approach)
I am using a Python package called PuLP to solve the LP problems. Now, let’s define the 3 main components of LP for the Sudoku puzzle.
Formulate the Objective Function
Unlike a typical Linear programming problem, with sudoku, there is no solution that is better than another solution. In sudoku, we are not really trying to minimize or maximize anything instead we are trying to find the values on our variables that satisfy a set of constraints. Therefore, minimization or maximization of the objective function is not important and the objective function could be anything. In this article, I will use zero as the objective function.
Identify a Set of Decision Variables
Even we can ensure the sum of all values in a row or column or 3×3 grid equals (1+2+3+4+5+6+7+8+9 = 45), it can still result in many other solutions that satisfy the 45 constraint but still with more than 1 same number in a row or column or 3×3 grid i.e., (1+1+1+5+6+7+7+8+9 = 45). Therefore, we cannot simply create a variable for each of the 81 squares with values between 1 and 9.
Instead, we must create a 9³ = 729 combination of (value, row and column) individual binary (0–1) problem variables. The binary variable indicates whether the existence of the value or number in a square is true or false. Eg. A variable (5,4,6) with the binary value of 1 means the value 5 was present in the square situated in row 4, column 6. Similarly, if the binary value is 0, it would mean there was not a value of 5 there.
Identify a Set of Constraints
- There must be only one number within any square. With the definition of decision variables I mentioned above, it is clear that for each square there can be only 1 of the 9 values as true(1) and the other 8 must be false (0).
- The values in the squares in any row must be each of 1 to 9
- The values in the squares in any column must be each of 1 to 9
- The values in the 3×3 grid must be each of 1 to 9
- The starting sudoku numbers must be in those same places in the final solution since these numbers are not changeable
Sudoku Solver Solution
Now let’s combine everything above and solve the Sudoku puzzle.

We can use the linear programming method to solve a problem as long as a problem can be formulated in terms of a linear objective function of n variables subject to a set of inequality constraints. LP can also be used in other interesting optimization applications such as cost minimization, transportation, job allocation, healthy diet planning, etc.
Recommended Reading
Reference
[1] "Sudoku – Wikipedia." [Online]. Available: https://en.wikipedia.org/wiki/Sudoku
[2] "A Sudoku Problem formulated as an LP – Pulp v1.4.6 documentation." [Online]. Available: https://www.coin-or.org/PuLP/CaseStudies/a_sudoku_problem.html