Spełnianie ograniczeń: backtracking, propagacja ograniczeń i AC-3 na sudoku i mapie czeskich krajów

Zmienne, dziedziny i ograniczenia, graf ograniczeń, backtracking, heurystyki MRV i LCV, sprawdzanie w przód, AC-3 i min-conflicts — na kolorowaniu czeskich krajów, sudoku i ośmiu hetmanach.

15 minut Matěj Žalmánek 2026-10-15

Seria Podstawy AI Część 23 z 52

1. Mapa sztucznej inteligencji: co jest czym i jak to do siebie pasuje
2. Krótka historia sztucznej inteligencji: od Turinga do modeli językowych
3. Dane, model, trening, inferencja: podstawowe pojęcia na jednym przykładzie
4. Jak czytać zapis matematyczny: symbole, indeksy, sumy i kwantyfikatory
5. Zbiory i relacje: klocki, z których składają się definicje w AI
6. Funkcje i odwzorowania: dlaczego każdy model AI jest funkcją
7. Logika i dowody: reguły, według których rozumuje AI
8. Grafy i drzewa: struktura, na której opierają się przeszukiwanie i sieci neuronowe
9. Algebra liniowa dla uczenia maszynowego: wektory, macierze i dlaczego AI głównie mnoży
10. Pochodne, gradient i reguła łańcuchowa: jak model ustala, w którą stronę się uczyć
11. Spadek gradientu: jak uczy się model
12. Czym jest prawdopodobieństwo: od rzutu kostką do aksjomatów Kołmogorowa
13. Prawdopodobieństwo warunkowe i twierdzenie Bayesa: jak zmienić ocenę, gdy dowiesz się czegoś nowego
14. Zmienna losowa i dystrybuanta: jedna funkcja, która mówi o rozkładzie wszystko
15. Funkcja gęstości i funkcja prawdopodobieństwa: dlaczego zmienna ciągła ma w punkcie prawdopodobieństwo zero
16. Wartość oczekiwana, wariancja i kowariancja: gdzie leży rozkład, jak jest szeroki i co z czym się wiąże
17. Przegląd rozkładów prawdopodobieństwa: Bernoulliego, dwumianowy, Poissona, jednostajny, normalny i wykładniczy
18. Prawo wielkich liczb i centralne twierdzenie graniczne: dlaczego średnie zachowują się tak przewidywalnie
19. Statystyka i estymacja parametrów: największa wiarygodność, MAP i przedziały ufności
20. Teoria informacji: entropia, entropia krzyżowa i dywergencja KL — skąd się biorą funkcje straty
21. Przeszukiwanie przestrzeni stanów: BFS, DFS, UCS i A* z animacjami
22. Gry i przeciwnik: minimax, przycinanie alfa-beta i Monte Carlo tree search
23. Spełnianie ograniczeń: backtracking, propagacja ograniczeń i AC-3 na sudoku i mapie czeskich krajów
24. Logika i systemy z bazą wiedzy: wnioskowanie w przód i wstecz, rezolucja i systemy ekspertowe
25. Planowanie: STRIPS, świat klocków, heurystyki z relaksacji i planowanie w agentach AI
26. Przeszukiwanie lokalne i symulowane wyżarzanie: komiwojażer przez czeskie miasta wojewódzkie
27. Algorytmy genetyczne: populacja, krzyżowanie, mutacja i selekcja na plecaku na wycieczkę
28. Strategie ewolucyjne i programowanie genetyczne: od reguły jednej piątej do prawa Keplera
29. Optymalizacja kolonią mrówek: jak ślad feromonowy znajduje krótką drogę
30. Optymalizacja rojem cząstek: bezwładność, własne doświadczenie i doświadczenie roju
31. Neuroewolucja: ewolucja wag i kształtu sieci neuronowych oraz algorytm NEAT
32. Zbiory rozmyte i funkcje przynależności: jak zapisać „trochę ciepło”
33. Logika rozmyta a prawdopodobieństwo: dlaczego „trochę ciepło” nie znaczy „prawdopodobnie ciepło”
34. Logika rozmyta: t-normy, implikacje i reguły JEŻELI–TO
35. Sterowanie rozmyte: Mamdani i Sugeno od wentylatora po wahadło na wózku
36. Klasteryzacja rozmyta: algorytm fuzzy c-means i punkty między skupieniami
37. Systemy neuro-rozmyte (ANFIS): reguły rozmyte, które uczą się z danych
38. Łańcuchy Markowa: macierz przejścia, rozkład stacjonarny i PageRank
39. Ukryte modele Markowa: algorytm Viterbiego i nieuczciwe kasyno
40. Sieci bayesowskie: dlaczego trawa jest mokra i co z tego wynika dla zraszacza
41. Filtr Kalmana: jak z niedokładnych pomiarów oszacować, gdzie jest samochód i jak szybko jedzie
42. Rodzaje uczenia maszynowego: nadzorowane, nienadzorowane, półnadzorowane i inne
43. Prompty, kontekst i RAG: jak dać modelowi właściwe informacje
44. Wariacyjne autoenkodery (VAE): nowe obrazki z ciągłej przestrzeni latentnej
45. Generatywne sieci przeciwstawne (GAN): fałszerz kontra detektyw
46. Modele dyfuzyjne: jak z czystego szumu powstaje obraz
47. Procesy decyzyjne Markowa: stany, akcje, nagrody i równania Bellmana
48. Q-learning i DQN: uczenie się wartości akcji od tabeli po sieć neuronową
49. Policy gradient i PPO: uczenie się bezpośrednio polityki
50. Jak działa agent AI: model językowy w pętli z narzędziami
51. Programowanie z agentami AI: zadanie, testy i kontrola
52. Ocena i bezpieczeństwo systemów AI: jak mierzyć i jak pilnować

