Introduction
The first thing we have to understand while dealing with constraint programming is that the way of thinking is very different from our usual way of thinking when we sit down to write code.
Constraint programming is an example of the declarative programming paradigm, as opposed to the usual imperative paradigm that we use most of the time.
What is a programming paradigm?
A paradigm means "an example" or "a pattern" of something. A programming paradigm is often described as a "way of thinking" or "way of programming". The most common examples including Procedural Programming (e.g. C), Object-Oriented Programming (e.g. Java) and Functional Programming (e.g. Haskell).
Most programming paradigms can be classified as a member of either the imperative or declarative paradigm group.
What is the difference between imperative and declarative programming?
- Imperative programming, simply put, is based on the developer describing the solution/algorithm for achieving a goal (some kind of result). This happens by changing the program state through assignment statements, while executing instructions step-by-step. Therefore it makes a huge difference in what order the instructions are written.
- Declarative programming does the opposite - we don't write the steps on how to achieve a goal, we describe the goal, and the computer gives us a solution. A common example you should be familiar with is SQL. Do you tell the computer how to give you the results you need? No, you describe what you need - you need the values from some column, from some table, where some conditions are met.
Installing the python-constraint Module
In this article we'll be working with a module called python-constraint (Note: there's a module called "constraint" for Python, that is not what we want), which aims to bring the constraint programming idea to Python.
To install this module, open the terminal and run:
$ pip install python-constraint
Basics of Using python-constraint
This is the generalized skeleton of programs written using this module (Note: we use import constraint and not import python-constraint)
- import
constraint - define a variable as our problem
- add variables and their respective intervals to our problem
- add built-in/custom constraints to our problem
- fetch the solutions
- go through the solutions to find the ones we need
As previously mentioned, constraint programming is a form of declarative programming. The order of statements doesn't matter, as long as everything is there in the end. It's usually used to solve problems like this:
Example A
Find all (x,y) where x ∈ {1,2,3} and 0 <= y < 10, and x + y >= 5
If we look at this sentence, we can see several conditions (let's call them constraints) that x and y have to meet.
For example, x is "constrained" to the values 1,2,3, y has to be less than 10 and their sum has to be greater than or equal to 5. This is done in a few lines of code and in a few minutes using constraint programming.
Looking at the problem above you probably thought "So what? I can do this with 2 for loops and half a cup of coffee in Python in less than 10 minutes".
You're absolutely right, though through this example we can get an idea of what constraint programming looks like:
import constraint
problem = constraint.Problem()
problem.addVariable('x', [1,2,3])
problem.addVariable('y', range(10))
def our_constraint(x, y):
if x + y >= 5:
return True
problem.addConstraint(our_constraint, ['x','y'])
solutions = problem.getSolutions()
# Easier way to print and see all solutions
# for solution in solutions:
# print(solution)
# Prettier way to print and see all solutions
length = len(solutions)
print("(x,y) ∈ {", end="")
for index, solution in enumerate(solutions):
if index == length - 1:
print("({},{})".format(solution['x'], solution['y']), end="")
else:
print("({},{}),".format(solution['x'], solution['y']), end="")
print("}")
Output:
(x,y) ∈ {(3,9),(3,8),(3,7),(3,6),(3,5),(3,4),(3,3),(3,2),(2,9),(2,8),(2,7),(2,6),(2,5),(2,4),(2,3),(1,9),(1,8),(1,7),(1,6),(1,5),(1,4)}
Let's walk through this program step by step. We had two variables, x and y. We've added them to our problem with their respective acceptable ranges.
Those two lines mean the following:
I'm adding a variable x that can only have values [1,2,3], and a variable y that can only have values [0,1,2,..,9]
Next we define our custom constraint (that is, x + y >= 5). Constraint methods are supposed to return True if a combination of variable values is acceptable, and None if it isn't.
In our our_constraint() method, we say "The only acceptable situation is when x + y >= 5, otherwise don't include those values of (x,y) in the final solutions."
After defining our constraint, we have to add it to our problem. The structure of the .addConstraint() method is:
addConstraint(which_constraint, list_of_variable_order)
Note: in our case, it doesn't matter if we write [x,y] or [y,x] as our second parameter, but the order does matter in most cases.
After that, we fetch the solutions with problem.getSolutions() (returns a list of all combinations of variable values that satisfy all the conditions) and we iterate through them.
Note: If, for example, we wanted to fetch only combinations where x /= y, we'd add a built-in constraint before fetching the solutions:
problem.addConstraint(constraint.AllDifferentConstraint())
You can find the list of all built-in constraints here. That's almost everything you need to know to be able to do any task of this type.
Warm-Up Examples
Example B
Here's a type of problem constraint programming is fun to use on, called crypt-arithmetic puzzles. In the following form of crypt-arithmetic puzzles, each character represents a different digit (the leading characters can't be 0):
TWO + TWO = FOUR
Think about how you'd solve this using regular Python. In fact, I encourage you to look up the solution for this problem that uses imperative programming.
It should also give you all the knowledge you need to solve Example D on your own.
Keep in mind that 'T' and 'F' can't be zero since they're the leading characters, i.e. the first digit in a number.
import constraint
problem = constraint.Problem()
# We're using .addVariables() this time since we're adding
# multiple variables that have the same interval.
# Since Strings are arrays of characters we can write
# "TF" instead of ['T','F'].
problem.addVariables("TF", range(1, 10))
problem.addVariables("WOUR", range(10))
# Telling Python that we need TWO + TWO = FOUR
def sum_constraint(t, w, o, f, u, r):
if 2*(t*100 + w*10 + o) == f*1000 + o*100 + u*10 + r:
return True
# Adding our custom constraint. The
# order of variables is important!
problem.addConstraint(sum_constraint, "TWOFUR")
# All the characters must represent different digits,
# there's a built-in constraint for that
problem.addConstraint(constraint.AllDifferentConstraint())
solutions = problem.getSolutions()
print("Number of solutions found: {}\n".format(len(solutions)))
# .getSolutions() returns a dictionary
for s in solutions:
print("T = {}, W = {}, O = {}, F = {}, U = {}, R = {}"
.format(s['T'], s['W'], s['O'], s['F'], s['U'], s['R']))
Running this piece of code, we're greeted with the possible solutions:
Number of solutions found: 7
T = 7, W = 6, O = 5, F = 1, U = 3, R = 0
T = 7, W = 3, O = 4, F = 1, U = 6, R = 8
T = 8, W = 6, O = 7, F = 1, U = 3, R = 4
T = 8, W = 4, O = 6, F = 1, U = 9, R = 2
T = 8, W = 3, O = 6, F = 1, U = 7, R = 2
T = 9, W = 2, O = 8, F = 1, U = 5, R = 6
T = 9, W = 3, O = 8, F = 1, U = 7, R = 6
Example C
You recently got a job as a cashier. You're trying to convince your friend that it's hard work, there are just SO many ways to give someone their change back! Your "friend" shakes his head, obviously not believing you. He says "It can't be that bad. How many ways can there POSSIBLY be to give someone their change back, for like 60 cents?".
Your response is, of course, to sit and quickly write a program that would prove your point. You have a decent amount of pennies (1 cent), nickels (5 cents), dimes (10 cents) and quarters (25 cents), and a lot of kinda suspicious coins worth 3 cents each. Calculate in how many ways you can return change for 60 cents.
Note: The order in which our result is printed isn't necessarily the same as the order in which we've added the variables. That is, if the result is (a,b,c,d,e) we don't know whether we have a of 1 cent coins, b of 3 cent coins, etc.
So we should explicitly print the variable and its value. One consequence of this is that we can't use the built-in .ExactSumConstraint() in its two-parameter form, ExactSumConstraint(50,[1,3,5,10,20]).
The second parameter here is the "weight" of each variable (how many times it should be multiplied), and we have no guarantee which of our variables will have what weight.
It's a common mistake to assume the weights will be allocated to the variables in the order in which the variables were added, instead we use the three-parameter form of this built-in constraint in the code below:
Check out our hands-on, practical guide to learning Git, with best-practices, industry-accepted standards, and included cheat sheet. Stop Googling Git commands and actually learn it!
import constraint
problem = constraint.Problem()
# The maximum amount of each coin type can't be more than 60
# (coin_value*num_of_coints) <= 60
problem.addVariable("1 cent", range(61))
problem.addVariable("3 cent", range(21))
problem.addVariable("5 cent", range(13))
problem.addVariable("10 cent", range(7))
problem.addVariable("20 cent", range(4))
problem.addConstraint(
constraint.ExactSumConstraint(60,[1,3,5,10,20]),
["1 cent", "3 cent", "5 cent","10 cent", "20 cent"]
)
# Where we explicitly give the order in which the weights should be allocated
# We could've used a custom constraint instead, BUT in this case the program will
# run slightly slower - this is because built-in functions are optimized and
# they find the solution more quickly
# def custom_constraint(a, b, c, d, e):
# if a + 3*b + 5*c + 10*d + 20*e == 60:
# return True
# problem.addConstraint(o, ["1 cent", "3 cent", "5 cent","10 cent", "20 cent"])
# A function that prints out the amount of each coin
# in every acceptable combination
def print_solutions(solutions):
for s in sols:
print("---")
print("""
1 cent: {0:d}
3 cent: {1:d}
5 cent: {2:d}
10 cent: {3:d}
20 cent: {4:d}""".format(s["1 cent"], s["3 cent"], s["5 cent"], s["10 cent"], s["20 cent"]))
# If we wanted to we could check whether the sum was really 60
# print("Total:", s["1 cent"] + s["3 cent"]*3 + s["5 cent"]*5 + s["10 cent"]*10 + s["20 cent"]*20)
# print("---")
solutions = problem.getSolutions()
#print_solutions(solutions)
print("Total number of ways: {}".format(len(solutions)))
Running this piece of code will yield:
Total number of ways: 535
Example D
CRASH + ERROR + REBOOT = HACKER
Example B and D are nearly identical when using constraints, just a few variables up and down and more verbose constraints. That's one good thing about constraint programming - good scalability, at least when time spent coding is concerned. There is only one solution to this puzzle and it is A=3 B=7 C=8 E=2 H=6 K=0 O=1 R=5 S=9 T=4.
Both of these types of tasks (especially crypt-arithmetic) are used more for fun and for easy demonstration of how constraint programming works, but there are certain situations in which constraint programming has practical value.
We can calculate the minimal number of broadcasting stations to cover a certain area, or find out how to set up traffic lights so that the flow of traffic is optimal. In general terms - constraints are used where there are a lot of possible combinations.
These examples are too complex for the scope of this article, but serve to show that constraint programming can have uses in the real world.
Harder Examples
Example E
You wish to pack chocolates for your mother. Luckily you work in a chocolate factory that has a lot of leftover chocolate. You have a few chocolate types at your disposal.
Your goal is to bring her the sweetest chocolate possible, that you can pack in your bag and sneak through security, and that wouldn't pass a certain net value for which you'd go to prison if you got caught.
Security most likely won't get suspicious if you bring less than 3kg. You can fit 1 dm^3 of chocolate in your bag. You won't go to jail if you steal less than $300 worth of chocolate.
| Chocolate Name | Weight (g) | Dimensions (cm) | Sweetness | Value ($) |
|---|---|---|---|---|
| Chocolate A | 100 | 8 × 2.5 × 0.5 | 20 | 8 |
| Chocolate B | 45 | 7 × 2 × 0.5 | 16 | 6.8 |
| Chocolate C | 10 | 3 × 2 × 0.5 | 9 | 4 |
| Chocolate D | 25 | 3 × 3 × 0.5 | 7 | 3 |
Now let's roll up our sleeves and get started. It shouldn't be too difficult if you've understood the previous examples.
We'll first figure out how much of each chocolate we can have if we ONLY brought that type, so we can have the upper bound of our intervals. For example, for Chocolate A, based on weight we can bring at most 30 bars, based on value we can bring 37 at most, and based on volume we can bring 100.
The smallest of these numbers is 30, and that's the maximum number of Chocolate A we can bring. The same steps give us the maximum amount of the rest, B -> 44, C -> 75, D -> 100.
import constraint
problem = constraint.Problem()
problem.addVariable('A', range(31))
problem.addVariable('B', range(45))
problem.addVariable('C', range(76))
problem.addVariable('D', range(101))
# We have 3kg = 3,000g available
def weight_constraint(a, b, c, d):
if (a*100 + b*45 + c*10 + d*25) <= 3000:
return True
# We have 1dm^3 = 1,000cm^3 available
def volume_constraint(a, b, c, d):
if (a*8*2.5*0.5 + b*6*2*0.5 * c*2*2*0.5 + d*3*3*0.5) <= 1000:
return True
# We can't exceed $300
def value_constraint(a, b, c, d):
if (a*8 + b*6.8 + c*4 + d*3) < 300:
return True
problem.addConstraint(weight_constraint, "ABCD")
problem.addConstraint(volume_constraint, "ABCD")
problem.addConstraint(value_constraint, "ABCD")
maximum_sweetness = 0
solution_found = {}
solutions = problem.getSolutions()
for s in solutions:
current_sweetness = s['A']*10 + s['B']*8 + s['C']*4.5 + s['D']*3.5
if current_sweetness > maximum_sweetness:
maximum_sweetness = current_sweetness
solution_found = s
print("""
The maximum sweetness we can bring is: {}
We'll bring:
{} A Chocolates,
{} B Chocolates,
{} C Chocolates,
{} D Chocolates
""".format(maximum_sweetness, solution_found['A'], solution_found['B'], solution_found['C'], solution_found['D']))
Running this piece of code will yield:
The maximum sweetness we can bring is: 365.0
We'll bring:
27 A Chocolates,
2 B Chocolates,
16 C Chocolates,
2 D Chocolates
Note: We can store all relevant information for each chocolate type in a dictionary, e.g. weight_dictionary = {'A' : 100, 'B' : 45, 'C' : 10, 'D' : 25}, and accessing values that way, instead of hardcoding them in functions. However, for the sake of readability, code length and focus on things more important for this tutorial, I prefer to hardcode in the constraint functions themselves.
Note: You probably noticed that it took a while for this result to be computed, this is a drawback of constraint programming.
Example F
Now for something more fun - let's make a sudoku (classic 9x9) solver. We'll read the puzzle from a JSON file and find all the solutions for that particular puzzle (assuming that the puzzle has a solution).
If you forgot the rules for solving sudoku:
- Cells can have values 1 - 9
- All cells in the same row must have different values
- All cells in the same column must have different values
- All cells in a 3x3 square (nine in total) must have different values
One of the issues in this program is - how do we store the values? We can't just add a matrix as a variable to our problem and have Python magically figure out what we want.
We're going to use a system where we'll treat numbers like variable names (that's allowed), and pretend that we have a matrix. The indices start from (1,1) instead of the usual (0,0). Using that we'll access elements of the board in a way that we're used to.
Next, we need to do the easy part of telling Python that all those cells can have values between 1 and 9.
Then we note that cells in the same row have the same first index, e.g. (1,x) for the first row. We can easily iterate through all rows and say that all the cell have to contain different values. Same goes for the columns. The rest is more easily understood when looking at the code.
Let's take a look at an example JSON file:
[[0, 9, 0, 7, 0, 0, 8, 6, 0],
[0, 3, 1, 0, 0, 5, 0, 2, 0],
[8, 0, 6, 0, 0, 0, 0, 0, 0],
[0, 0, 7, 0, 5, 0, 0, 0, 6],
[0, 0, 0, 3, 0, 7, 0, 0, 0],
[5, 0, 0, 0, 1, 0, 7, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 0, 9],
[0, 2, 0, 6, 0, 0, 0, 5, 0],
[0, 5, 4, 0, 0, 8, 0, 7, 0]]
# 1 - - - - - - - - -
# 2 - - - - - - - - -
# 3 - - - - - - - - -
# 4 - - - - - - - - -
# 5 - - - - - - - - -
# 6 - - - - - - - - -
# 7 - - - - - - - - -
# 8 - - - - - - - - -
# 9 - - - - - - - - -
# 1 2 3 4 5 6 7 8 9
import constraint
import json
problem = constraint.Problem()
# We're letting VARIABLES 11 through 99 have an interval of [1..9]
for i in range(1, 10):
problem.addVariables(range(i * 10 + 1, i * 10 + 10), range(1, 10))
# We're adding the constraint that all values in a row must be different
# 11 through 19 must be different, 21 through 29 must be all different,...
for i in range(1, 10):
problem.addConstraint(constraint.AllDifferentConstraint(), range(i * 10 + 1, i * 10 + 10))
# Also all values in a column must be different
# 11,21,31...91 must be different, also 12,22,32...92 must be different,...
for i in range(1, 10):
problem.addConstraint(constraint.AllDifferentConstraint(), range(10 + i, 100 + i, 10))
# The last rule in a sudoku 9x9 puzzle is that those nine 3x3 squares must have all different values,
# we start off by noting that each square "starts" at row indices 1, 4, 7
for i in [1,4,7]:
# Then we note that it's the same for columns, the squares start at indices 1, 4, 7 as well
# basically one square starts at 11, the other at 14, another at 41, etc
for j in [1,4,7]:
square = [10*i+j,10*i+j+1,10*i+j+2,10*(i+1)+j,10*(i+1)+j+1,10*(i+1)+j+2,10*(i+2)+j,10*(i+2)+j+1,10*(i+2)+j+2]
# As an example, for i = 1 and j = 1 (bottom left square), the cells 11,12,13,
# 21,22,23, 31,32,33 have to be all different
problem.addConstraint(constraint.AllDifferentConstraint(), square)
file_name = input("Enter the name of the .json file containing the sudoku puzzle: ")
try:
f = open(file_name, "r")
board = json.load(f)
f.close()
except IOError:
print ("Couldn't open file.")
sys.exit()
# We're adding a constraint for each number on the board (0 is an "empty" cell),
# Since they're already solved, we don't need to solve them
for i in range(9):
for j in range(9):
if board[i][j] != 0:
def c(variable_value, value_in_table = board[i][j]):
if variable_value == value_in_table:
return True
# Basically we're making sure that our program doesn't change the values already on the board
# By telling it that the values NEED to equal the corresponding ones at the base board
problem.addConstraint(c, [((i+1)*10 + (j+1))])
solutions = problem.getSolutions()
for s in solutions:
print("==================")
for i in range(1,10):
print("|", end='')
for j in range(1,10):
if j%3 == 0:
print(str(s[i*10+j])+" | ", end='')
else:
print(str(s[i*10+j]), end='')
print("")
if i%3 == 0 and i!=9:
print("------------------")
print("==================")
if len(solutions) == 0:
print("No solutions found.")
Output (when we use our example JSON file as input):
==================
|295 | 743 | 861 |
|431 | 865 | 927 |
|876 | 192 | 345 |
------------------
|387 | 459 | 216 |
|612 | 387 | 594 |
|549 | 216 | 783 |
------------------
|768 | 524 | 139 |
|923 | 671 | 458 |
|154 | 938 | 672 |
==================
==================
|295 | 743 | 861 |
|431 | 865 | 927 |
|876 | 192 | 345 |
------------------
|387 | 459 | 216 |
|612 | 387 | 594 |
|549 | 216 | 738 |
------------------
|763 | 524 | 189 |
|928 | 671 | 453 |
|154 | 938 | 672 |
==================
==================
|295 | 743 | 861 |
|431 | 865 | 927 |
|876 | 192 | 543 |
------------------
|387 | 459 | 216 |
|612 | 387 | 495 |
|549 | 216 | 738 |
------------------
|763 | 524 | 189 |
|928 | 671 | 354 |
|154 | 938 | 672 |
==================
Note: It's very easy to overlook the part of the code that makes sure we don't touch the values already in the puzzle.
If we tried to run the code without that part, the program would try to come up with ALL SUDOKU PUZZLES IMAGINABLE. Which might as well be an endless loop.
Conclusion and Drawbacks
As fun and different as constraint programming is, it certainly has its drawbacks. Every problem solved using constraint programming can be written in imperative style with an equal or (as in most cases) better runtime.
It's only natural that the developer understands the problem better than he can describe it to python-constraint. A very important note to make is that constraint programming can, in some situations, save hours and hours of development time in exchange for slightly worse runtime.
I recently had a real life example of this. A friend of mine, someone who only learned of Python's existence a few months before, needed to solve a problem for a physical chemistry research project she was working on.
That friend needed the following problem solved:
Generate all combinations (that have a length equal to the number of keys) of values stored in a dictionary (the order of output doesn't matter). The dictionary is {String : List_of_Strings}. In such a way that every combination has exactly one value from the List_of_Strings of a key.
You don't know the number of keys in the dictionary in advance, nor do you know how long a List_of_String is, every List_of_String can be of different length. I.e. the dictionary is dynamically generated via user input.
Example input: dictionary = {"A" : [1,2], "B" -> [4], "C" -> [5,6,7], "D" -> [8,9]}
Example output: (1,4,5,8), (1,4,5,8), (1,4,6,8), (1,4,6,9), (1,4,7,8)....
Try and think how you would solve this using imperative programming.
I couldn't even come up with an idea of a good solution imperatively. At least not in the 5 minutes it took me to solve her problem in constraint programming, in literally a few lines of code.
import constraint
# input example
generated_dictionary = {'A' : [1,2], 'B' : [4], 'C' : [5,6,7], 'D' : [8,9]}
problem = constraint.Problem()
for key, value in generated_dictionary.items():
problem.addVariable(key, value)
solutions = problem.getSolutions()
for solution in solutions:
print(solution)
That's it. We just didn't add any constraints and the program generated all acceptable combinations for us. In her case, the minimal difference in runtime of this program doesn't remotely matter as much as how quickly it was written and how readable it is.
One more thing to note is that python-constraint can do more than just test whether a combination fits all constraints mindlessly.
There are backtracking (and recursive backtracking) capabilities implemented, as well as problem solvers based on the minimum conflicts theory. These can be passed as an argument to the .Problem() method, e.g .Problem(BacktrackingSolver), the rest is done in the same way as in the examples above.
List of Built-in Constraints
| Constraint Name | Constraint Description |
|---|---|
| AllDifferentConstraint | Enforces that values of all given variables are different |
| AllEqualConstraint | Enforces that values of all given variables are equal |
| MaxSumConstraint | Enforces that values of given variables sum up to a given amount |
| ExactSumConstraint | Enforces that values of given variables sum exactly to a given amount |
| MinSumConstraint | Constraint enforcing that values of given variables sum at least to a given amount |
| InSetConstraint | Constraint enforcing that values of given variables are present in the given set |
| NotInSetConstraint | Constraint enforcing that values of given variables are not present in the given set |
| SomeInSetConstraint | Constraint enforcing that at least some of the values of given variables must be present in a given set |
| SomeNotInSetConstraint | Constraint enforcing that at least some of the values of given variables must not be present in a given set |
When using constraints that can take a list of multipliers as a parameter (Like ExactSum or MinSum) take care to explicitly say the order or variables if necessary, like we did in Example E
Conclusion
Constraint programming is amazing as far as readability and ease of developing certain programs is concerned, but does so at the cost of runtime. It's up to the developer to decide which is more important to him/her for a particular problem.
