Problém tahu rytíře

Problémem tahu jezdce  je problém najít cestu šachového jezdce , který jednou projde všemi políčky šachovnice .

Tento problém je znám přinejmenším od 18. století . Leonhard Euler jí věnoval velké dílo „Řešení kuriózní otázky, která, jak se zdá, nepodléhá žádnému výzkumu“, z roku 1759 [1] . V dopise Goldbachovi [2] uvedl:

... Vzpomínka na problém, který mi byl kdysi navržen, mi nedávno posloužila jako příležitost k nějakému subtilnímu výzkumu, ve kterém obyčejná analýza, zdá se, nemá smysl... Konečně jsem našel jasný způsob, jak najít co nejvíce řešení, jak se mi líbí (jejich počet však není nekonečný), bez zkoušení.

Problémové prohlášení

Z hlediska teorie grafů každá cesta rytíře přes všechna pole šachovnice odpovídá hamiltonovské cestě (nebo cyklu, je-li cesta uzavřena) v grafu , jehož vrcholy jsou čtverce šachovnice a dvě pole jsou spojena hrana, pokud se člověk může dostat z jednoho na druhého jedním tahem koně.

Pro desku 8 × 8 je počet všech uzavřených rytířských cest (hamiltonských cyklů) bez zohlednění směru obchvatu 13 267 364 410 532 [3] . Počet všech otevřených tras (s přihlédnutím ke směru obchvatu) je 19 591 828 170 979 904.

Metody řešení

Eulerova metoda

Eulerova metoda spočívá v tom, že nejprve se rytíř pohybuje po libovolné trase, dokud nevyčerpá všechny možné tahy. Poté jsou zbývající buňky, které neprošly, přidány do vytvořené trasy po speciální permutaci jejích prvků.

Jako příklad zvažte následující cestu:

55 58 29 40 27 44 19 22
60 39 56 43 třicet 21 26 45
57 54 59 28 41 osmnáct 23 dvacet
38 51 42 31 osm 25 46 17
53 32 37 A 47 16 9 24
padesáti 3 52 33 36 7 12 patnáct
jeden 34 5 48 b čtrnáct C deset
čtyři 49 2 35 6 jedenáct d 13

Nejprve zkusme udělat uzavřenou trasu z otevřené trasy. Chcete-li to provést, zvažte, kam můžete přejít z polí 1 a 60. Z pole 1 můžete přejít na pole 2, 32 a 52 a od 60 do 29, 51 a 59. V těchto dvou sadách jsou pole, která se liší o jednu , konkrétně - 51 a 52. Díky tomu můžete trasu uzavřít obrácením její části. Chcete-li to provést, přečíslujte pole z 52 na 60 v opačném pořadí. Poté dostaneme uzavřenou trasu:

57 54 29 40 27 44 19 22
52 39 56 43 třicet 21 26 45
55 58 53 28 41 osmnáct 23 dvacet
38 51 42 31 osm 25 46 17
59 32 37 A 47 16 9 24
padesáti 3 60 33 36 7 12 patnáct
jeden 34 5 48 b čtrnáct C deset
čtyři 49 2 35 6 jedenáct d 13

Nyní můžete do trasy zahrnout některé z neprojetých buněk. Vzhledem k tomu, že naše trasa je uzavřená, lze ji na libovolném místě přerušit a na jeden z konců připevnit vhodný řetězec neprojetých buněk. Pokud například přerušíme řetězec v buňce 51 (přečíslováním buněk a tím, že bude poslední a 52 jako první), můžeme náš řetězec rozšířit o buňky a , b a d , ze kterých se stanou buňky 61, 62 a 63.

Vandermondova metoda

Vandermonde se pokusil zredukovat problém na aritmetiku. Za tímto účelem označil cestu rytíře podél šachovnice jako posloupnost zlomků x / y , kde x a y  jsou souřadnice pole na šachovnici. Je zřejmé, že v posloupnosti zlomků odpovídajících tahům jezdce může být rozdíl mezi čitateli dvou sousedních zlomků pouze 1 nebo 2, přestože rozdíl mezi jejich jmenovateli je 2 nebo 1. Navíc, čitatel a jmenovatel nesmí být menší než 1 a větší než 8 .

Jeho metoda pro nalezení vhodné sekvence je podobná Eulerově metodě, ale umožňuje pouze nalezení rytířských cest pro desky sudých rozměrů.


Warnsdorfovo pravidlo

Warnsdorfovo pravidlo , které je jakýmsi chamtivým algoritmem pro nalezení cesty rytíře, je formulováno následovně:

Při obcházení hrací plochy se rytíř řídí polem, ze kterého je možné přejít na minimální počet polí, která ještě neprošli. Pokud existuje několik takových polí, můžete přejít na kterékoli z nich.

Dlouho se věřilo, že Warnsdorffovo pravidlo funguje bezchybně. Později byla s pomocí počítačů zjištěna nepřesnost v jeho druhé části: je-li více vhodných polí, pak nejsou všechna stejná a svévolná volba pole může koně zavést do slepé uličky. V praxi je však pravděpodobnost, že se dostanete do slepé uličky, malá i při volném použití druhé části Warnsdorffova pravidla. [čtyři]

