PYTHON
Free Section Starter Challenge
30 min
4. Constraint Satisfaction Problems & The AC-3 Algorithm
Overview: Enforce pairwise arc consistency on variable domains to drastically reduce search spaces.
Concept & Syntax Guide
A Constraint Satisfaction Problem (CSP) consists of variables $X_i$, domains $D_i$, and binary constraints $C_{ij}$. An arc $(X_i, X_j)$ is arc-consistent if for every value $x \in D_i$, there exists an allowable $y \in D_j$. The AC-3 algorithm repeatedly eliminates inconsistent domain values until convergence.
Hands-On Practice Exercise
Run AC-3 Arc Consistency Reductions
Given constraints X < Y and Y < Z with initial domains {1,2,3}, compute consistent domains.
Target Output:
AC-3 consistent domains: {'X': [1], 'Y': [2], 'Z': [3]}
Need a hint? Click here to reveal
Hint: Check syntax carefully and make sure your code contains:
AC-3 consistent domains: {'X': [1], 'Y': [2], 'Z': [3]}
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10