Jezdcova procházka
Jezdcova procházka je šachový a matematický problém popsaný pomocí šachové figury jezdce a šachovnice. Jezdec se pohybuje v souladu s šachovými pravidly po prázdné šachovnici a jeho úkolem je, aby každé pole navštívil právě jednou.
Problémem se zabývali již středověcí arabští a indičtí učenci a první řešení jsou známá již z 9. století. Mnoho variant jezdcovy procházky bylo a dosud je oblíbenou úlohou rekreační matematiky, ale také předmětem studia řady významných matematiků, například Eulera, Legendra nebo Vandermonda. Používají se různě velké šachovnice i různé varianty pohybu jezdce.
Na typické šachovnici 8 × 8 polí má úloha obrovské množství řešení, z nichž v přesně 26 534 728 821 064 případech jezdec končí na poli, odkud opět ohrožuje své startovní pole.[1]
Historie
Starověké počátky
Z Číny okolo roku 2200 př. n. l. je znám tzv. magický čtverec (tj. čtverec s očíslovanými poli, v němž součet číslic v jednotlivých řadách, sloupcích či hlavních diagonálách je vždy stejný) o 3 × 3 polích. Čtverec bylo možné projet figurou kombinující tahy tří kamenů používaných v tehdejší variantě šachové hry tak, aby svou procházku začala na poli s číslicí 1 a poté vzestupně pokračovala až k číslici 9, přičemž každé pole navštívila právě jednou. Použity byly tahy kamenů, jež by v pozdější asijské variantě šachu šatrandž odpovídaly pěšci (baidak, v asijských variantách šachu bez možnosti postoupit o 2 pole z počátečního postavení), vezíru (fers, předchůdce dnešní dámy, který ovšem mohl táhnout pouze o 1 pole diagonálně) a koni (faras, dnešní jezdec).[2]
Středověk
První zmínky o jezdcově procházce, jak ji známe dnes, pochází od arabských a indických učenců 9. století. Al-Ádlí popsal kolem roku 840 jezdcovu procházku ve své učebnici šachu, která se však nedochovala. Jeho řešení jezdcovy procházky tak známe díky jejímu popisu v rukopise jiného arabského učence al-Hakima. Al-Ádlího procházka je tzv. uzavřená (viz druhy řešení), takže umožňuje řešení z jakéhokoliv pole šachovnice. Ve stejném rukopise se vyskytuje ještě řešení mnohem méně známého hráče šachu Ali C. Maniho, které je však méně propracované – jezdec při procházce, která je otevřená, nejprve objíždí okraje, aby pak na závěr zakončil ve středu šachovnice.
Velmi známé je také řešení kašmírského básníka Rudraty někdy z konce 9. století. Rudrata se jezdcovou procházkou zabýval jen na polovině šachovnice, pokud však chceme procházku dokončit na celé šachovnici, stačí na její druhé polovině postup zopakovat. Toto řešení je popsáno i v perském rukopise z počátku 19. století. V sanskrtem psané encyklopedii Manasollasa z 12. století lze zase nalézt variantu, v níž řešení první poloviny šachovnice je na druhé polovině zopakováno, ovšem otočené o 180° (a mírně upraveno, aby na sebe obě poloviny mohly navázat).
Vzhledem k časové blízkosti těchto tří řešení jezdcovy procházky (z nichž dvě známe ze stejného rukopisu) nelze jednoznačně říci, které je starší. Je však velmi pravděpodobné, že tyto procházky měly své předchůdce, o nichž však historické prameny mlčí.[2]
Dalším arabským učencem, který se jezdcovou procházkou zabýval, byl Abu-Bakr Muhammad ben Yahya as-Súlí, jehož dílo se uchovalo zprostředkovaně v rukopisech jiných autorů. Zejména jedna ze dvou jeho jezdcových procházek je pozoruhodná – pokud myšlenou čarou rozdělíme šachovnici vodorovně na dvě poloviny, zjistíme, že jeho řešení je na obou polovinách téměř osově souměrné. As-Súlí sestavil také dvě procházky kombinující tahy jezdce a slona (alfil, předchůdce střelce, pohybující se o dvě pole diagonálně) a jezdce a vezíra (fers, pohybující se o jedno pole diagonálně).
V evropských pramenech lze první procházku nalézt až v anglo-normanském rukopisu z poslední čtvrtiny 13. století, uloženém v King's Library v Londýně. Podobně jako Rudratova procházka se skládá ze dvou na sebe navazujících procházek po obou polovinách šachovnice. Část řešení, které leží v pravé horní čtvrtině šachovnice, je navíc téměř úplnou jezdcovou procházkou po 4 × 4 polích, kdy pouze jednou jezdec namísto pole h6 navštíví pole g4 ležící mimo tuto oblast. Blíže se řešení jezdcovy procházky nelze na šachovnici 4 × 4 dostat.
V pařížské knihovně Bibliotheque de Paris se nachází latinský rukopis z první poloviny 14. století, který obsahuje sbírku šachových úloh Bonus Socius („Dobrý společník“). Jeho autor Nicolas de Nicolai zde představil verzi jezdcovy procházky, v níž je na polovině šachovnice rozestavěno určitým způsobem všech 32 šachových kamenů s bílým jezdcem v rohu. Jezdec má za úkol odebrat nejprve všechny figury kromě králů, potom všechny pěšce a teprve nakonec oba krále. Část, v níž jezdec odebírá figury, má jednoznačné řešení, ovšem pěšci mohou být odebráni šesti různými způsoby.[2]
Novověk
Šachové poznatky asijských středověkých učenců byly později v Evropě prakticky zapomenuty a evropští šachisté a matematici začínají šachovou procházku znovu objevovat až v 18. století. Roku 1725 vyšlo nové vydání staršího díla Jacquese Ozanama Recreations Mathematiques et Physiques, které obsahovalo tři jezdcovy procházky, připisované Jean-Jacquesi d'Ortous de Mairan (francouzskému matematikovi a řediteli Francouzské akademie věd), Abrahamu de Moivre a Pierru Rémondovi de Montmort. Jejich řešení však nedosahovala stejných kvalit jako o mnoho staletí starší procházky starověkých učenců. Všechny tyto tři jezdcovy procházky byly otevřené a zdaleka nebyly tak promyšlené a esteticky hodnotné jako např. řešení as-Súlího.
Roku 1759 Pruská akademie věd v Berlíně vypsala odměnu 4000 franků za nejlepší pojednání o problému jezdcovy procházky a téhož roku jí svou studii představil švýcarský matematik Leonhard Euler. Odměna však nebyla udělena, pravděpodobně proto, že Euler v té době zastával na akademii významné místo.
Euler, inspirovaný myšlenkami jiného švýcarského matematika L. Bertranda, ve své práci sestavil několik desítek jezdcových procházek. Mnoho z nich bylo navzájem souvisejícími variantami, které vytvářel pomocí nové metody rozpojení již existující sekvence jezdcovy procházky na vhodném místě a opětovného spojení na místě jiném. Zabýval se také symetrií jezdcových procházek a některá symetrická řešení opět pomocí své metody rozvinul do různých variant.
Euler také analyzoval některé možnosti procházek na menších šachovnicích. Dopustil se však chyby, když prohlásil, že uzavřenou procházku nelze sestavit na šachovnici o hraně menší než 5 polí, což byl omyl, který přežil více než jedno a půl století. Teprve roku 1917 ho vyvrátil Ernest Bergholt, který našel řešení uzavřené procházky na šachovnicích 3 × 10 a 3 × 12 polí.
Na konci 18. století pak jezdcovu procházku velmi zpopularizoval rakouský vynálezce Wolfgang von Kempelen, který cestoval po Evropě se svým údajným šachovým automatem Turek (ve skutečnosti ukrývajícím ve svých útrobách šachistu). Po Kempelenově smrti v těchto turné pokračoval Johann Nepomuk Mälzel, který se strojem procestoval i Spojené státy.[3]
Matematický popis a zobecnění
Jezdcova procházka je příkladem mnohem obecnějšího problému teorie grafů – nalezení hamiltonovské cesty v grafu. Tento problém je NP-úplný. Podobně, uzavřené řešení jezdcovy procházky je příkladem problému nalezení hamiltonovské kružnice. Na rozdíl od obecného problému je však problém jezdcovy procházky řešitelný v lineárním čase.[4]
Příslušný graf, v němž jsou hamiltonovské cesty hledány, je přitom určen následovně: Vrcholy jsou jednotlivá pole šachovnice a hrana mezi dvěma vrcholy vede právě tehdy, když se lze z prvého do druhého dostat jediným tahem jezdce. Nazvěme ho graf pohybu jezdce.
Řešení
Řešením problému jezdcovy procházky na dané šachovnici se nazývá každá posloupnost tahů jezdce splňující dvě základní podmínky:
- Každý tah je proveden podle šachových pravidel.
- Každé pole šachovnice je navštíveno právě jednou.
Ve výše uvedené matematické reprezentaci tedy řešení odpovídá cesta v grafu pohybu jezdce procházející všemi vrcholy.
Existence, případně počet řešení závisí jak na rozměrech zvolené šachovnice, tak na tom, zda jsou na řešení kladeny nějaké dodatečné podmínky.
Druhy řešení
Řešení se nazývá „uzavřené“, pokud se jezdec může z koncového pole jediným tahem dostat zpět na pole, z něhož vycházel a „uzavřít“ tak svoji cestu, tj. pokud příslušná cesta v grafu pohybu jezdce tvoří (po doplnění hrany mezi koncovým a počátečním polem) kružnici. Není-li řešení „uzavřené“, nazývá se „otevřené“.
Každou uzavřenou procházku lze provést dvěma směry. Považujeme-li tato dvě řešení za různá (tj. chápeme-li graf pohybu jezdce jako orientovaný), říkáme, že jsou to řešení „orientovaná“. V opačném případě, považujeme-li tato řešení za totožná (tj. graf pohybu jezdce chápeme jako neorientovaný), nazýváme řešení „neorientovaná“. Protože na každé neorientované řešení připadají právě dvě řešení orientovaná (dva způsoby, jak danou trasu procházet), je počet neorientovaných uzavřených řešení přesně polovinou počtu orientovaných uzavřených řešení.
Existence řešení
Podmínky řešitelnosti problému jezdcovy procházky pro obecné rozměry šachovnice stanovuje Schwenkova věta:
Pro jakoukoliv šachovnici o rozměrech m × n polí, kde m ≤ n, je uzavřené řešení jezdcovy procházky vždy možné, s výjimkou následujících případů:
- obě čísla m a n jsou lichá
- m = 1, 2 nebo 4; m a n nejsou současně obě rovna 1
- m = 3 a n = 4, 6, nebo 8
Důkaz Schwenkovy věty naleznete v samostatném článku.
Počty řešení
Čtvercové šachovnice
Na šachovnici 8 × 8 polí existuje přesně 13 267 364 410 532 neorientovaných uzavřených řešení. Na šachovnici 6 × 6 polí lze nalézt 9862 neorientovaných uzavřených řešení, na menších čtvercových šachovnicích žádná taková řešení nejsou.[5] Na šachovnici 5 × 5 polí existuje 1 728 otevřených řešení, na menších čtvercových šachovnicích už nelze nalézt ani žádné otevřené řešení.[5]
Šachovnice se čtyřmi řádky
Podle Schwenkovy věty neexistují na šachovnici mající čtyři řádky žádná uzavřená řešení jezdcovy procházky. Existují zde však řešení otevřená. Jejich počty na šachovnicích s rozměry 4 × n pro n ≤ 21 shrnuje následující tabulka.[6]
| Rozměry | otevřených řešení |
|---|---|
| 4 × 1 | 0 |
| 4 × 2 | 0 |
| 4 × 3 | 16 |
| 4 × 4 | 0 |
| 4 × 5 | 328 |
| 4 × 6 | 2976 |
| 4 × 7 | 25512 |
| 4 × 8 | 124352 |
| 4 × 9 | 758752 |
| 4 × 10 | 4852448 |
| 4 × 11 | 26735408 |
| 4 × 12 | 145945312 |
| 4 × 13 | 805129880 |
| 4 × 14 | 4334341216 |
| 4 × 15 | 22824469832 |
| 4 × 16 | 119276925152 |
| 4 × 17 | 617722010896 |
| 4 × 18 | 3163151197504 |
| 4 × 19 | 16059782780784 |
| 4 × 20 | 80965219241952 |
| 4 × 21 | 405344545960912 |
Šachovnice se třemi řádky
Počty řešení na šachovnici o rozměrech 3 × n pro některá n shrnuje následující tabulka.[5]
| Rozměry | otevřených řešení | uzavřených řešení |
|---|---|---|
| 3 × 1 | 0 | 0 |
| 3 × 2 | 0 | 0 |
| 3 × 3 | 0 | 0 |
| 3 × 4 | 16 | 0 |
| 3 × 5 | 0 | 0 |
| 3 × 6 | 0 | 0 |
| 3 × 7 | 104 | 0 |
| 3 × 8 | 792 | 0 |
| 3 × 9 | 1120 | 0 |
| 3 × 10 | chybí údaj | 8 |
| 3 × 11 | 21344 | 0 |
| 3 × 12 | chybí údaj | 28 |
Algoritmy
Backtracking
Nejjednodušším algoritmem pro nalezení řešení problému jezdcovy procházky je backtracking. Při něm jezdec skáče zcela libovolně na zatím neobsazená pole, dokud se neocitne v situaci, kde již nemůže táhnout dále. V takovém případě se vrátí o jeden tah zpět a pokračuje jinou cestou. Tento algoritmus je ale vzhledem k poměrně časté nutnosti vracet se ze „slepých uliček“ dosti pomalý.
Warnsdorffův algoritmus
První efektivnější algoritmus řešení jezdcovy procházky byl tzv. Warnsdorffův algoritmus, poprvé popsaný roku 1823 H. C. Warnsdorffem. V tomto algoritmu je za pole, na které jezdec potáhne, vybráno vždy to, z něhož lze dále pokračovat nejméně způsoby. Díky tomu jsou častěji obsazována pole, jež jsou již „téměř nedostupná“ a naopak zatím snadno dostupná pole se nechávají na později.
Warnsdorffův algoritmus pracuje pro malé šachovnice v lineárním čase (vzhledem k počtu polí). Pro šachovnice o rozměrech větších než 76 × 76 se však již stejně jako backtracking dostává velmi často do slepých uliček.[5]
Conradův algoritmus
První algoritmus pracující v lineárním čase pro všechny velikosti čtvercových šachovnic popsal v roce 1994 A. Conrad.[4] Algoritmus spočívá v dělení dané šachovnice na menší obdélníkové výseče, pro něž je řešení jezdcovy procházky známé.[5]
V kultuře
Již v 9. století použil princip jezdcovy procházky kašmírský básník Rudrata ve svém veršovaném sanskrtem psaném díle Kâvyâlankâra. Různé slabiky, napsané v šachovnicových polích, dávaly smysl pouze tehdy, když se při čtení sledoval vzor daný jezdcovou procházkou.[2] V současnosti se tento typ hádanky nazývá koníček.
Ve 20. století se jezdcovou procházkou inspirovali spisovatelé skupiny Oulipo. Nejznámějším příkladem je román francouzského spisovatele Georgese Pereca La Vie mode d'emploi z roku 1978. Perec v něm popisuje život v činžovním domě, který má 10 podlaží a v každém z nich je 10 místností. Každé místnosti je věnována jedna kapitola, přičemž děj se mezi místnostmi přesouvá podle vzoru jezdcovy procházky.
Odkazy
Reference
V tomto článku byl použit překlad textu z článku Knight's tour na anglické Wikipedii.
- ↑ WEGENER, I. Branching Programs and Binary Decision Diagrams. [s.l.]: Society for Industrial & Applied Mathematics, 01. 01. 1987. ISBN 0-898-71458-3. (anglicky)
- ↑ a b c d JELISS, George. Knight's Tour Notes [online]. 2000–2004 [cit. 2008-03-19]. Kapitola Early History of Knight's Tours. Dostupné online. (anglicky)
- ↑ JELISS, George. Knight's Tour Notes [online]. 2000–2004 [cit. 2008-03-19]. Kapitola Rediscovery of the Knight's Problem 1725 – 1825. Dostupné online. (anglicky)
- ↑ a b CONRAD, A., et al. Solution of the Knight's Hamiltonian Path Problem on Chessboards. Discrete Applied Math. 1994, roč. 50, čís. 2, s. 125–134. (anglicky)
- ↑ a b c d e WEISSTEIN, Eric W. Knight's tour [online]. MathWorld – A Wolfram Web Resource [cit. 2008-04-02]. Dostupné online. (anglicky)
- ↑ HEALY, Alex. Sequence A079312 [online]. [cit. 2008-03-18]. Dostupné online. (anglicky)
Literatura
- Watkins, John J. Across the Board: the Mathematics of Chessboard Problems. Princeton UP, 2004.
Související články
Externí odkazy
Obrázky, zvuky či videa k tématu Jezdcova procházka na Wikimedia Commons - Knight's tour notes – obsažné stránky věnované jezdcově procházce: historie, různé varianty, matematická teorie pro řešení problému (anglicky)
- The ultimate Knight's Tour page of Links Archivováno 6. 8. 2004 na Wayback Machine. – sbírka webových adres souvisejících s jezdcovou procházkou (anglicky)
- The knight's tour – možnost řešit úlohu online (anglicky)
- Warnsdorff's Rule – stránky věnované Warnsdorffovu algoritmu a jeho efektivitě (anglicky)
- 8 by 8 Knight's Tour strategy – popis jednoho z řešení problému jezdcovy procházky, které je snadno naučitelné nazpaměť (anglicky)
- Science World: modifikovaná verze úlohy s jezdcovou procházkou (česky)
