Python introduction to Google OR-Tools

2 minute read

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

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