Pełny program serii Gotowe: 52 z 83 tematów

Plan lekcji, w którym żaden nauczyciel nie uczy dwóch klas naraz. Sudoku. Rozmieszczenie elementów na płytce, dyżury w szpitalu, przydział samolotów do bramek. Wszystkie te zadania łączy to, że nie szukamy ścieżki, lecz przypisania: każdej zmiennej trzeba dać wartość tak, by wszystkie reguły obowiązywały jednocześnie. Takie zadanie nazywa się problemem spełniania ograniczeń i w przeciwieństwie do ogólnego przeszukiwania ma jedną wielką zaletę — reguły są widoczne, więc algorytm może z nich wnioskować, a nie tylko próbować.

Nawiązuje do części Przeszukiwanie przestrzeni stanów i Grafy i drzewa.

1. Czym jest problem spełniania ograniczeń

Definicja — CSP

Problem spełniania ograniczeń (constraint satisfaction problem, CSP) to trójka (X, D, C), gdzie

• X = {X₁, …, X_n} to zbiór zmiennych,
• D = {D₁, …, D_n}, gdzie D_i to dziedzina — zbiór wartości, które może przyjmować X_i,
• C to zbiór ograniczeń. Każde ograniczenie to para (zakres, relacja): zakres to lista zmiennych, relacja mówi, które kombinacje ich wartości są dozwolone.

Ograniczenie z dwiema zmiennymi w zakresie jest binarne, na przykład X₁ ≠ X₂.

Definicja — przypisanie i rozwiązanie

Przypisanie nadaje wartość z dziedziny niektórym zmiennym. Jest spójne, gdy nie narusza żadnego ograniczenia, i pełne, gdy wartość ma każda zmienna.

Rozwiązanie CSP to pełne spójne przypisanie.

Dlaczego nie potraktować tego jak zwykłego przeszukiwania? Dałoby się — stan to rozpoczęte przypisanie, akcja to „daj kolejnej zmiennej wartość”. Tyle że przeszukiwanie patrzyłoby na stan jak na czarną skrzynkę. CSP zagląda do środka: wie, które reguły obowiązują i których zmiennych dotyczą. Na tym opierają się wszystkie sztuczki w tej części.

