Nejdelší nekřížená cesta rytířů - Longest uncrossed knights path - Wikipedia
The nejdelší nekřížený (nebo neprotínající se) rytířská cesta je matematický problém zahrnující a rytíř na standardní 8 × 8 šachovnice nebo obecněji na náměstí n×n prkno. Problém je najít nejdelší cesta rytíř může vzít na danou tabuli tak, že se cesta neprotíná sama. Lze dále rozlišovat mezi a Zavřeno cesta, která končí na stejném poli jako tam, kde začíná, a otevřeno cesta, která končí na jiném poli, než kde začíná.
Známá řešení
Nejdelší otevřené cesty na nXn desky jsou známé pouze pro n ≤ 9. Jejich délky pro n = 1, 2, ..., 9 jsou:
Nejdelší uzavřené cesty jsou známé pouze pro n ≤ 10. Jejich délky pro n = 1, 2, ..., 10 jsou:
 |  |
| Nejdelší uzavřená cesta pro n = 7 o délce 24. | Nejdelší otevřená cesta pro n = 8 o délce 35. |
Zobecnění
Problém lze dále zobecnit na obdélníkový n×m desky, nebo dokonce na desky ve tvaru jakéhokoli polyomino. jiný standardní šachové figurky než rytíř jsou méně zajímavé, ale víla šachové figurky jako velbloud ((3,1) - později), žirafa ((4,1) - méně) a zebra ((3,2) - méně) vede k problémům srovnatelné složitosti.
Viz také
- A rytířské turné je protínající se rytířská cesta navštěvující všechna pole hrací plochy.
- TwixT, desková hra založená na nekřížených rytířských cestách.
Reference
- L. D. Yarbrough (1969). „Nekřížené rytířské zájezdy“. Časopis rekreační matematiky. 1 (3): 140–142.
- George Jelliss, Neprotínající se cesty
- Nepřekračující se rytířské zájezdy