Algorytm BACKTRACKING-SEARCH na rysunku 6.5 ma bardzo prostą zasadę postępowania, gdy gałąź wyszukiwania nie powiedzie się: cofnij się do poprzedniej zmiennej i wypróbuj jej inną wartość. Nazywa się to wycofywaniem chronologicznym, ponieważ ponownie sprawdzany jest ostatni punkt decyzyjny. W tym podrozdziale rozważamy lepsze możliwości. Rozważmy, co się stanie, gdy zastosujemy proste śledzenie wstecz na rysunku 6.1 z uporządkowaniem stałej zmiennej Q, NSW, V, T, SA, WA, NT. Załóżmy, że wygenerowaliśmy przypisanie częściowe {Q = red , NSW = green, V = blue, T = red} . Kiedy próbujemy następnej zmiennej, SA , widzimy, że każda wartość narusza ograniczenie. Wracamy do T i próbujemy nowego koloru dla Tasmanii! Oczywiście jest to głupie przebarwianie Tasmanii nie może pomóc w rozwiązaniu problemu z Australią Południową. Bardziej inteligentnym podejściem jest cofnięcie się do zmiennej, która może rozwiązać problem – zmiennej, która była odpowiedzialna za uniemożliwienie jednej z możliwych wartości SA. Aby to zrobić, będziemy śledzić zestaw przypisań, które są w konflikcie z pewną wartością SA.
Zbiór (w tym przypadku {{Q = red , NSW = green, V = blue} ) nazywany jest zbiorem konfliktów dla SA. Metoda backjumping cofa się do najnowszego przypisania w zestawie konfliktów; w tym przypadku backjumping przeskoczyłby Tasmanię i spróbowałby nowej wartości dla V . Ta metoda jest łatwo zaimplementowana przez modyfikację BACKTRACK tak, że gromadzi zestaw konfliktów podczas sprawdzania legalnej wartości do przypisania. Jeśli nie zostanie znaleziona żadna prawidłowa wartość, algorytm powinien zwrócić ostatni element zbioru konfliktu wraz ze wskaźnikiem niepowodzenia.
Bystrooki czytelnik mógł zauważyć, że sprawdzanie w przód może dostarczyć zestaw konfliktów bez dodatkowej pracy: za każdym razem, gdy sprawdzanie w przód oparte na przypisaniu X = x usuwa wartość z domeny Y, powinno dodać X = x do zestawu konfliktów Y. Jeśli ostatnia wartość zostanie usunięta z domeny , wtedy przypisania w zbiorze konfliktów Y są dodawane do zbioru konfliktów X. Oznacza to, że teraz wiemy, że X = x prowadzi do sprzeczności (w Y ), a zatem różnica przypisania powinna być wypróbowane dla X . Czytelnik z orlim wzrokiem mógł zauważyć coś dziwnego: backjumping występuje, gdy każda wartość w domenie jest w konflikcie z bieżącym przypisaniem; ale sprawdzanie w przód wykrywa to zdarzenie i zapobiega dotarciu do takiego węzła przez wyszukiwanie! W rzeczywistości można wykazać, że każda gałąź przycinana przez backjumping jest również przycinana przez sprawdzanie w przód. W związku z tym proste cofanie jest zbędne w wyszukiwaniu z sprawdzaniem do przodu lub, w rzeczy samej, w wyszukiwaniu, które wykorzystuje silniejsze sprawdzanie spójności, takie jak MAC – wystarczy wykonać jedno lub drugie. Pomimo obserwacji z poprzedniego akapitu, idea backjumpingu pozostaje dobra: cofać się w oparciu o przyczyny porażki. Backjumping zauważa awarię, gdy domena zmiennej staje się pusta, ale w wielu przypadkach gałąź jest skazana na zagładę na długo przed tym, jak to nastąpi. Rozważmy ponownie przypisanie częściowe {WA = red , NSW = red} (które, z naszej wcześniejszej dyskusji, jest niespójne). Załóżmy, że próbujemy następnie T = czerwony, a następnie przypisujemy NT, Q ,V, SA. Wiemy, że żadne przypisanie nie może działać dla tych czterech ostatnich zmiennych, więc w końcu zabrakło nam wartości do wypróbowania w NT . Teraz pytanie brzmi, gdzie się cofnąć? Backjumping nie może działać, ponieważ NT ma wartości zgodne z poprzednio przypisanymi zmiennymi — NT nie ma pełnego zestawu konfliktów poprzedzających zmiennych, które spowodowały jego awarię. Wiemy jednak, że cztery zmienne NT , Q , V i SA razem wzięte zawiodły z powodu zestawu poprzedzających zmiennych, które muszą być tymi zmiennymi, które bezpośrednio kolidują z tymi czterema. Prowadzi to do innego i głębszego pojmowania zbioru konfliktów dla zmiennej takiej jak NT: jest to ten zbiór poprzedzających zmiennych, który spowodował, że NT, wraz z wszelkimi kolejnymi zmiennymi, nie mają spójnego rozwiązania. W tym przypadku zestaw to WA i NSW, więc algorytm powinien cofnąć się do NSW i pominąć Tasmanię. Algorytm backjumping, który wykorzystuje zdefiniowane w ten sposób zestawy konfliktów, nazywa się backjumpingiem skierowanym na konflikt
Musimy teraz wyjaśnić, jak obliczane są te nowe zbiory konfliktów. Metoda jest w rzeczywistości dość prosta. Błąd „terminalny” gałęzi wyszukiwania zawsze występuje, ponieważ domena zmiennej staje się pusta; ta zmienna ma standardowy zestaw konfliktów. W naszym przykładzie SA zawodzi, a jego zestaw konfliktów to (powiedzmy) {W,A,NT,Q}. Wracamy do Q , a Q absorbuje zbiór konfliktów z SA (oczywiście bez samego Q) do swojego własnego bezpośredniego zbioru konfliktów, którym jest {NT,NSW}; nowy zestaw konfliktów to {WA, NT , NSW} . Oznacza to, że od Q nie ma rozwiązania, biorąc pod uwagę poprzednie przypisanie do {WA, NT, NSW}. Dlatego wracamy do NT, ostatni z tych NT absorbuje {WA, NT, NSW} – {NT} do swojego własnego bezpośredniego zbioru konfliktów {W,A}, dając {WA, NSW} (jak podano w poprzednim akapicie ). Teraz algorytm wraca do NSW, tak jak mamy nadzieję. Podsumowując: niech Xj będzie zmienną bieżącą, a con f(Xj) niech będzie jej zbiorem konfliktu. Jeśli każda możliwa wartość Xj zawiedzie, wróć do ostatniej zmiennej Xi w conf(Xj) i ponownie oblicz konflikt ustawiony dla Xi w następujący sposób:
