Définition de la consistance d'arc : Un CSP (X,D,C) est consistant d'arc si pour tout couple de variables (Xi,Xj) de X, et pour toute valeur vi appartenant à D(Xi), il existe une valeur vj appartenant à D(Xj) telle que l'affectation partielle {(Xi,vi),(Xj,vj)} satisfasse toutes les contraintes binaires de C.

Par exemple, si C contient la contrainte "X1 + X2 > 2", et si D(X1)=D(X2)={0,1,2}, alors le CSP n'est pas consistant d'arc car lorsque X1=0, il n'y a aucune valeur de D(X2) qui puisse satisfaire la contrainte "X1 + X2 > 2". Pour qu'il soit consistant d'arc, il faut enlever des domaines de X1 et X2 la valeur 0.

L'algorithme qui enlève les valeurs des domaines des variables d'un CSP jusqu'à ce qu'il soit consistant d'arc (on dit que l'algorithme filtre les domaines des variables) s'appelle AC (pour Arc Consistency). Il existe différentes versions de cet algorithme: AC1, AC2, AC3, ..., chaque version étant plus efficace (en général) que la précédente.

Pour plus d'informations sur les algorithmes AC, vous pouvez lire les articles scientifiques suivants :