2. Graf ograniczeń: kolorowanie mapy krajów

Klasyczne zadanie: pokolorować mapę tak, by żadne dwa sąsiednie państwa nie miały tego samego koloru. Weźmy czternaście czeskich krajów. Zmienne to kraje, dziedzina to zestaw kolorów, a dla każdej wspólnej granicy jest ograniczenie „różne kolory”.

Definicja — graf ograniczeń

Graf ograniczeń binarnego CSP ma za wierzchołki zmienne i krawędź między X_i a X_j wtedy i tylko wtedy, gdy łączy je jakieś ograniczenie.

Z czterema kolorami idzie gładko. Z trzema nie da się wcale — a graf pokaże dlaczego. Kraj środkowoczeski sąsiaduje z Pragą i z siedmioma krajami, które tworzą wokół niego zamknięty krąg. Krąg o nieparzystej liczbie wierzchołków sam w sobie potrzebuje trzech kolorów (dwa musiałyby się regularnie przeplatać, a przy nieparzystej liczbie to nie wychodzi). Kraj środkowoczeski sąsiaduje ze wszystkimi siedmioma, więc dla niego musi zostać czwarty kolor:

To, że cztery kolory wystarczą na każdą mapę, mówi słynne twierdzenie o czterech barwach. Udowodnili je Appel i Haken w 1976 roku — jako pierwsze wielkie twierdzenie matematyczne z pomocą komputera, który sprawdził prawie dwa tysiące przypadków.

3. Backtracking

Definicja — backtracking

Backtracking to przeszukiwanie w głąb, które w każdym kroku przypisuje wartość jednej kolejnej zmiennej. Wartości, która narusza ograniczenie z już przypisanymi zmiennymi, w ogóle nie próbuje. Gdy dla zmiennej nie zostanie żadna wartość, wraca do poprzedniej zmiennej i próbuje jej następnej wartości.

W najgorszym przypadku przechodzi O(dⁿ) przypisań, gdzie d to rozmiar dziedziny, a n liczba zmiennych. Ogólny CSP jest NP-trudny, więc w najgorszym przypadku lepiej nie potrafimy.

def backtracking(assignment, csp):
    if len(assignment) == len(csp.variables):
        return assignment                     # wszystko ma wartość: rozwiązanie
    p = select_variable(assignment, csp)
    for h in csp.domains[p]:
        if consistent(p, h, assignment, csp):
            assignment[p] = h
            result = backtracking(assignment, csp)
            if result:
                return result
            del assignment[p]                 # ślepy zaułek: wróć
    return None

Na krajach z czterema kolorami backtracking wykonuje 14 przypisań, jedno na kraj, i ani razu się nie cofa. Z trzema kolorami musi udowodnić, że rozwiązanie nie istnieje — a to oznacza wypróbowanie wszystkiego: 93 przypisania, zanim się podda.

4. Którą zmienną i jaką wartość

Szkielet backtrackingu pozostawia otwarte dwa pytania: którą zmienną wziąć jako następną i w jakiej kolejności próbować jej wartości. Odpowiedzi mają większe znaczenie, niż mogłoby się wydawać.

Definicja — MRV, stopień, LCV

MRV (minimum remaining values): wybierz zmienną z najmniejszą liczbą wartości, które jeszcze nie są w konflikcie z przypisaniem.

Heurystyka stopnia: przy remisie wybierz zmienną, która ma najwięcej ograniczeń z dotąd nieprzypisanymi zmiennymi.

LCV (least constraining value): wartości zmiennej próbuj od tej, która sąsiadom skreśli najmniej możliwości.

Przy trzech kolorach na krajach MRV razem ze sprawdzaniem w przód z następnego rozdziału zmniejsza liczbę przypisań z 93 do 45 — zaczyna od kraju, któremu zostało najmniej kolorów, i sprzeczność znajduje dwa razy szybciej.

