Problem ośmiu hetmanów
Problem ośmiu hetmanów polega na ustawieniu ośmiu hetmanów na szachownicy tak, aby żadne dwa się nie atakowały. Kompozytor szachowy Max Bezzel opublikował go w 1848 roku i stał się on klasycznym pierwszym przykładem przeszukiwania z powrotami.
Łamigłówka szachowa z 1848 roku
Max Bezzel, niemiecki kompozytor szachowy, przedstawił ten problem w berlińskim czasopiśmie szachowym w 1848 roku. Franz Nauck opublikował wszystkie 92 rozwiązania w 1850 roku i zadał to samo pytanie dla większych plansz. Carl Friedrich Gauss śledził ten problem z zainteresowaniem i omawiał go w swoich listach.
Jeden hetman na wiersz i kolumnę
Osiem hetmanów, które się nie atakują, musi stać w ośmiu różnych wierszach i ośmiu różnych kolumnach. Rozwiązanie jest więc przetasowaniem liczb od 1 do 8, czyli permutacją, z jedną dodatkową zasadą: żadne dwa hetmany nie mogą stać na jednej przekątnej. Z 40 320 permutacji przechodzi tylko 92.
Algorytm z powrotami
Algorytm z powrotami buduje rozwiązanie kawałek po kawałku i cofa się, gdy tylko trafi w ślepy zaułek. Dla hetmanów: postaw hetmana na pierwszym bezpiecznym polu następnego wiersza, a gdy w wierszu nie ma bezpiecznego pola, wróć do wiersza powyżej i przesuń tamtego hetmana dalej. W 1972 roku Edsger Dijkstra użył tego problemu, aby wyjaśnić programowanie strukturalne właśnie na takim przeszukiwaniu.
Symetria
Obróć planszę o ćwierć obrotu albo ją odbij, a rozwiązanie pozostanie rozwiązaniem. Daje to do ośmiu wersji każdego rozwiązania. 92 rozwiązania dzielą się na 12 takich rodzin: jedenaście po 8 członków i jedną, która ma tylko 4, bo to rozwiązanie wygląda tak samo po pół obrotu.
Problem n hetmanów
Na planszy n×n pytanie jest takie samo, tylko z n hetmanami. Rozwiązania istnieją dla każdego n od 4 wzwyż, a ich liczba szybko rośnie: 2 dla 4×4, 92 dla 8×8 i 14 200 dla 12×12. Nie jest znany żaden wzór na tę liczbę; rekordowe wartości pochodzą z dużych przeszukiwań komputerowych.
Wypróbuj w PictorX
Otwórz Osiem hetmanów i kliknij pole, aby postawić hetmana; kliknij je ponownie, aby go zdjąć. Pokaż ataki oznacza kropką pola atakowane przez twoje hetmany, a czerwone hetmany atakują się nawzajem. Rozwiąż uruchamia przeszukiwanie z powrotami krok po kroku i zachowuje postawione przez ciebie hetmany. Następne rozwiązanie przechodzi po kolei przez wszystkie rozwiązania, a Rozmiar zmienia planszę od 4×4 do 12×12.
Często zadawane pytania
Kto wymyślił problem ośmiu hetmanów?
Max Bezzel, niemiecki kompozytor szachowy, w 1848 roku. Franz Nauck opublikował pierwszy pełny zestaw rozwiązań w 1850 roku.
Ile jest rozwiązań?
92 na standardowej szachownicy. Jeśli obroty i odbicia liczy się jako jedno, jest ich 12.
Dlaczego plansza 6×6 ma tak mało rozwiązań?
Ma tylko 4, wszystkie z jednej rodziny. Mniejsza plansza 5×5 ma 10. Większe plansze mają coraz więcej: 40 na 7×7 i 92 na 8×8.
Czy PictorX coś wysyła?
Nie. Plansza jest rysowana na płótnie w przeglądarce. Zapisz pobiera PNG, a Edytuj otwiera ten obraz w edytorze PictorX.
Powiązane narzędzia
Osiem hetmanów
Ustaw osiem hetmanów na szachownicy tak, aby żaden nie atakował innego. Spróbuj sam, obejrzyj, jak przeszukiwanie z powrotami krok po kroku znajduje rozwiązanie, i przejrzyj wszystkie 92 rozwiązania.
Trasa skoczka
Poprowadź skoczka szachowego przez każde pole planszy dokładnie raz. Graj sam z podpowiedziami Warnsdorffa albo patrz, jak Rozwiąż kończy trasę otwartą lub zamkniętą. Zapisz ścieżkę jako PNG.
Trasa skoczka szachowego
Historia i matematyka trasy skoczka: Euler i Warnsdorff, trasy otwarte i zamknięte, dlaczego plansze nieparzyste nie mają trasy zamkniętej i jak komputer ją znajduje.
Wieże Hanoi
Przenieś w przeglądarce wieżę z krążków między trzema prętami. Po jednym krążku, nigdy większy na mniejszy. Najkrótsze rozwiązanie to 2ⁿ − 1 ruchów.
Wieże Hanoi
Wieże Hanoi: trzy pręty, jeden krążek naraz i nigdy większy na mniejszym. Najkrótsze rozwiązanie to 2ⁿ−1 ruchów. Édouard Lucas przedstawił łamigłówkę w 1883 roku.
Mrówka Langtona
Uruchom mrówkę Langtona w przeglądarce. Zobacz symetrię, chaos i autostradę o cyklu 104 kroków, a potem wypróbuj reguły wielokolorowe, kilka mrówek, siatkę sześciokątną i turmity.
Chcesz wypróbować?
Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.
Wypróbuj Osiem hetmanów