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

AI Optimization Algorithm

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