N-koniecznicy: Jak Backtracking Przycina Wyszukiwanie Eksponencjalne

Mała i zmyślna plansza

Umieść N królowych na planszy N×N tak, aby żadne dwie nie dzieliłyby jednej rzędu, kolumny ani przekątnej. Dla N=8 proste podejście — spróbować wszystkich sposobów umieszczenia 8 królowych wśród 64 pól — daje C(64,8), ponad 4 miliardy kombinacji. Ograniczając się do jednej kolumny na pole i jedną rzędę (królowa atakuje zarówno poziomo, jak i pionowo, więc żaden prawidłowy rozwiązanie nie może powtarzać ani jednego z tych warunków) sprowadza to do 8! = 40 320 permutacji, ale nadal musisz sprawdzić każdą z nich na konflikty poziomie, chyba że szukasz bardziej inteligentnie.

Powrot do wcześniejszychdecyzji: budowa, sprawdzenie, cofanie

Metoda backtracking umieszcza królewskie figury w jednej kolumnie na raz i cofa się od częściowego ułożenia jak tylko staje się jasne, że nie można go rozszerzyć — dawno przed tym, gdy wszystkie N królewskie figury zostaną umieszczone. To cała idea: inkrementalne budowanie plus wcześniejsza odrzucenie, które przekształca eksponencjalny wyszukiwanie siłą bruta w coś, co zakończy się w ułamku milisekundy dla N=8.

funkcja solve(wiersz, kolumny, przekątna1, przekątna2): jeżeli wiersz == N: zapisz rozwiązanie; zwróc dla kolumny w zakresie 0..N-1: d1 = wiersz - kolumna + N // id przekątnej "/" d2 = wiersz + kolumna // id przekątnej "\" jeżeli kolumna w kolumny lub d1 w przekątna1 lub d2 w przekątna2: kontynuuj // konflikt — pomin, nie nawet rekursjowani umieśc królewską figurę na pozycji (wiersz, kolumna) solve(wiersz + 1, kolumny ∪ {kolumna}, przekątna1 ∪ {d1}, przekątna2 ∪ {d2}) usun królewską figurę z pozycji (wiersz, kolumna) // ← krok cofania Każda z dwóch kierunków przekątnej jest śledzona przez pojedynczy identyfikator całkowity dla każdej przekątnej — komórki na tej samej przekątej "/" dzielą się row+col, a komórki na tej samej przekątnej "\" dzielą się row-col — więc sprawdzenie konfliktu to trzy operacje wyszukiwania zbiorów, O(1) każda, zamiast skanowania już umieszczonego królewskich figur. To jedno zmienione miejsce jest przyczyną tego, że proste rekurencyjne ułożenie bez tych zbiorów identyfikatorów jest znacznie wolniejsze niż wersja pokazana tu, nawet jeśli obie technicznie są backtrackingiem.

function solve(row, cols, diag1, diag2):
    if row == N: record solution; return
    for col in 0..N-1:
        d1 = row - col + N        // "/" diagonal id
        d2 = row + col            // "\" diagonal id
        if col in cols or d1 in diag1 or d2 in diag2:
            continue               // conflict — skip, don't even recurse
        place queen at (row, col)
        solve(row + 1, cols ∪ {col}, diag1 ∪ {d1}, diag2 ∪ {d2})
        remove queen at (row, col)   // ← the "backtrack" step

Jaka rzeczywista ilość podcinania występuje

Drzewo wyszukiwania dla umieszczania N królików w jednej kolumnie po raz na rząd ma w teorii N^N liści, jeśli ignorujemy wszystkie ograniczenia. Podcinanie kolumnowe i przekątnych znacznie zmniejsza to: dla N=8 jest 92 rozwiązań (12 do symetrii) dostępnych po odwiedzeniu tylko kilku tysięcy częściowych umiejscowień, a nawet dla N=20 — z 39×10^15 potencjalnymi permutacjami, jeśli ograniczamy się tylko do kolumn — rozwiązanie wchodzi w działo w mniej niż sekundę dzięki odwrotnemu przeszukiwaniu wiersz po wierszu, ponieważ prawie każda gałąź umiera już w pierwszych kilku wierszach. Liczba rozwiązań wzrasta rzadko jak stała do potęgi N (empirycznie około 2,5 do 2,7 dla każdej dodanej króliku w zakresie, który został obliczony dokładnie), ale nikt nie dowiódł formuły zamkniętej — liczby rozwiązań poza N≈27 są znane tylko z dedykowanych wysiłków wyszukiwania na skalę dużą, a nie odvojenia.

Dlaczymy to zastępuje znacznie większą klasę problemów

N-Konie jest klasycznym przykładem zagadnienia spełniającego ograniczenia (CSP): zmienne (jedna na każdą wiersz), dziedziny (który kolumna), oraz ograniczenia (brak współdzielonych kolumn lub przekątnych). Ten sam szkielet zwracania się do powrotu plus odcinania, z logiką sprawdzania ograniczeń zamienioną, rozwiązuje Sudoku, kolorowanie grafów, planowanie harmonogramów egzaminów i układanie schematów elektrycznych. Dwa ogólne przyspieszenia zagadnień spełniających ograniczenia mapują bezpośrednio na N-Konie: propagacja ograniczeń (sprawdzanie w przód — po umieszczeniu króla, natychmiast zmniejsz kandydatów kolumn dla przyszłych wierszy zamiast czekać, aż odkryjesz konflikt), oraz heurystyki ustalania kolejności zmiennych (takie jak najmniej pozostawionych wartości — umieszczenie najbardziej ograniczonego wiersza nastepnie), oba z których odcinają drzewo wcześniej i mogą przekształcić szybką już wyszukiwanie na znacznie szybsze na trudniejszych instancjach zagadnień spełniających ograniczenia, nawet gdy barely mają znaczenie dla prostej N-Konie.

Po powrotnej śledzeniu

Dla bardzo dużych N wyszukiwanie lokalne wykazuje się lepiej niż systematyczne powrotne śledzenie: zaczynaj od umieszczenia wszystkich N królików (jeden na rzędzie i kolumnie, dopuszczając konflikty) i ponownie przesuwanie królika o największej liczbie konfliktów do kolumny, która minimalizuje te konflikty — forma wzgórz górskich nazywana min-conflicts. Rozwiązuje plansze z milionem królików w przybliżonym czasie liniowym, co stanowi ciekawą kontrast do wykładniczego worst case powrotnej śledzenia; to możliwe dlatego, że nigdy nie musi tworzyć rozwiązania stopniowo z pustej planszy; naprawia już pełny, ale zawodowy.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz N-Queens Problem i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.