vpravo|náhled|250px|Animace jezdcovy procházky 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.
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).
Středověk vpravo|náhled|Jezdcova procházka od al-Ádlího. 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-Hákima. 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čí.
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.
Novověk vpravo|náhled|250px|Jezdcova procházka, jak ji předváděl údajný šachový automat Turek Š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.
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.
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í vpravo|náhled|250px|Otevřená varianta řešení jezdcovy procházky Ř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 Počty orientovaných řešení na šachovnici o rozměrech n × n pro některá n shrnuje následující tabulka. rozměryotevřených řešeníuzavřených řešení1 × 1102 × 2003 × 3004 × 4005 × 5172806 × 66 637 92019 7247 × 7165 575 218 32008 × 819 591 828 170 979 90426 534 728 821 064
Š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 orientované počty na šachovnicích s rozměry 4 × n pro některá n shrnuje následující tabulka.
rozměry otevřených řešenírozměryotevřených řešení4 × 1 04 × 21202 672 272 980 4564 × 2 04 × 221 008 192 626 002 5444 × 3 164 × 234 987 067 296 004 9844 × 4 04 × 2424 540 946 112 970 7924 × 5 1644 × 25120 182 777 733 678 6484 × 6 1 4884 × 26585 963 673 826 712 9124 × 7 12 7564 × 272 845 274 471 022 031 2124 × 8 62 1764 × 2813 763 488 804 771 426 0884 × 9 379 3764 × 2966 343 070 395 932 985 5964 × 10 2 426 2244 × 30318 738 002 895 113 637 8644 × 11 13 367 7044 × 311 526 635 741 014 993 035 9684 × 12 72 972 6564 × 327 290 968 321 425 418 984 9764 × 13 402 564 9404 × 3334 726 476 427 504 151 753 8444 × 14 2 167 170 6084 × 34164 980 421 302 702 066 497 1364 × 15 11 412 234 9164 × 35781 924 347 362 947 213 376 5964 × 16 59 638 462 5764 × 363 697 574 334 808 700 267 867 3684 × 17 308 861 005 4484 × 3717 447 906 703 305 222 624 090 6364 × 18 1 581 575 598 7524 × 3882 166 367 320 637 491 720 650 5284 × 19 8 029 891 390 3924 × 39368 202 856 878 514 147 509 646 6764 × 20 40 482 609 620 9764 × 401 811 967 339 273 341 647 172 816 184
Šachovnice se třemi řádky Počty orientovaných řešení na šachovnici o rozměrech 3 × n pro některá n shrnuje následující tabulka.