Constraint programming is a powerful approach for modeling and solving complex combinatorial problems. It works by representing problems through variables and the constraints imposed on them, enabling a systematic exploration of the solution space to identify feasible or optimal solutions. Many decision problems are so hard that there is no rule for any a-priori “better“ approach.
Constraint programming is a powerful paradigm for solving combinatorial search problems that draws on a wide range of techniques from artificial intelligence, computer science, and operations research. Constraint programming is “programming” partly in the sense of programming in mathematical programming.
The Google OR-Tools are an open source software suite for optimization, tuned for tackling the world's toughest problems in vehicle routing, flows, integer and linear programming, and constraint programming.
In this article, I will demonstrate how to leverage constraint programming and Google's OR-Tools to solve a Sudoku puzzle efficiently.
Solving the Game
The objective of Sudoku is to complete the grid by filling in the digits 1 through 9, ensuring that each digit appears exactly once in every row, every column, and each 3x3 sub-grid.
In the Figure 1, we can see the Sudoku puzzle we will solve. However, as previously explained, by defining a constraint programming model, we can solve any Sudoku puzzle without altering the program's logic. The only modification required is to update the input variables that define the game's initial state.
In constraint programming, models are built using variables and constraints. Let’s define the decision variables.
Decision Variables
We begin by defining integer variables to represent each square in the Sudoku puzzle. These variables are constrained to take on values between 1 and 9.
# p(i,j,n): is true when the number 'n' is in the cell in the 'ith' row and the 'jth' column.
propositions = {}
for i in rows:
for j in columns:
propositions[(i, j)] = model.NewIntVar(1, 9, f'i{i}_j{j}')
Constraints
With all the decision variables of our model defined, the next step is to apply the explicit constraints of the Sudoku puzzle. This involves assigning the predefined numbers from the puzzle's initial setup to their corresponding variables.
Set the initial status of the game
# Define explicit constraints (the start status of the given game)
model.Add(propositions[(2, 1)] == 7)
model.Add(propositions[(6, 1)] == 3)
model.Add(propositions[(7, 1)] == 5)
model.Add(propositions[(9, 1)] == 6)
model.Add(propositions[(3, 2)] == 9)
model.Add(propositions[(5, 2)] == 5)
model.Add(propositions[(7, 2)] == 7)
model.Add(propositions[(2, 3)] == 5)
model.Add(propositions[(5, 3)] == 9)
model.Add(propositions[(5, 4)] == 6)
model.Add(propositions[(8, 4)] == 3)
model.Add(propositions[(9, 4)] == 4)
model.Add(propositions[(2, 5)] == 2)
model.Add(propositions[(6, 5)] == 1)
model.Add(propositions[(7, 5)] == 6)
model.Add(propositions[(4, 6)] == 4)
model.Add(propositions[(3, 7)] == 4)
model.Add(propositions[(7, 7)] == 1)
model.Add(propositions[(1, 8)] == 3)
model.Add(propositions[(6, 8)] == 5)
model.Add(propositions[(4, 9)] == 2)
model.Add(propositions[(5, 9)] == 8)
model.Add(propositions[(9, 9)] == 5)
Next, we will define the implicit constraints that stem directly from the core rules of Sudoku.
No digit can occur twice in any of the rows
for i in rows:
model.AddAllDifferent([propositions[(i, j)] for j in columns])
No digit can occur twice in any of the columns
for j in rows:
model.AddAllDifferent([propositions[(i, j)] for i in columns])
No digit can occur twice any of the 3x3 sub-grids
for i in range(n):
for j in range(n):
model.AddAllDifferent([propositions[(ii, jj)] for ii in range(1 + i * n, 1 + (i + 1) * n) for jj in
range(1 + j * n, 1 + (j + 1) * n)])
Solve the game
Constraint programming solves problems by combining systematic search with inference techniques. The search explores all possible variable-value combinations, forming a tree where the root represents the original problem.
Here the CPSolver from Google OR-Tools is invoked with the given task to solve the problem and provide the solution of our Sudoku puzzle.
solver = cp_model.CpSolver()
solver.SearchForAllSolutions(model, SolutionPrinter(propositions))
Solutions
Finally, with the help of the SolutionPrinter python class we can print the all solutions found by the solver.
solution 1
[2, 6, 1, 8, 4, 7, 5, 3, 9]
[7, 4, 5, 9, 2, 3, 6, 8, 1]
[8, 9, 3, 1, 5, 6, 4, 2, 7]
[1, 8, 7, 5, 9, 4, 3, 6, 2]
[4, 5, 9, 6, 3, 2, 7, 1, 8]
[3, 2, 6, 7, 1, 8, 9, 5, 4]
[5, 7, 8, 2, 6, 9, 1, 4, 3]
[9, 1, 4, 3, 8, 5, 2, 7, 6]
[6, 3, 2, 4, 7, 1, 8, 9, 5]
solution 2
[2, 6, 8, 7, 4, 9, 5, 3, 1]
[7, 4, 5, 1, 2, 3, 6, 8, 9]
[1, 9, 3, 5, 8, 6, 4, 2, 7]
[8, 1, 7, 9, 5, 4, 3, 6, 2]
[4, 5, 9, 6, 3, 2, 7, 1, 8]
[3, 2, 6, 8, 1, 7, 9, 5, 4]
[5, 7, 4, 2, 6, 8, 1, 9, 3]
[9, 8, 1, 3, 7, 5, 2, 4, 6]
[6, 3, 2, 4, 9, 1, 8, 7, 5]
solution 3
[2, 6, 1, 7, 4, 8, 5, 3, 9]
[7, 4, 5, 9, 2, 3, 6, 8, 1]
[8, 9, 3, 1, 5, 6, 4, 2, 7]
[1, 8, 7, 5, 9, 4, 3, 6, 2]
[4, 5, 9, 6, 3, 2, 7, 1, 8]
[3, 2, 6, 8, 1, 7, 9, 5, 4]
[5, 7, 8, 2, 6, 9, 1, 4, 3]
[9, 1, 4, 3, 8, 5, 2, 7, 6]
[6, 3, 2, 4, 7, 1, 8, 9, 5]
solution 4
[2, 6, 1, 9, 4, 8, 5, 3, 7]
[7, 4, 5, 1, 2, 3, 6, 8, 9]
[8, 9, 3, 7, 5, 6, 4, 2, 1]
[1, 8, 7, 5, 9, 4, 3, 6, 2]
[4, 5, 9, 6, 3, 2, 7, 1, 8]
[3, 2, 6, 8, 1, 7, 9, 5, 4]
[5, 7, 8, 2, 6, 9, 1, 4, 3]
[9, 1, 4, 3, 8, 5, 2, 7, 6]
[6, 3, 2, 4, 7, 1, 8, 9, 5]
solution 5
[2, 8, 6, 7, 4, 9, 5, 3, 1]
[7, 4, 5, 1, 2, 3, 6, 8, 9]
[1, 9, 3, 5, 8, 6, 4, 2, 7]
[8, 1, 7, 9, 5, 4, 3, 6, 2]
[4, 5, 9, 6, 3, 2, 7, 1, 8]
[3, 6, 2, 8, 1, 7, 9, 5, 4]
[5, 7, 4, 2, 6, 8, 1, 9, 3]
[9, 2, 1, 3, 7, 5, 8, 4, 6]
[6, 3, 8, 4, 9, 1, 2, 7, 5]
The full code is provided below:
from ortools.sat.python import cp_model
rows = [1, 2, 3, 4, 5, 6, 7, 8, 9]
columns = [1, 2, 3, 4, 5, 6, 7, 8, 9]
n = 3 # size of sub-grids
class SolutionPrinter(cp_model.CpSolverSolutionCallback):
def __init__(self, propositions):
cp_model.CpSolverSolutionCallback.__init__(self)
self.propositions_ = propositions
self.solutions_ = 0
def OnSolutionCallback(self):
self.solutions_ = self.solutions_ + 1
print("solution", self.solutions_)
for i in rows:
row_solution = []
for j in columns:
row_solution.append(self.Value(self.propositions_[(i, j)]))
print(row_solution)
print()
def main():
# Create the CP-SAT model.
model = cp_model.CpModel()
# Create the decision variables
# p(i,j,n): is true when the number 'n' is in the cell in the 'ith' row and the 'jth' column.
propositions = {}
for i in rows:
for j in columns:
propositions[(i, j)] = model.NewIntVar(1, 9, f'i{i}_j{j}')
# Define explicit constraints (the start status of the given game)
model.Add(propositions[(2, 1)] == 7)
model.Add(propositions[(6, 1)] == 3)
model.Add(propositions[(7, 1)] == 5)
model.Add(propositions[(9, 1)] == 6)
model.Add(propositions[(3, 2)] == 9)
model.Add(propositions[(5, 2)] == 5)
model.Add(propositions[(7, 2)] == 7)
model.Add(propositions[(2, 3)] == 5)
model.Add(propositions[(5, 3)] == 9)
model.Add(propositions[(5, 4)] == 6)
model.Add(propositions[(8, 4)] == 3)
model.Add(propositions[(9, 4)] == 4)
model.Add(propositions[(2, 5)] == 2)
model.Add(propositions[(6, 5)] == 1)
model.Add(propositions[(7, 5)] == 6)
model.Add(propositions[(4, 6)] == 4)
model.Add(propositions[(3, 7)] == 4)
model.Add(propositions[(7, 7)] == 1)
model.Add(propositions[(1, 8)] == 3)
model.Add(propositions[(6, 8)] == 5)
model.Add(propositions[(4, 9)] == 2)
model.Add(propositions[(5, 9)] == 8)
model.Add(propositions[(9, 9)] == 5)
# B) Constraints: no digit can occur twice in any of the rows or columns
# or in any of the 3x3 sub-grids
# no digit can occur twice in any of the rows
for i in rows:
model.AddAllDifferent([propositions[(i, j)] for j in columns])
# no digit can occur twice in any of the columns
for j in rows:
model.AddAllDifferent([propositions[(i, j)] for i in columns])
# no digit can occur twice any of the 3x3 sub-grids
for i in range(n):
for j in range(n):
model.AddAllDifferent([propositions[(ii, jj)] for ii in range(1 + i * n, 1 + (i + 1) * n) for jj in
range(1 + j * n, 1 + (j + 1) * n)])
# Declare the solver and search for all solutions and print them in the callback Class
solver = cp_model.CpSolver()
solver.SearchForAllSolutions(model, SolutionPrinter(propositions))
main()
Getting the some statistics on the solution found we can see interesting things as the walltime, usertime, deterministic_time, branches, propagations and of course the status.
Response stats: CpSolverResponse summary:
status: OPTIMAL
objective: 0
best_bound: 0
integers: 6
booleans: 8
conflicts: 0
branches: 100
propagations: 239
integer_propagations: 419
restarts: 49
lp_iterations: 0
walltime: 0.010958
usertime: 0.010958
deterministic_time: 0.00225428
gap_integral: 0
solution_fingerprint: 0x1ad791e213b2d87f
More information about these metrics can be found here.
Constraint Programming represents one if the closest approaches computer science has yet made to the Holy Grail of programming: the user states the problem, the computer solves it.
Eugene C. Freuder, Inaugural issue of the Constraints Journal, 1997
References
[2] Google OR-Tools