# Constraints Satisfaction Problem in AI

### Constraints Satisfaction

• One type of problem-solving strategy that works for many problems is constraint satisfaction.

• In many AI challenges, the objective is not stated clearly in the problem description.
• These categories include problems like crypto-arithmetic puzzles, design tasks requiring the creation of designs, and material where constraint satisfaction is relevant.
• Formally, a set of variables {V1, V2,,,,,,,, Vn} and a set of constraints {C1, C2,,,,,,, Cn} characterize a constraint satisfaction.

#### Thus, Constraint Satisfaction is a Two Steps Process:

• Firstly, Constraint satisfaction is discovered and propagated throughout the system.
• If there is no solution, and a search begins, a guess is made and added to the constraint.

### Constraint Satisfaction Problem in AI  Algorithm

1. Propagate available constraints

• Open each object that needs a value supplied for the solution to be complete.
• Continue until an inconsistency is found or until all objects have valid values assigned to them.
• Choose an item and make the constraints that are applied to it stronger.
• Open all objects that share any of the restrictions if the collection of constraints differs from the previous set.
• Take the chosen thing out.

2. Return the solution if the set of restrictions that you found above identifies a solution.

3. Return failure if the combination of the criteria found above defines a contradiction.

4. Assume to move forward. Continue until a solution is discovered or every option has been considered:

• constraint
• Choose an item and attempt to make its constraints stronger. It has an allocated number.
• Invoke constraint satisfaction recursively using the chosen strengthening constraint in addition to the current set of constraints.

### Constraint Satisfaction Problem in AI Example

#### Constrains Graph

{1,2,3,4}

{Red, Green, Blue{

{1≠2, 1≠3, 2≠4, 3≠4}