# Python introduction to Google OR-Tools

Operations research (OR) is a sub-field of applied mathematics that tries to find optimal or near-optimal solutions to complex decision-making problems.

OR-Tools is an open source software suite for optimization developed by Google, tuned for tackling the world’s toughest problems in vehicle routing, flows, integer and linear programming, and constraint programming.

# Sudoku

We will implement a simple sudoku solver with the python library of OR-Tools.

Note: I will use the version `7.1.6720` of the package.

## Installation

The package is on PyPI so just run:

``````pip install ortools
``````

## Input

We will use a 9x9 list of lists to create the initial grid:

``````initial_grid = [
[0, 6, 0, 0, 5, 0, 0, 2, 0],
[0, 0, 0, 3, 0, 0, 0, 9, 0],
[7, 0, 0, 6, 0, 0, 0, 1, 0],
[0, 0, 6, 0, 3, 0, 4, 0, 0],
[0, 0, 4, 0, 7, 0, 1, 0, 0],
[0, 0, 5, 0, 9, 0, 8, 0, 0],
[0, 4, 0, 0, 0, 1, 0, 0, 6],
[0, 3, 0, 0, 0, 8, 0, 0, 0],
[0, 2, 0, 0, 4, 0, 0, 5, 0]
]
``````

We will mark the blank positions with a 0.

## Initial variables

We first declare the domain variables for our problem.

``````cell_size = 3
line_size = cell_size**2
line = range(line_size)
cell = range(cell_size)
``````

## ORTools variables

Create the `CpModel` object.

``````from ortools.sat.python import cp_model
model = cp_model.CpModel()
``````

And the variables for the model, for each position we create an IntVar between 1 and 9.

``````# 1. Using dict comprehension
grid = {
(i, j): model.NewIntVar(1, line_size, 'grid %i %i' % (i, j))
for i in line
for j in line
}

# 2. Using nested for loops
grid = {}
for i in line:
for j in line:
grid[i, j] = model.NewIntVar(1, line_size, 'grid %i %i' % (i, j))
``````

The `model.NewIntVar(lb, ub, name)` method takes a [lower bound, upper bound] and a name. The name doesn’t have to be unique and can be an empty string.

## Constraints

For the main constraints we will use the `model.AddAllDifferent` method that takes an iterable of variables and forces them to be all different.

• AllDifferent on rows
``````for i in line:
model.AddAllDifferent([grid[(i, j)] for j in line])
``````
• AllDifferent on columns
``````for j in line:
model.AddAllDifferent([grid[(i, j)] for i in line])
``````
• AllDifferent on cells
``````for i in cell:
for j in cell:
one_cell = [
grid[(i * cell_size + di,
j * cell_size + dj)]
for di in cell
for dj in cell
]
``````
• Initial values using `model.Add`
``````for i in line:
for j in line:
if initial_grid[i][j]:
``````

## Solving the model

• Create the solver object.
``````solver = cp_model.CpSolver()
``````
• Call the `Solve` method passing the model.
``````status = solver.Solve(model)
``````
• Check the status and print the solution.
``````# Other status values are INFEASIBLE, OPTIMAL and MODEL_INVALID
if status == cp_model.FEASIBLE:
for i in line:
print([int(solver.Value(grid[(i, j)])) for j in line])
``````

The `solver.Value(variable)` method takes a model variable and returns its value in the found solution.

You can find the whole script on my github but you can also view all the official examples at:

Tags:

Updated: