O trasie skoczka | Reguła Warnsdorffa, trasy otwarte i zamknięte

Stara łamigłówka

W dziele Kavyalankara, które w IX wieku napisał indyjski poeta Rudrata, pewien wers jest rozpisany na połowie szachownicy tak, że można go odczytać wzdłuż drogi skoczka. Leonhard Euler napisał pierwsze matematyczne studium trasy skoczka w 1759 roku, z metodami budowania tras i zamieniania ich w trasy zamknięte.

Ścieżka w grafie

Wyobraź sobie każde pole jako punkt, a każdy ruch skoczka jako linię między dwoma punktami. Trasa skoczka jest wtedy ścieżką, która odwiedza każdy punkt dokładnie raz, co matematycy nazywają ścieżką Hamiltona; trasa zamknięta to cykl Hamiltona. W większości sieci taką ścieżkę bardzo trudno znaleźć. Sieć skoczka jest hojna: ma tak wiele tras, że dobra reguła szybko znajduje jedną z nich.

Reguła Warnsdorffa

H. C. von Warnsdorff opisał swoją regułę w 1823 roku: zawsze skacz na pole, które zostawia najmniej dalszych ruchów. Pola przy krawędzi mają mało sąsiadów, więc reguła odwiedza je wcześnie, zamiast zostawiać je odcięte. Gdy dwa pola remisują, trzeba wybrać, a pechowy wybór wciąż może sprawić, że skoczek utknie. W aplikacji złote liczby oznaczają pola, które wybrałaby reguła.

Przeszukiwanie z nawrotami

Rozwiąż trzyma się kolejności Warnsdorffa, ale nie ufa jej ślepo. Przeszukuje w głąb i gdy tylko do któregoś nieodwiedzonego pola nie da się już dotrzeć, porzuca tę gałąź i próbuje następnego ruchu. Na planszach do 10×10 zwykle od razu znajduje trasę. Gdy twoja własna ścieżka zamknęła skoczka w pułapce, najpierw cofa się o kilka ruchów.

Kolory i trasy zamknięte

Każdy ruch skoczka zmienia kolor pola. Na nieparzystej planszy, takiej jak 5×5, jest o jedno pole więcej w kolorze rogów niż w drugim kolorze, więc trasa musi zaczynać się i kończyć na kolorze rogów. Trasa zamknięta jest tam niemożliwa, bo pętla, w której kolory się przeplatają, ma tyle samo pól każdego koloru. Na parzystych planszach trasy zamknięte istnieją od 6×6 wzwyż.

Wypróbuj w PictorX

Otwórz Trasę skoczka i kliknij pole, żeby zacząć. Podświetlone pola to dozwolone skoki, złota liczba to wybór Warnsdorffa, a plansza zapamiętuje kolejność twoich ruchów. Rozmiar ustawia planszę od 5×5 do 10×10, „Trasa zamknięta” każe przyciskowi Rozwiąż szukać pętli, a Cofnij cofa dowolny ruch. Zapisz gotową ścieżkę jako PNG.

Często zadawane pytania

Kto pierwszy badał trasę skoczka?

Trasy znano na długo przedtem, zanim ktokolwiek zbadał je matematycznie. Leonhard Euler napisał pierwsze matematyczne opracowanie w 1759 roku, a Warnsdorff podał swoją regułę w 1823 roku.

Czy trasa istnieje na każdej planszy?

Kwadratowe plansze od 5×5 wzwyż mają trasy otwarte, a parzyste od 6×6 wzwyż mają też trasy zamknięte. Plansze 2×2, 3×3 i 4×4 nie mają żadnej trasy.

Ile tras ma szachownica?

Jest 26 534 728 821 064 tras zamkniętych, jeśli trasę i tę samą trasę przebytą wstecz liczy się osobno. Liczba tras otwartych to około 19,6 biliarda.

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.