Podręcznik

Alternatywą do algorytmu przeszkiwania są tzw. algorytmy spójności (consistency algorithms). Zbiór ograniczeń jest spójny, jeżeli każde częściowe przypisanie do zmiennych, które nie narusza ograniczeń jest dopuszczalne, a w szczególności może zostać rozszerzone do dopuszczalnego całkowitego przypisania. Należy zwrócić uwagę, że spójność nie jest tożsama ze zbiorem rozwiązań dopuszczalnych. Spójność wyklucza wszelki częściowe przypisania przez ograniczenia. Dla spójnych ograniczeń nie jest konieczne przeszukiwanie zbioru rozwiązań z backtrakingiem, gdyż każde dopuszczalne częściowe przypisanie doprowadzi do dopuszczalnego całkowitego przypisania.
Jeżeli pewne ograniczenie nie jest spójne, tzn. istnieją pewne wartości zmiennych występujących w tym ograniczeniu, takie, że spełniają to ograniczenie, ale cały problem nie ma rozwiązania, to można takie wartości usunąć z domen tych zmiennych, czyniąc ograniczenie spójnym. Jest to realizowane przez algorytm Generlized Arc Consistency (GAC). Algorytm GAC rozważa kolejno ograniczenia i w przypadku niespójności ograniczenia dokonuje redukcji domeny zmiennych do wartości zapewniających spójność. Może to powodować konieczność ponownego rozważnie ograniczeń, które już wczesniej zostały uzznane za spójne.
Zamiast formalizować szczegóły algorytm, prześledźmy jego przykładowe działania dla poniższego problemu dla trzech zmiennych $x_1, x_2, x_3$, z których każda może przyjąć wartości ze zbioru $\{1, 2, 3\}$, przy poniższych ograniczeniach:
$x_1 > x_2$
$x_2 > x_3$
Oznaczmy przez $dom_x$ domenę zmiennej $x$. Aby doprowadzić do spójności pierwsze ograniczenie należy ograniczyć domenę $x_1$ do $dom_{x_1}=\{2,3\}$ oraz domenę zmiennej $x_2$ do $dom_{x_2}=\{1,2\}$. Następnie, drugie ograniczenie powoduje redukcję domeny $dom_{x_3}=\{1,2\}$ oraz $dom_{x_2}=\{2\}$. Ponieważ $x_2$ może teraz przyjąć tylko wartość 2, to powoduje redukcję $dom_{x_3}=\{1\}$ i konieczność weryfikacji spójności ograniczenia pierwszego, co w efekcie prowadzi do $dom_{x_1}=\{3\}$. W ten sposób uzyskaliśmy jednoznaczne rozwiązanie $(x_1, x_2,x_3)= (3,2,1)$, choć oczywiście w ogólnym przypadku domeny zmiennych po zastosowaniu GAC nie muszą być jednoelementowe.