Constraints Programming with Python

Happy new year 2024 to all readers of Playful Python! Hope this new year brings with it a lot of new python learning.

And what better way to bring in the new year than to write a fun little program? A few days ago, this tweet from Rodrigo landed on my X stream.

The tweet says to not use Python... but we are going to use python to solve this problem 😎

Problem Statement

This problem contains a number of digits, represented by letters. Each letter represents a unique digit, so no duplicates. None of the numbers start with leading zeros, so S and M cannot be zero.

Finally, the problem states that SEND + MORE = MONEY

Such puzzles are called cryptarithmic puzzles. Let's see how we can use Python to solve them.

Brute Force Approach

One simple approach we can take is the brute force approach.

There are eight letters - S, E, N, D, M, O, R, Y and each letter can take values between 0 and 9, except S and M which start with 1.

We could just loop through all the possible values and find the one that matches the conditions.

from itertools import product, combinations

def all_unique(variables):
    for a, b in combinations(variables, 2):
        if a == b:
            return False
    return True

def match_total(s, e, n, d, m, o, r, y):
    send = 1000*s + 100*e + 10*n + d
    more = 1000*m + 100*o + 10*r + e
    money = 10000*m + 1000*o + 100*n + 10*e + y
    return send + more == money


for variables in product(range(10), repeat=8):
    s, e, n, d, m, o, r, y = variables
    if s == 0 or m == 0:
        continue
    if all_unique(variables) and match_total(*variables):
        print(f"{s}{e}{n}{d} + {m}{o}{r}{e} = {m}{o}{n}{e}{y}")
        break
else:
        print("No solution")

If you run this code, you will get the right solution, but it takes a long, LONG time to run.

Constraint Programming

Instead of the brute force approach, we can take an alternative route of using constraint programming algorithms.

Constraint programming is used when you have a large solution space, but there are constraints that can narrow down the solution space considerably. A classic example is Sudoku, where you have many numbers to find out, but the various constraints are such that most people can easily solve them manually.

Cryptarithmetic puzzles also fall into the same category.

We are coding in Python, so we don't actually need to implement the algorithms ourselves. As usual, there is a library for it. We are going to use the python-constraint library. Read more about it in the link below.

GitHub - python-constraint/python-constraint: Constraint Solving Problem resolver for Python

Constraint Solving Problem resolver for Python. Contribute to python-constraint/python-constraint development by creating an account on GitHub.

GitHubpython-constraint

To get started, install the package

> pip install python-constraint

Now we can start writing the code. To get started, we import constraint and then create a Problem object. (Note that the module to import is called constraint while the python package is called python-constraint)

import constraint

question = constraint.Problem()

Next, we define our variables and the range of possible values for each one. We can define each variable individually, or together if multiple variables have the same range.

question.addVariables("SM", range(1, 10))
question.addVariables("ENDORY", range(0, 10))

Now, we add the constraints. The first constraint is that every value should be unique. The module has an inbuilt constraint to represent this, so we use that

question.addConstraint(constraint.AllDifferentConstraint())

Finally, SEND + MORE = MONEY. We define this constraint using our own function and tell the module which variables are used in this constraint.

def total(s, e, n, d, m, o, r, y):
    send = 1000*s + 100*e + 10*n + d
    more = 1000*m + 100*o + 10*r + e
    money = 10000*m + 1000*o + 100*n + 10*e + y
    return send + more == money

question.addConstraint(total, "SENDMORY")

Now that all the constraints are defined, we can run the solver

answers = question.getSolutions()

Here is the whole code

import constraint

question = constraint.Problem()
question.addVariables("SM", range(1, 10))
question.addVariables("ENDORY", range(0, 10))
question.addConstraint(constraint.AllDifferentConstraint())

def total(s, e, n, d, m, o, r, y):
    send = 1000*s + 100*e + 10*n + d
    more = 1000*m + 100*o + 10*r + e
    money = 10000*m + 1000*o + 100*n + 10*e + y
    return send + more == money

question.addConstraint(total, "SENDMORY")

answers = question.getSolutions()
print(answers)

Run this code and you will get the answer. You will notice that it runs much faster than the brute force approach, but it still takes a few seconds.

Granular Constraints

We can further speed up the code by adding in more constraints. We know that SEND + MORE = MONEY. This tells us that the units place of D + E should equal Y. Similarly, we can come up with constraints for each of the individual digit additions.

def unit(value):
    return value % 10

def carry(value):
    return value // 10

question.addConstraint(lambda d, e, y: unit(d + e) == y, "DEY")
question.addConstraint(lambda d, e, n, r: unit(carry(d + e) + n + r) == e, "DENR")
question.addConstraint(lambda d, e, n, r, o: unit(carry(carry(d + e) + n + r) + e + o) == n, "DENRO")

Run the code with these additional constraints and we will get the answer almost instantly.

Summary

Constraint programming is commonly used to solve logic puzzles like Sudoku or the cryptarithmetic problem above. But these algorithms also have a lot of practical applications, especially in the field of operations research.

Consider an example where an airline has pilots in different cities and wants to assign pilots to various flights. There may be constraints on how many hours a pilot can fly continuously. Further only pilots that are present in a city can be scheduled for flights departing from that city. When a pilot flies a flight they are now in a different city and their next flight has to be from the new city they are in. Finally, pilots would like to return to their home city for a break every week.

How do we assign the pilots to the flights to meet all these conditions? This is a classical constraint programming problem and python has many tools that make it easy to implement such applications.