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

AI Optimization Algorithm

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 𝐵 = 𝐶.

Step 1: Generate All Arcs

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 𝐶 = 𝐵.

Step 2: Create the Queue

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

Step 3: Iterate Over the 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.