# Python introduction to Google OR-Tools

Operations research (

OR) is a sub-field of applied mathematics that tries to findoptimalor near-optimal solutions to complexdecision-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
```

to get the latest version.

## 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
]
model.AddAllDifferent(one_cell)
```

- Initial values using
`model.Add`

```
for i in line:
for j in line:
if initial_grid[i][j]:
model.Add(grid[(i, j)] == 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:

## Leave a comment