5. Sprawdzanie w przód

Definicja — sprawdzanie w przód

Po przypisaniu X_i = v przejdź każdą nieprzypisaną zmienną X_j, która jest połączona z X_i ograniczeniem, i usuń z D_j wartości niezgodne z v. Jeśli któraś dziedzina zostanie pusta, natychmiast cofnij przypisanie.

Różnicę widać na sudoku poniżej. Prosty backtracking idący po wierszach potrzebuje ponad 14 milionów przypisań. Ze sprawdzaniem w przód jest ich 11 400. A gdy dodamy do tego MRV, spada to do 81 — 30 podanych cyfr i 51 uzupełnionych, bez ani jednego powrotu.

6. Spójność łukowa i AC-3

Sprawdzanie w przód patrzy tylko o krok dalej: na sąsiadów zmiennej, którą właśnie przypisaliśmy. Można to zrobić dokładniej — skreślać także między zmiennymi, które jeszcze nie mają wartości.

Definicja — spójność łukowa

Zmienna X_i jest łukowo spójna względem X_j, gdy dla każdej wartości x ∈ D_i istnieje y ∈ D_j taka, że para (x, y) spełnia ograniczenie między nimi. CSP jest łukowo spójny, gdy zachodzi to dla każdej skierowanej krawędzi (X_i, X_j) grafu ograniczeń.

Algorytm — AC-3

1. Wstaw do kolejki wszystkie skierowane krawędzie (X_i, X_j).
2. Wyjmij krawędź z kolejki i usuń z D_i każdą wartość, która w D_j nie ma partnera.
3. Jeśli D_i się zmniejszyła, wstaw z powrotem do kolejki wszystkie krawędzie (X_k, X_i) dla sąsiadów X_k ≠ X_j — ich wartości mogły właśnie stracić partnera. Jeśli D_i jest pusta, CSP nie ma rozwiązania.
4. Powtarzaj, dopóki kolejka nie jest pusta.

Dla c binarnych ograniczeń i dziedzin rozmiaru najwyżej d AC-3 trwa O(c · d³).

from collections import deque

def ac3(csp):
    queue = deque((xi, xj) for xi in csp.variables for xj in csp.neighbors[xi])
    while queue:
        xi, xj = queue.popleft()
        if revise(csp, xi, xj):
            if not csp.domains[xi]:
                return False                  # pusta dziedzina: rozwiązanie nie istnieje
            for xk in csp.neighbors[xi]:
                if xk != xj:
                    queue.append((xk, xi))
    return True

def revise(csp, xi, xj):
    before = len(csp.domains[xi])
    csp.domains[xi] = [x for x in csp.domains[xi]
                       if any(csp.allowed(xi, x, xj, y) for y in csp.domains[xj])]
    return len(csp.domains[xi]) < before

7. Sudoku: propagacja w praktyce

Sudoku to CSP jak z podręcznika: 81 zmiennych, dziedziny {1, …, 9} i ograniczenie „różne wartości” dla każdej pary pól w tym samym wierszu, kolumnie lub kwadracie 3 × 3. Każde pole ma więc 20 sąsiadów w grafie ograniczeń.

Uruchommy na łamigłówce z 30 cyframi samo AC-3, bez ani jednego przypisania na ślepo. Skreśli 408 wartości — i każdemu z 51 pustych pól zostanie dokładnie jedna. Sudoku jest rozwiązane czystym rozumowaniem:

Przy łatwych sudoku tak to wygląda; przy trudniejszych propagacja gdzieś utknie i do akcji wkracza szukanie — backtracking, który po każdym przypisaniu ponownie uruchamia propagację. To połączenie (utrzymywanie spójności łukowej, MAC) jest podstawą większości prawdziwych solverów. Dla porównania na tej samej łamigłówce:

Od czternastu milionów do zera. Brutalna siła i sprytne rozumowanie rozwiązują to samo zadanie — tylko jedno z nich czyta reguły.

