Najdłuższa nieprzecięta ścieżka rycerska
Najdłuższa nieskrzyżowana (lub nieprzecinająca się ) ścieżka rycerza to problem matematyczny dotyczący skoczka na standardowej szachownicy 8 × 8 lub, bardziej ogólnie, na kwadratowej szachownicy n × n . Problem polega na znalezieniu najdłuższej ścieżki, którą rycerz może pokonać na danej planszy, tak aby ścieżka się nie przecinała. Można dokonać dalszego rozróżnienia między zamkniętą , która kończy się na tym samym polu, na którym się zaczyna, a ścieżką otwartą ścieżka, która kończy się na innym polu niż się zaczyna.
Znane rozwiązania
Najdłuższe otwarte ścieżki na tablicy n × n są znane tylko dla n ≤ 9. Ich długości dla n = 1, 2, …, 9 to:
Najdłuższe ścieżki zamknięte znane są tylko dla n ≤ 10. Ich długości dla n = 1, 2, …, 10 wynoszą:
|
|
|
Najdłuższa zamknięta ścieżka dla n = 7 o długości 24. |
Najdłuższa otwarta ścieżka dla n = 8 o długości 35. |
Uogólnienia
Problem można dalej uogólnić na prostokątne tablice n × m , a nawet na deski w kształcie dowolnego polyomino . Problem dla n × m , gdzie n nie przekracza 8, a m może być bardzo duży, został podany podczas światowych finałów ICPC 2018. Rozwiązanie wykorzystywało programowanie dynamiczne i wykorzystuje fakt, że rozwiązanie powinno wykazywać cykliczne zachowanie.
Inne standardowe figury szachowe niż rycerz są mniej interesujące, ale szachy wróżkowe, takie jak wielbłąd ((3,1)-skaczący), żyrafa ((4,1)-skaczący) i zebrowy ((3,2)-skaczący) prowadzą do problemów o porównywalnej złożoności.
Zobacz też
- Trasa rycerska to samoprzecinająca się ścieżka rycerska odwiedzająca wszystkie pola planszy.
- TwixT , gra planszowa oparta na nieskrzyżowanych ścieżkach rycerzy.
- LD Yarbrough (1968). „Nieskrzyżowane wyprawy rycerskie”. Dziennik matematyki rekreacyjnej . 1 (3): 140–142.
- George Jelliss, Nieprzecinające się ścieżki
- Nieprzekraczające wycieczki rycerskie
- Rozwiązania Światowych Finałów ICPC 2018 (Problem J)