# How to Solve Constraint Satisfaction Problems (CSPs) Using AC-3 Algorithm in Python

## AI Optimization Algorithm

Jan 22 Β· 4 min read

The AC-3 algorithm simplifies a constraint satisfaction problem using the constraints to prune out values from the variables domain.

In this article, we will see how the AC-3 algorithm works and the implementation in Python.

# How It Works

We can represent the AC-3 algorithm in 3 steps:

1. Get all the constraints and turn each one into two arcs. For example:
π΄ > π΅ becomes π΄ > π΅ and π΅ < π΄.
2. Add all the arcs to a queue.
3. Repeat until the queue is empty:
3.1. Take the first arc (π₯, π¦), off the queue (dequeue).
3.2. For every value in the π₯ domain, there must be some value of the π¦ domain.
3.3. Make π₯ arc consistent with π¦. To do so, remove values from π₯ domain for which there is no possible corresponding value for π¦ domain.
3.4. If the π₯ domain has changed, add all arcs of the form (π, π₯) to the queue (enqueue). Here π is another variable different from π¦ that has a relation to π₯.

# Example

Letβs take this example, where we have three variables π΄, π΅, and πΆ and the constraints: π΄ > π΅ and π΅ = πΆ.

The first thing to do is to work out all our arcs. We take the constraint π΄ > π΅ and generate π΄ > π΅ and π΅οΉ€π΄. With the constraint π΅ = πΆ we will have π΅ = πΆ and πΆ = π΅.

We now take all generated arcs and add them to our queue.

First, we will take the first item in the queue (π΄ > π΅) and remove it, and we are going through all the values of the π΄ domain. For each value of π΄, we will compare it with the values of π΅. If there are no values in π΅ for the value of π΄, we remove this value from π΄. As the domain of π΄ has changed, we have to look at the right side of all the arcs. Whether there are variables for π΄ and that arc is not already in the queue. As we can see, this is not the case here.

On the second iteration, we take the first item in the queue (π΅οΉ€π΄). After removing all the inconsistent values in the π΅ domain, we notice that it has been modified. Looking at all the arcs and checking whether there is the variable π΅ on the right side, we can see that the arc π΄ > π΅ is not in the queue, so we have to add it again to the queue.

Now, we will keep doing that until the queue is empty. In the end, we will have the following state:

# Solution in Python

Here is the implementation of the AC-3 algorithm (with the previous example) in Python.

# Conclusion

The time complexity of AC-3 is π(ππΉΒ³), where π is the number of constraints and πΉ is the size of the maximum domain in a problem.

AC-3 is an algorithm with non-optimal worst-case complexity although, it is simple, efficient in practice, and widely used.

## The Startup

Get smarter at building your thing. Join The Startupβs +725K followers.

Written by

## Cesar William Alvarenga

Software Engineer

## The Startup

Get smarter at building your thing. Follow to join The Startupβs +8 million monthly readers & +725K followers.

Written by

## Cesar William Alvarenga

Software Engineer

## The Startup

Get smarter at building your thing. Follow to join The Startupβs +8 million monthly readers & +725K followers.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and youβll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer β welcome home. Itβs easy and free to post your thinking on any topic. Write on Medium

Get the Medium app