8. Przeszukiwanie lokalne: min-conflicts

Zupełnie inna strategia: nie budować rozwiązania kawałek po kawałku, lecz zacząć od pełnego przypisania, które narusza mnóstwo ograniczeń, i stopniowo je poprawiać. To przeszukiwanie lokalne z części o przeszukiwaniu, tylko funkcją celu jest liczba naruszonych ograniczeń.

Algorytm — min-conflicts

1. Zacznij od losowego pełnego przypisania.
2. Dopóki jakieś ograniczenie nie jest spełnione: wybierz losowo zmienną w konflikcie i daj jej wartość, z którą narusza najmniej ograniczeń (przy remisie losowo).

Klasycznym sprawdzianem jest problem n hetmanów: rozstawić n szachowych hetmanów na szachownicy n × n tak, by żadne dwa się nie atakowały. Zmienną jest wiersz hetmana w każdej kolumnie. Dla ośmiu hetmanów nasz przebieg zaczął się od sześciu atakujących się par i skończył po 8 krokach:

Zwróć uwagę na środkowe kroki: liczba konfliktów przez cztery kroki utrzymuje się na jednym — algorytm przesuwa hetmany „w bok” po płaskowyżu, zanim znajdzie ruch, który usunie sprzeczność. Zaskakujące jest, jak dobrze to się skaluje: milion hetmanów min-conflicts rozwiązuje średnio w mniej więcej pięćdziesięciu krokach. Tą samą metodą planowano obserwacje Kosmicznego Teleskopu Hubble’a.

9. Ograniczenia w praktyce

• Plany i harmonogramy. Szkolne plany lekcji, grafiki dyżurów, przydział sal i plany produkcji zadaje się jako zmienne, dziedziny i ograniczenia. Solvery takie jak Google OR-Tools łączą propagację, szukanie i lokalne ulepszanie.
• Solvery SAT rozwiązują CSP, w których każda zmienna to prawda/fałsz. Weryfikują projekty układów scalonych, szukają błędów w oprogramowaniu, a menedżery pakietów (na przykład w Linuksie) składają nimi wersje bibliotek, które ze sobą współpracują.
• Kompilatory przydzielają zmienne programu do rejestrów procesora przez kolorowanie grafu: dwie zmienne, które żyją jednocześnie, nie mogą dzielić rejestru — dokładnie jak sąsiednie kraje koloru.
• Konfiguratory w sklepach internetowych i produkcji pilnują, by wybrane komponenty do siebie pasowały.
• Agenci AI i modele językowe w CSP często nie błyszczą: do sudoku czy planu lekcji bardziej niezawodnie nadaje się solver. Dobry agent dlatego nie rozwiązuje zadania „z głowy” — przekłada je na zmienne i ograniczenia i wywołuje na nim narzędzie.

10. Podsumowanie

• CSP to trójka (X, D, C): zmienne, dziedziny i ograniczenia. Rozwiązanie to pełne przypisanie, które nie narusza żadnego ograniczenia.
• Backtracking przypisuje zmienne jedną po drugiej i wycofuje się ze ślepych zaułków; w najgorszym przypadku jest wykładniczy.
• Heurystyki MRV i LCV wybierają najtrudniejszą zmienną i najbardziej ustępliwą wartość; sprawdzanie w przód wykrywa ślepy zaułek o krok wcześniej.
• AC-3 rozprowadza skreślenia po grafie ograniczeń, dopóki każda wartość nie ma partnera; łatwe sudoku rozwiązuje całkowicie bez szukania.
• Min-conflicts poprawia pełne przypisanie i radzi sobie nawet z ogromnymi zadaniami, takimi jak milion hetmanów.

Chcesz to wypróbować? Poproś agenta AI o napisanie solvera sudoku z backtrackingiem, a potem dodawaj do niego sprawdzanie w przód, MRV i AC-3 — i licz, ile przypisań ubędzie.

Masz inne zdanie? Napisz na support@coden-app.com.