♛ Problem N hetmanów

Istnieje dokładnie 92 odrębne rozwiązania dla N=8. Uwzględniając tylko zasadniczo różne układy (usuwając obroty i odbicia planszy), istnieje 12 unikalnych rozwiązań. Dla N=1 istnieje trywialnie 1 rozwiązanie; N=2 i N=3 mają 0 rozwiązań; liczby rosną szybko: N=12 ma 14 200 rozwiązań, a N=15 ma 2 279 184.

Algorytm ustawia hetmany po jednym w każdym wierszu. Przed umieszczeniem hetmana w kolumnie sprawdza, czy ta kolumna lub którakolwiek przekątna jest już atakowana. Jeśli tak, pomija tę kolumnę. Gdy w danym wierszu nie ma żadnej poprawnej kolumny, algorytm cofa się do poprzedniego wiersza i próbuje tam następnej kolumny. To filtrowanie kolumn i przekątnych przycina nieprawidłowe gałęzie, zanim zostaną w pełni zbadane, redukując pracę z O(N!) do znacznie mniejszej w praktyce.

Decydowanie, czy częściowe ustawienie hetmanów można rozszerzyć do pełnego rozwiązania (problem "uzupełnienia N hetmanów") zostało wykazane jako NP-zupełne przez Genta, Jeffersona i Nightingale'a w 2017 roku. Jednak znalezienie jednego rozwiązania standardowego problemu N hetmanów (wszystkich N hetmanów ustawionych od zera) można wykonać w czasie O(N) za pomocą konstrukcji w postaci zamkniętej, więc wariant uzupełnienia jest ściśle trudniejszy niż standardowy problem.

Istnieje kilka jawnych konstrukcji O(N). Jedna wynika z jawnego wzoru: jeśli N mod 6 ≠ 2 i N mod 6 ≠ 3, ustaw hetmany w kolumnach 2, 4, 6, …, N, 1, 3, 5, …, N−1 (najpierw parzyste kolumny, potem nieparzyste). Specjalne uporządkowania obsługują przypadki N mod 6 = 2 i mod 6 = 3. Te konstrukcje dają jedno poprawne rozwiązanie bez żadnego nawracania, co jest przydatne, gdy potrzebne jest tylko jedno rozwiązanie, a nie wszystkie 92 (lub ile ich jest).

Naiwne przeszukiwanie z nawracaniem znajduje wszystkie 92 rozwiązania dla N=8. Wykorzystując 8-elementową grupę symetrii kwadratu (4 obroty × 2 odbicia), wystarczy przeszukać tylko pierwszą połowę pierwszego wiersza (kolumny 1-4), a następnie odbić każde znalezione rozwiązanie, redukując przeszukiwanie o czynnik około 8. To łamanie symetrii jest standardem w przeszukiwaniu kombinatorycznym i programowaniu z ograniczeniami.

Forward checking to technika przewidywania: po ustawieniu hetmana algorytm natychmiast usuwa wszystkie atakowane komórki z dziedzin (dostępnych kolumn) przyszłych wierszy. Jeśli dziedzina jakiegokolwiek przyszłego wiersza stanie się pusta, bieżąca gałąź jest natychmiast przycinana, zamiast czekać, aż ten wiersz zostanie osiągnięty. Dla N hetmanów odpowiada to śledzeniu trzech wektorów bitowych: jednego dla atakowanych kolumn, jednego dla atakowanych lewych przekątnych i jednego dla atakowanych prawych przekątnych.

Tak. Klasyczny solver oparty na manipulacji bitowej (Martin Richards, 1997) reprezentuje atakowane kolumny, lewe przekątne i prawe przekątne jako pojedyncze liczby całkowite i wykorzystuje bitowe AND, OR oraz przesunięcia do obliczania dostępnych pozycji. Każde ustawienie to pojedynczy bit wyczyszczony z maski dostępnych kolumn; nawracanie przywraca maskę. Pozwala to nowoczesnym procesorom eksplorować miliony pozycji na sekundę i znaleźć wszystkie 92 rozwiązania dla N=8 w mikrosekundach.

Problem N hetmanów jest wykorzystywany jako test porównawczy dla solverów ograniczeń i przeszukiwania równoległego. Systemy programowania z ograniczeniami, takie jak Choco, Gecode i OR-Tools, zawierają go jako standardowy przypadek testowy. Leżąca u podstaw technika — umieszczanie niekonfliktowych elementów na strukturalnej siatce — ma odpowiedniki w projektowaniu układów VLSI (umieszczanie niewzajemnie zakłócających się elementów obwodu), planowaniu (przydzielanie nienakładających się przedziałów czasowych) oraz przewidywaniu struktury drugorzędowej RNA.

Dokładna liczba rozwiązań Q(N) rośnie w przybliżeniu wykładniczo; ciąg ten to OEIS A000170. Q(20) = 39 029 188 884, a Q(27) = 234 907 967 154 122 528. Dla N ≥ 28 dokładne liczby nie zostały opublikowane od 2024 roku; samo obliczenie Q(28) wymagałoby obliczeń na skalę petaflopów. Szacunki asymptotyczne sugerują Q(N) ≈ (0,143 N)^N, ale dokładna asymptotyka pozostaje otwartym problemem badawczym.

Rozwiązanie problemu N hetmanów, w którym hetmany zajmują też odrębne łamane przekątne (przekątne toroidalne owijające się wokół planszy), nazywane jest rozwiązaniem "toroidalnym" lub "modularnym" N hetmanów i odpowiada transwersalowi cyklicznego kwadratu łacińskiego. Takie rozwiązania istnieją tylko dla N niepodzielnego przez 2 ani 3. To powiązanie łączy kombinatorykę, teorię grup i projektowanie ortogonalnych kwadratów łacińskich używanych w projektowaniu eksperymentów statystycznych.

Dla każdej kolumny próbuje wierszy od góry do dołu, sprawdzając, czy nowy hetman dzieli wiersz lub przekątną z jakimkolwiek już ustawionym hetmanem. Używany jest pierwszy znaleziony bezpieczny wiersz, a przeszukiwanie przechodzi do następnej kolumny.

Jeśli każdy wiersz koliduje z istniejącym hetmanem, algorytm się cofa: usuwa poprzedniego hetmana i kontynuuje od następnego wiersza w tamtej kolumnie, co właśnie liczy statystyka "Nawroty".

Liczba sposobów ustawienia N hetmanów rośnie w przybliżeniu wykładniczo wraz z rozmiarem planszy — N=8 ma 92 rozwiązania, N=12 ma 14 200 — a liczba kroków nawracania potrzebnych do ich znalezienia rośnie jeszcze szybciej.

Żółty oznacza testowanego hetmana, zielony oznacza hetmany potwierdzone jako bezpieczne, czerwony podświetla konflikt z wcześniejszym hetmanem, a niebieski błysk oznacza każdą kolumnę wypełnioną bez konfliktu.

Pozostawiony uruchomiony, kontynuuje nawracanie po każdym rozwiązaniu, aby szukać kolejnych, aż całe drzewo przeszukiwania zostanie wyczerpane, więc licznik "Znalezione rozwiązania" zlicza każdy poprawny układ dla wybranego N.