AD3311 - ARTIFICIAL INTELLIGENCE LABORATORY
Ex: 4 Constraint Programming
Aim: To solve constraint satisfaction problem using python
Description:
Constraint programming is an example of the declarative programming paradigm, as opposed to the
usual imperative paradigm that we use most of the time. Most programming paradigms can be
classified as a member of either the imperative or declarative paradigm group.
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.
Procedure
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:
Program
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']))
Output:
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
Result : Thus the constraint satisfaction problem is resolved successfully.
