Problem skoczka szachowego

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Próba rozwiązania problemu dla planszy 3x3

Problem skoczka szachowego – zadanie polegające na obejściu skoczkiem wszystkich pól planszy tak, żeby na każdym polu stanąć raz i tylko raz. Jeśli skoczek może po ostatnim ruchu wrócić na pole, z którego zaczynał, to mówimy o zamkniętej ścieżce skoczka szachowego. Jeśli skoczek może obejść wszystkie pola, ale po ostatnim ruchu nie może wrócić na startowe pole, to mówimy o ścieżce otwartej.

Rozwiązanie problemu dla plansz kwadratowych[edytuj | edytuj kod]

Dla planszy o wymiarach 3 na 3 skoczek może obejść osiem pól, ale na dziewiąte, środkowe nie może wskoczyć.

Na takiej planszy więc nie da się rozwiązać tego problemu. Dla planszy 4 na 4 też nie istnieje rozwiązanie. Ale dla wszystkich plansz kwadratowych o boku większym od czterech można znaleźć taką ścieżkę otwartą dla skoczka, żeby obszedł wszystkie pola dokładnie jeden raz.

Otwarta ścieżka dla planszy 8x8
Zamknięta ścieżka dla planszy 8x8


Zobacz też[edytuj | edytuj kod]

Bibliografia[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]

Wikimedia Commons