Analytics Vidhya
Published in

Analytics Vidhya

AI Fundamentals: Introduction to Constraints Satisfaction Problems (CSP)

Photo by Ondrej Machart on Unsplash

What is a Constraints Satisfaction Problem?

Constraint Satisfaction Problems (CSP) represents a class of problems where there are some restrictions between objects within that problem.


Like every problem, also CSP can have solutions; but we need to define the “notion of solution”. So, let’s start from states:

CSP: An Example 🦘

If you didn’t know before, there are these 7 regions in Australia

You have to color each region of Australia using three colors {red, blue green} so that no neighboring territory has the same color.

Ok, it can be even too simple at first glance but let’s define the CSP:
1. V = {WA, NT, Q, NSW, V, SA, T}
2. D = {green, red, blue}, in this problem all variables have the same domain
C = {“adjacent regions can’t have the same color”}

Constraint graph

The Constraint Graph
We. Now.

Generate-and-Test Algorithms

Have you ever heard of a brute force hacking attack? Here, it’s the same principle. This strategy provides to generate a complete assignment to each variable, check if that assignment is a solution, checking if each constraint is satisfied. If so, this strategy has found a solution, if not, start again. This is not the best strategy because there is a lot of useless work. Let’s think of a smarter solution instead.


This strategy involves checking the constraint after each assignment on a single variable — and not after each variable is assigned like the Generate-and-Test strategy.
So, if some constraints are violated, this strategy backtracks to previous choices (undoing the assignment) and tries another assignment.

When the algorithm found no solution:



Analytics Vidhya is a community of Analytics and Data Science professionals. We are building the next-gen data science ecosystem

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store