# AI Fundamentals: Introduction to Constraints Satisfaction Problems (CSP)

## 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.

## Solutions

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
3.
C = {“adjacent regions can’t have the same color”}

## 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.

## Backtracking

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.