Pozoruhodné cesty

Janischova cesta

padesáti jedenáct 24 63 čtrnáct 37 26 35
23 62 51 12 25 34 patnáct 38
deset 49 64 21 40 13 36 27
61 22 9 52 33 28 39 16
48 7 60 jeden dvacet 41 54 29
59 čtyři 45 osm 53 32 17 42
6 47 2 57 44 19 třicet 55
3 58 5 46 31 56 43 osmnáct
Janischova cesta

Trasa koně, kterou našel K. A. Yanish , tvoří polokouzelný čtverec , a když se deska otočí o 180°, přechází první polovina trasy (čísla od 1 do 32) do druhé (čísla od 33 do 64 ). Trasa, která je skutečným magickým čtvercem, pro desku 8 × 8 neexistuje [5] .

Turkova cesta

Šachový automat "Turk" předvedl uzavřenou cestu rytíře, znázorněnou na schématu vpravo.

Mnemotechnická báseň

S rytířem můžete objet všechna šachová pole jednou, kromě toho to můžete udělat „naslepo“, na přání „diváka“ začínající nebo končící na libovolném poli, můžete postupovat podle básně: [6]

Reddens podzim s hodnotnými dárky,
Další životodárný den.
Chlebové červené žluté šňůry,
Filosofický baldachýn Crystal Waters.

Dva večery ulpívající pupeny
Umělec napsal, Bezdonna Sineva.
Road Slag Kiss Worms,
Stále pokrytý Phlox Grass.

Kouří čaj Efektivní čokoláda,
Porcelánové šálky dostanou tři,
Blondýnka Dana Joy
Forshmak Divide se studenou hranou.

Manželka tlačí křehkou přítelkyni
Chce točit tento víkend
Ocenění samotné arktické vánice,
Hodí melounovou kouli do čtyř.

Cicada Heel, sotva břichomluvec,
Dává Sandman Window Ficusovi.
I když jsou žízniví po čaji spokojeni,
Majitel Noisily Daruje víno.

Foxtrot Šest dívek v zajetí,
Variety tance jsou fantastickější než táta,
Vyšlo sotva krokující kuře,
A toulavý drak je pryč.

Tělo bronzové osiky zčervená,
Vládne stíny prolamovaná délka.
Tichý než pneumatiky auta
Swamp Vítr dává semena.

Lucerna Osm chimér září,
Brouk přilétá, tleská, tam.
Žádoucí podzim, pokud se dokončí
Nejcennější zbytek veselé práce.

První písmena určují souřadnice tahů:

Aleet podzim = A1; Hodnotné dary = C2; atd.

Do každé sloky je vložena nápověda, aby nedošlo k záměně posloupnosti sloek: JEDNOU ještě, DVA večery, TŘI dostanu atd.

Zobecnění na libovolné desky

Uzavřené trasy

Počet uzavřených tras s přihlédnutím ke směru je dvojnásobný. Uzavřené trasy existují na deskách pro všechny sudé (sekvence A001230 v OEIS ).

Otevřené trasy

Pro nečtvercové desky existuje neuzavřená jízda rytířů pouze tehdy, jsou-li splněny následující podmínky: je-li jedna strana desky 3, pak druhá strana musí být buď 4, nebo alespoň 7; jsou-li obě strany větší než 3, pak lze rytíře obejít na všech prknech kromě 4 × 4. Zejména na čtvercových prknech pro všechny existují neuzavřené cesty . [7] Počet otevřených cest na deskách tvoří sekvenci A165134 v OEIS .

Viz také

Poznámky

  1. ↑ Euler, Leonhard, Solution d'une question curieuse que ne paroit soumise à aucune analysis Archivováno 30. září 2017 ve Wayback Machine , Mémoires de l'académie des sciences de Berlin, 15 (1759) 1766, s. 310-337.
  2. ↑ Jak to Euler dokázal archivovat 8. srpna 2017 na Wayback Machine .
  3. ↑ Brendan McKay. Rytířské prohlídky na šachovnici 8x8  (neurčeno)  // Technická zpráva TR-CS-97-03. — Department of Computer Science, Australian National University, 1997. Archivováno z originálu 28. září 2013.
  4. ↑ E. Geek. Kapitola 2. Chameleonský kůň // Šachy a matematika . - M. : Nauka, 1983. - (Knihovna "Quantum").
  5. ↑ Eric W. Weisstein, Na šachovnici nejsou žádné kouzelné rytířské prohlídky Archivováno 8. září 2017 na Wayback Machine , MathWorld Headline News.
  6. ↑ V. Panov. Tajemství jednoho triku  // Věda a život . - 1969. - č. 5 .
  7. ↑ A. Conrad, T. Hindrichs, H. Morsy, I. Wegener. Řešení úlohy hamiltonovské cesty rytíře na šachovnicích   // Discr . Appl. Matematika. : deník. - 1994. - Sv. 50 . - str. 125-134 . - doi : 10.1016/0166-218X(92)00170-Q .

Odkazy