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

AI Optimization Algorithm

Cesar William Alvarenga
Jan 22 Β· 4 min read
Photo made with Canva.

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.

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

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