Lokalne algorytmy wyszukiwania okazują się bardzo skuteczne w rozwiązywaniu wielu CSP. Używają sformułowania pełnego stanu (przedstawionego w rozdziale 4.1.1), w którym każdy stan przypisuje wartość do każdej zmiennej, a wyszukiwanie zmienia wartość jednej zmiennej na raz. Jako przykład użyjemy problemu 8-królowych. Na rysunku zaczynamy po lewej stronie od pełnego przypisania do 8 zmiennych; zazwyczaj narusza to kilka ograniczeń.
Następnie losowo wybieramy zmienną powodującą konflikt, która okazuje się być Qs , skrajną prawą kolumną. Chcielibyśmy zmienić wartość na coś, co przybliża nas do rozwiązania; najbardziej oczywistym podejściem jest wybranie wartości, która powoduje minimalną liczbę konfliktów z innymi zmiennymi – heurystyka min – konfliktów.
Na rysunku widzimy dwa wiersze, które naruszają tylko jedno ograniczenie; wybieramy Qs = 3 (czyli przenosimy hetmana do ósmej kolumny, trzeciego rzędu). W następnej iteracji, na środkowej planszy figury, wybieramy Q6 jako zmienną do zmiany i zauważamy, że przeniesienie hetmana do ósmego rzędu nie powoduje żadnych konfliktów. W tym momencie nie ma już sprzecznych zmiennych, więc mamy rozwiązanie.
Min-konflikty są zaskakująco skuteczne w przypadku wielu dostawców CSP. O dziwo, jeśli chodzi o problem -matek, jeśli nie liczyć początkowego rozmieszczenia hetmanów, czas trwania minikonfliktów jest z grubsza niezależny od rozmiaru problemu. Rozwiązuje nawet problem miliona królowych w średnio 50 krokach (po wstępnym zadaniu). Ta godna uwagi obserwacja była bodźcem prowadzącym do wielu badań w latach 90. nad wyszukiwaniem lokalnym i rozróżnieniem między łatwymi i trudnymi problemami. Z grubsza mówiąc, -queens jest łatwe do wyszukiwania lokalnego, ponieważ rozwiązania są gęsto rozmieszczone w przestrzeni stanów. Minkonflikty sprawdzają się również w przypadku trudnych problemów. Na przykład został wykorzystany do planowania obserwacji dla Kosmicznego Teleskopu Hubble’a, skracając czas potrzebny na zaplanowanie tygodniowych obserwacji z trzech tygodni (!) do około 10 minut. Wszystkie lokalne techniki wyszukiwania są kandydatami do zastosowania w CSP, a niektóre z nich okazały się szczególnie skuteczne. Krajobraz CSP w ramach heurystyki minikonfliktów zwykle ma szereg płaskowyżów. Mogą istnieć miliony przypisań zmiennych, od których dzieli tylko jeden konflikt od rozwiązania. Wyszukiwanie na płaskowyżu, które umożliwia przechodzenie na boki do innego stanu z tym samym wynikiem, może pomóc wyszukiwaniu lokalnemu w odnalezieniu drogi poza tym płaskowyżem. Tę wędrówkę po płaskowyżu można pokierować techniką zwaną wyszukiwaniem tabu: utrzymywanie małej listy ostatnio odwiedzanych stanów i zabranianie algorytmowi powrotu do tych stanów. Symulowane wyżarzanie może być również wykorzystane do ucieczki z płaskowyżów. Inna technika, zwana wagą ograniczeń, ma na celu skoncentrowanie poszukiwań na ważnych ograniczeniach. Każdemu ograniczeniu przypisywana jest waga liczbowa, początkowo równa 1. Na każdym etapie wyszukiwania algorytm wybiera parę zmienna/wartość do zmiany, która da w wyniku najniższą całkowitą wagę wszystkich naruszonych ograniczeń. Wagi są następnie dostosowywane przez zwiększenie wagi każdego ograniczenia, które jest naruszone przez bieżące przypisanie. Ma to dwie zalety: dodaje topografię do płaskowyżów, upewniając się, że można poprawić stan obecny, a także dodaje naukę: z czasem trudnym ograniczeniom przypisuje się wyższe wagi. Kolejną zaletą wyszukiwania lokalnego jest to, że można go używać w trybie online, gdy problem ulegnie zmianie. Rozważ problem z planowaniem tygodniowych lotów linii lotniczych. Harmonogram może obejmować tysiące lotów i dziesiątki tysięcy przydziałów personelu, ale zła pogoda na jednym lotnisku może sprawić, że harmonogram będzie niewykonalny. Chcielibyśmy naprawić harmonogram z minimalną liczbą zmian. Można to łatwo zrobić za pomocą lokalnego algorytmu wyszukiwania, zaczynając od bieżącego harmonogramu. Wyszukiwanie wsteczne z nowym zestawem ograniczeń zwykle wymaga znacznie więcej czasu i może znaleźć rozwiązanie z wieloma zmianami w bieżącym harmonogramie.