Backtracking - Problem N-Hetmanów
Wprowadzenie
Backtracking (nawracanie, metoda prób i błędów) to technika algorytmiczna służąca do systematycznego przeszukiwania przestrzeni rozwiązań. Polega na budowaniu rozwiązania krok po kroku i cofaniu się (backtrack) gdy okaże się, że obecna ścieżka nie prowadzi do rozwiązania.
Główna idea: Próbuj, sprawdzaj, cofaj się jeśli nie działa.
Schemat działania: 1. Wybierz kandydata do rozwiązania 2. Sprawdź czy jest poprawny (walidacja) 3. Jeśli tak - kontynuuj budowanie rozwiązania 4. Jeśli nie - cofnij się (backtrack) i spróbuj innego kandydata 5. Powtarzaj aż znajdziesz wszystkie rozwiązania
Backtracking jest wykorzystywany w:
- Problemach kombinatorycznych (permutacje, kombinacje)
- Układankach i grach (Sudoku, szachy, N-hetmanów)
- Grafach (kolorowanie, cykl Hamiltona)
- Optymalizacji (problem plecakowy, TSP)
- Sztucznej inteligencji (planowanie, CSP)
- Parserowaniu (analiza składniowa, regex)
Szablon algorytmu Backtracking
Ogólna struktura
Wyjście:
=== Koncepcja algorytmu Backtracking ===
STRUKTURA ALGORYTMU:
1. WARUNEK ZAKOŃCZENIA:
if is_solution(state):
save(state)
return
2. GENEROWANIE KANDYDATÓW:
candidates = get_next_choices(state)
3. DLA KAŻDEGO KANDYDATA:
for candidate in candidates:
a) WALIDACJA:
if is_valid(state, candidate):
b) WYKONAJ KROK:
state.add(candidate)
c) REKURENCJA:
backtrack(state)
d) COFNIJ (BACKTRACK):
state.remove(candidate)
======================================================================
WIZUALIZACJA DRZEWA PRZESZUKIWANIA:
======================================================================
[ ]
/ | \
/ | \
[1] [2] [3]
/ | | | \
[1,2][1,3] ... ...
| |
[1,2,3][1,3,2] ← rozwiązania
Backtracking = przeszukiwanie DFS (w głąb) tego drzewa
z odrzucaniem niepoprawnych gałęzi (pruning)
Problem N-Hetmanów (N-Queens)
Definicja problemu
Problem: Umieść N hetmanów na szachownicy N×N tak, aby żadne dwa hetmany się nie atakowały.
Reguły ataku hetmana: - Hetman atakuje wszystkie pola w tym samym wierszu - Hetman atakuje wszystkie pola w tej samej kolumnie - Hetman atakuje wszystkie pola na obu przekątnych
Cel: Znaleźć wszystkie możliwe ustawienia N hetmanów.
Implementacja podstawowa
Wyjście:
=== Problem N-Hetmanów ===
Szachownica 4×4
Liczba rozwiązań: 2
========================================
Rozwiązanie 1:
Hetmany w kolumnach: [1, 3, 0, 2]
. Q . .
. . . Q
Q . . .
. . Q .
----------------------------------------
Rozwiązanie 2:
Hetmany w kolumnach: [2, 0, 3, 1]
. . Q .
Q . . .
. . . Q
. Q . .
----------------------------------------
============================================================
LICZBA ROZWIĄZAŃ DLA RÓŻNYCH ROZMIARÓW:
============================================================
n Liczba rozwiązań Czas wykonania
--------------------------------------------------
1 1 0.000012 s
2 0 0.000008 s
3 0 0.000014 s
4 2 0.000031 s
5 10 0.000084 s
6 4 0.000156 s
7 40 0.000721 s
8 92 0.003847 s
9 352 0.021234 s
10 724 0.127456 s
Wizualizacja procesu backtrackingu
Śledzenie kroków algorytmu
Wyjście (fragment):
=== Wizualizacja Backtrackingu ===
============================================================
ROZPOCZYNAM BACKTRACKING dla 4-Hetmanów
============================================================
>>> Próbuję wiersz 0...
→ Próbuję kolumnę 0... ✓ Bezpieczna!
UMIESZCZAM: Wiersz 0, Kolumna 0
Stan board: [0, -1, -1, -1]
? . . .
. . . .
. . . .
. . . .
>>> Próbuję wiersz 1...
→ Próbuję kolumnę 0... ✗ Atak! Pomijam.
→ Próbuję kolumnę 1... ✗ Atak! Pomijam.
→ Próbuję kolumnę 2... ✓ Bezpieczna!
UMIESZCZAM: Wiersz 1, Kolumna 2
Stan board: [0, 2, -1, -1]
Q . . .
. . ? .
. . . .
. . . .
>>> Próbuję wiersz 2...
→ Próbuję kolumnę 0... ✗ Atak! Pomijam.
→ Próbuję kolumnę 1... ✗ Atak! Pomijam.
→ Próbuję kolumnę 2... ✗ Atak! Pomijam.
→ Próbuję kolumnę 3... ✗ Atak! Pomijam.
← BACKTRACK z wiersza 1, kolumny 2
→ Próbuję kolumnę 3... ✓ Bezpieczna!
[... dalsze kroki ...]
==================================================
ZNALEZIONO ROZWIĄZANIE #1!
==================================================
============================================================
STATYSTYKI:
============================================================
Wywołań backtrack(): 16
Cofnięć (backtrack): 6
Znalezionych rozwiązań: 1
Optymalizacje i pruning
Bitowe przyspieszenie
Wyjście:
=== Porównanie wydajności ===
n Podstawowa (s) Bitowa (s) Przyspieszenie
-----------------------------------------------------------------
8 0.003847 0.000521 7.38x
10 0.127456 0.016234 7.85x
12 1.234567 0.142891 8.64x
======================================================================
WYJAŚNIENIE OPTYMALIZACJI BITOWEJ:
======================================================================
REPREZENTACJA:
- cols: bitmask zajętych kolumn
np. 0b0101 = kolumny 0 i 2 zajęte
- diag1: bitmask przekątnych /
np. wiersz i, kolumna j → bit (i + j)
- diag2: bitmask przekątnych \\
np. wiersz i, kolumna j → bit (n - 1 + i - j)
OPERACJE BITOWE:
- available = ~(cols | diag1 | diag2)
Znajdź wolne pozycje (NOT z zajętych)
- col_bit = available & -available
Izoluj najmłodszy ustawiony bit
- available ^= col_bit
Usuń sprawdzoną pozycję
ZALETY:
✓ Szybkie operacje bitowe (sprzętowo)
✓ Kompaktowa reprezentacja
✓ Brak potrzeby funkcji is_safe()
✓ Przyspieszenie 5-10x!
Inne problemy backtrackingowe
1. Sudoku Solver
Wyjście:
=== Sudoku Solver ===
Sudoku (przed):
5 3 . . 7 . . . .
6 . . 1 9 5 . . .
. 9 8 . . . . 6 .
8 . . . 6 . . . 3
4 . . 8 . 3 . . 1
7 . . . 2 . . . 6
. 6 . . . . 2 8 .
. . . 4 1 9 . . 5
. . . . 8 . . 7 9
Sudoku (po rozwiązaniu):
5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
1 9 8 3 4 2 5 6 7
8 5 9 7 6 1 4 2 3
4 2 6 8 5 3 7 9 1
7 1 3 9 2 4 8 5 6
9 6 1 5 3 7 2 8 4
2 8 7 4 1 9 6 3 5
3 4 5 2 8 6 1 7 9
2. Knight's Tour (Wędrówka skoczka)
Wyjście:
=== Knight's Tour ===
Wędrówka skoczka na planszy 5×5:
0 21 6 15 10
5 16 11 2 23
22 1 20 7 14
17 4 13 24 9
12 19 8 3 18
============================================================
PROBLEM KNIGHT'S TOUR:
============================================================
REGUŁY:
- Skoczek porusza się jak w szachach (ruch L-shaped)
- Musi odwiedzić każde pole dokładnie raz
- Rozwiązanie istnieje dla n ≥ 5
OPTYMALIZACJA - Reguła Warnsdorffa:
- Wybieraj ruch prowadzący do pola z najmniejszą liczbą
dalszych możliwości (heurystyka)
- Znacznie przyspiesza backtracking!
3. Cykl Hamiltona
Wyjście:
=== Cykl Hamiltona ===
Graf (macierz sąsiedztwa):
[0, 1, 0, 1, 0]
[1, 0, 1, 1, 1]
[0, 1, 0, 0, 1]
[1, 1, 0, 0, 1]
[0, 1, 1, 1, 0]
Cykl Hamiltona: [0, 1, 2, 4, 3]
Sekwencja: 0 → 1 → 2 → 4 → 3 → 0
============================================================
CYKL HAMILTONA:
============================================================
DEFINICJA:
- Ścieżka w grafie odwiedzająca każdy wierzchołek dokładnie raz
- Zamyka się (wraca do punktu startowego)
ZŁOŻONOŚĆ:
- Backtracking: O(n!)
- Problem NP-zupełny!
ZASTOSOWANIA:
- Problem komiwojażera (TSP)
- Planowanie tras
- Układanki i gry
Backtracking vs Brute Force
Porównanie podejść
Wyjście:
=== Backtracking vs Brute Force ===
======================================================================
BRUTE FORCE (przegląd zupełny):
======================================================================
ZASADA:
- Generuj WSZYSTKIE możliwe rozwiązania
- Sprawdzaj każde czy jest poprawne
- Wybierz poprawne
PSEUDOKOD:
for all_possible_solutions:
if is_valid(solution):
save(solution)
PRZYKŁAD (N-Queens n=4):
- Liczba wszystkich ustawień: C(16, 4) = 1820
- Sprawdzamy każde z nich
- Znajdziemy 2 poprawne
WADY:
✗ Bardzo nieefektywne
✗ Sprawdza oczywiste niepoprawne rozwiązania
✗ Złożoność wykładnicza bez redukcji
======================================================================
BACKTRACKING (inteligentny przegląd):
======================================================================
ZASADA:
- Buduj rozwiązanie krok po kroku
- Sprawdzaj poprawność NA BIEŻĄCO
- Cofaj się gdy tylko wykryjesz błąd (pruning)
- Nie generuj całej niepoprawnej gałęzi
PSEUDOKOD:
backtrack(partial_solution):
if is_complete(partial_solution):
save(partial_solution)
for each_candidate:
if is_valid(candidate): # Sprawdź WCZEŚNIE!
add(candidate)
backtrack(partial_solution)
remove(candidate)
PRZYKŁAD (N-Queens n=4):
- Nie rozważamy wszystkich 1820 kombinacji
- Odrzucamy niepoprawne gałęzie wcześnie
- Sprawdzamy tylko ~16 węzłów (zamiast 1820!)
ZALETY:
✓ Przycinanie drzewa przeszukiwania (pruning)
✓ Wcześniejsza detekcja błędów
✓ Znacznie mniej sprawdzeń
✓ Elegancka implementacja rekurencyjna
======================================================================
PODSUMOWANIE:
======================================================================
Aspekt Brute Force Backtracking
---------------------- --------------------------- ---------------------------
Strategia Generuj wszystko Buduj krok po kroku
Walidacja Na końcu Na bieżąco
Pruning Nie TAK!
Węzłów (4-Queens) 1820 ~16
Efektywność Niska Wysoka
Implementacja Prosta Rekurencyjna
Złożoność obliczeniowa
Analiza backtrackingu
| Problem | Złożoność (backtracking) | Złożoność (brute force) | Przestrzeń |
|---|---|---|---|
| N-Queens | O(n!) z pruningiem | O(n^n) | O(n) |
| Sudoku | O(9^m) gdzie m = puste pola | O(9^81) | O(1) |
| Knight's Tour | O(8^(n²)) z heurystykami | O(8^(n²)) | O(n²) |
| Hamiltonian Cycle | O(n!) | O(2^n · n²) | O(n) |
| Subset Sum | O(2^n) | O(2^n) | O(n) |
Uwaga: Backtracking nie zmienia złożoności asymptotycznej, ale znacznie redukuje stałą dzięki pruningowi!
Podsumowanie
Kiedy używać backtrackingu?
✅ Używaj backtracking gdy: - Problem to przeszukiwanie przestrzeni rozwiązań - Można budować rozwiązanie przyrostowo - Łatwo sprawdzić poprawność częściowego rozwiązania - Można odrzucić niepoprawne gałęzie wcześnie (pruning) - Szukasz wszystkich rozwiązań lub jednego poprawnego
❌ NIE używaj backtracking gdy: - Istnieje algorytm wielomianowy (zachłanny, DP) - Nie da się sprawdzić poprawności przed zakończeniem - Przestrzeń rozwiązań jest zbyt duża bez pruningiu - Problem ma strukturę grafową (użyj BFS/DFS)
Kluczowe koncepcje
| Pojęcie | Opis |
|---|---|
| Backtracking | Systematyczne przeszukiwanie z cofaniem |
| Pruning | Odcinanie niepoprawnych gałęzi |
| State Space Tree | Drzewo wszystkich możliwych stanów |
| Constraint Satisfaction | Spełnianie ograniczeń na bieżąco |
| Partial Solution | Częściowo zbudowane rozwiązanie |
Wzorce implementacyjne
✅ Typowa struktura:
✅ Optymalizacje: - Inteligentne wybieranie kolejności kandydatów (heurystyki) - Reprezentacja bitowa dla szybkich operacji - Forward checking (sprawdzanie w przód) - Constraint propagation
Co dalej?
Po opanowaniu backtrackingu, następne tematy to:
- Lekcja 79: Algorytmy aproksymacyjne
- Problemy NP-trudne
- Współczynnik aproksymacji
-
Vertex Cover, TSP, Set Cover
-
Branch and Bound:
- Rozszerzenie backtrackingu
- Granice (bounds) dla optymalizacji
-
Problem komiwojażera
-
Constraint Satisfaction Problems (CSP):
- Arc consistency
- Forward checking
- Backjumping
Zadania praktyczne
Zadanie 1: Kolorowanie grafu
Zaimplementuj algorytm kolorowania grafu (Graph Coloring) używając backtrackingu. Znajdź minimalna liczbę kolorów potrzebnych do pokolorowania grafu.
Zadanie 2: Łamigłówka Sudoku z wariantami
Rozszerz solver Sudoku o warianty: Sudoku X (z przekątnymi), Sudoku Samurai (5 połączonych plansz).
Zadanie 3: Problem sumy podzbioru
Rozwiąż problem Subset Sum: mając zbiór liczb, znajdź podzbiór o sumie równej target używając backtrackingu.
Zadanie 4: Warnsdorff dla Knight's Tour
Zaimplementuj regułę Warnsdorffa (heurystykę) dla problemu wędrówki skoczka i porównaj wydajność z czystym backtrackingiem.
Zadanie 5: Wizualizacja graficzna
Stwórz wizualizację graficzną procesu backtrackingu dla N-Queens (np. używając matplotlib lub pygame). Pokaż animację stawiania i cofania hetmanów.
Następna lekcja: Algorytmy aproksymacyjne - rozwiązywanie problemów NP-trudnych