Prohlídka rytířů - Knights tour - Wikipedia

Otevřená rytířská prohlídka šachovnice

Animace otevřené rytířské prohlídky na desce 5 × 5

A rytířské turné je sled tahů a rytíř na šachovnice tak, že rytíř navštíví každé náměstí přesně jednou. Pokud rytíř končí na čtverci, který je jedním rytířským tahem od počátečního čtverce (aby mohl okamžitě projít po desce po stejné cestě), je prohlídka uzavřena; jinak je otevřený.^[1][2]

The problém s rytířským turné je matematický problém najít rytířské turné. Vytváření a program najít rytířské turné je běžným problémem počítačová věda studenti.^[3] Variace rytířské cesty zahrnují šachovnice různých velikostí, než je obvyklé 8 × 8, stejně jako nepravidelné (ne obdélníkové) desky.

Teorie

Rytířský graf ukazující všechny možné cesty rytířské cesty na standardní šachovnici 8 × 8. Čísla na každém uzlu označují počet možných tahů, které lze z dané pozice provést.

Rytířský problém s prohlídkou je příkladem obecnějšího Problém hamiltonovské cesty v teorie grafů. Problém nalezení uzavřené rytířské cesty je obdobou případu Hamiltoniánský cyklus. Na rozdíl od obecného problému s hamiltoniánskou cestou lze problém rytířské cesty vyřešit v lineární čas.^[4]

Dějiny

Rytířská cesta, jak ji vyřešil Turek, podvod na šachy. Toto konkrétní řešení je uzavřené (kruhové) a lze jej tedy dokončit z kteréhokoli místa na desce.

Nejdříve známá zmínka o rytířském turné se datuje do 9. století našeho letopočtu. v Rudraṭa Kavyalankara^[5] (5.15), sanskrtské dílo Poetika, vzor rytířské cesty na polopenzi byl představen jako komplikovaná poetická postava (citra-alaṅkāra) volal turagapadabandha nebo „uspořádání v krocích koně“. Stejný verš ve čtyřech řadách po osmi slabikách lze číst zleva doprava nebo sledováním cesty rytíře na cestě. Protože Indické systémy psaní používané pro sanskrt jsou slabičné, každou slabiku lze považovat za představující čtverec na šachovnici. Příklad Rudraty je následující:

přepsáno:

Například první řádek lze číst zleva doprava nebo přesunutím z prvního čtverce do druhého řádku, třetí slabiky (2.3) a poté na 1,5 až 2,7 až 4,8 až 3,6 až 4,4 až 3,2.

The Sri Vaishnava básník a filozof Vedanta Desika během 14. století ve svém 10000 veršovém díle magnum chválil Pána Ranganatha božské sandály z Srirangam, tj. Paduka Sahasram (v kapitole 30: Chitra Paddhati) složil dva po sobě jdoucí Sanskrt verše obsahující každý 32 písmen (v Anushtubh metr), kde lze druhý verš odvodit z prvního verše provedením Rytířské prohlídky na a 4 × 8 deska, počínaje levým horním rohem.^[6] Přepsaný 19. verš je následující:

20. verš, který lze získat provedením Rytířského turné ve výše uvedeném verši, je následující:

sThi thA sa ma ya rA ja thpA

ga tha rA mA dha kE ga vi |

dhu běžel ha sAm sa nna thA dhA

sA dhyA thA pa ka rA sa rA ||

Předpokládá se, že Desika složila všech 1008 veršů (včetně speciálních Chaturanga Turanga Padabandham výše) za jedinou noc jako výzvu.^[7]

Prohlídka popsaná v páté knize Bhagavantabaskaraby od Bhata Nilakantha, cyklopedické dílo v sanskrtu o rituálu, právu a politice, napsané buď kolem roku 1600, nebo kolem roku 1700, popisuje tři rytířské cesty. Prohlídky jsou nejen opakované, ale také symetrické a verše jsou založeny na stejné prohlídce, počínaje různými čtverci.^[8] Dílo Bhata Nilakantha je mimořádným počinem, protože je plně symetrickým uzavřeným turné, které předcházelo Eulerovu práci (1759) nejméně o 60 let.

Jeden z prvních matematiků, kteří zkoumali rytířskou cestu, byl Leonhard Euler. Prvním postupem dokončení rytířské cesty bylo Warnsdorffovo pravidlo, poprvé popsané v roce 1823 H. C. von Warnsdorffem.

Ve 20. století se Oulipo skupina spisovatelů to mimo jiné používala. Nejpozoruhodnějším příkladem je 10 × 10 rytířská prohlídka, která určuje pořadí kapitol Georges Perec román Life a User's Manual.

Šestá hra Mistrovství světa v šachu 2010 mezi Viswanathan Anand a Veselin Topalov viděl Ananda dělat 13 po sobě jdoucích rytířských tahů (i když s použitím obou rytířů); online komentátoři žertovali, že se Anand během hry pokoušel vyřešit problém s rytířským turné.

Existence

Radiálně symetrická uzavřená rytířská cesta

Schwenk^[9] dokázal, že pro všechny m × n nastoupit s m ≤ n, uzavřená rytířská prohlídka je vždy možná pokud je splněna jedna nebo více z těchto tří podmínek:

1. m a n jsou oba zvláštní
2. m = 1, 2 nebo 4
3. m = 3 a n = 4, 6 nebo 8.

Vyřazeno et al. a Conrad et al. dokázal, že na každé obdélníkové desce, jejíž menší rozměr je alespoň 5, je (možná otevřená) rytířská prohlídka.^[4][10]

Počet prohlídek

Na 8 × 8 na palubě je přesně 26 534 728 821 064 režie uzavřené prohlídky (tj. dvě prohlídky po stejné cestě, které cestují v opačných směrech, se počítají zvlášť, stejně jako rotace a odrazy ).^[11][12][13] Počet neorientovaný uzavřených prohlídek je polovina tohoto počtu, protože každou prohlídku lze vysledovat obráceně. Existuje 9 862 neřízených uzavřených prohlídek na a 6 × 6 prkno.^[14]

Hledání prohlídek s počítači

Existuje několik způsobů, jak najít rytířskou prohlídku na dané desce s počítačem. Některé z těchto metod jsou algoritmy zatímco ostatní jsou heuristika.

Algoritmy hrubé síly

A vyhledávání hrubou silou pro rytíře je nepraktické na všech, kromě nejmenších desek.^[15] Například existuje přibližně 4 × 10⁵¹ možné sekvence pohybu na 8 × 8 prkno,^[16] a je daleko nad kapacitu moderních počítačů (nebo počítačových sítí) provádět operace na takové velké sadě. Velikost tohoto čísla však nenaznačuje obtížnost problému, který lze vyřešit „pomocí lidského vhledu a vynalézavosti ... bez větších obtíží“.^[15]

Algoritmy rozděl a panuj

Rozdělením desky na menší kousky, vytvořením zájezdů na každém kusu a opravením kousků dohromady můžete vytvořit zájezdy na většině obdélníkových desek v lineární čas - to znamená v čase úměrném počtu čtverců na desce.^[10][17]

Warnsdorffovo pravidlo

	A	b	C	d	E	F	G	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	A	b	C	d	E	F	G	h

Grafické znázornění Warnsdorffova pravidla. Každý čtverec obsahuje celé číslo udávající počet tahů, které rytíř mohl z tohoto čtverce provést. V tomto případě nám pravidlo říká, abychom se přesunuli na čtverec s nejmenším celým číslem, jmenovitě 2.

Velmi velká (130 × 130) čtvercová otevřená rytířská prohlídka vytvořená pomocí Warnsdorffova pravidla

Warnsdorffovo pravidlo je a heuristický za nalezení turné jediného rytíře. Rytíř se pohybuje tak, aby vždy postupoval na pole, ze kterého bude mít rytíř nejméně další pohyby. Při výpočtu počtu dalších tahů pro každý kandidátský čtverec nepočítáme tahy, které se vracejí k již navštívenému čtverci. Je možné mít dvě nebo více možností, u nichž je počet dalších tahů stejný; existují různé metody prolomení takových vazeb, včetně metody navržené Pohlem^[18] a další Veverka a Cull.^[19]

Toto pravidlo lze také obecněji použít na jakýkoli graf. Z graficko-teoretického hlediska je každý pohyb proveden do sousedního vrcholu s nejmenším stupeň.^[20] Ačkoliv Problém hamiltonovské cesty je NP-tvrdé obecně je na mnoha grafech, které se v praxi vyskytují, tato heuristika schopna úspěšně najít řešení v lineární čas.^[18] Rytířská cesta je takovým zvláštním případem.^[21]

The heuristický byl poprvé popsán v „Des Rösselsprungs einfachste und allgemeinste Lösung“ H. C. von Warnsdorffem v roce 1823.^[21]

Počítačový program, který najde rytířskou cestu pro jakoukoli výchozí pozici pomocí Warnsdorffova pravidla, napsal Gordon Horsington a byl publikován v roce 1984 v knize Uživatelská kniha počítačových hádanek Century / Acorn.^[22]

Řešení neuronových sítí

Uzavřená rytířská prohlídka na a 24 × 24 deska vyřešená neuronovou sítí

Rytířský problém s cestováním se také dá vyřešit pomocí a nervová síť implementace.^[23] Síť je nastavena tak, že každý legální rytířský tah je reprezentován a neuron, a každý neuron je inicializován náhodně buď jako „aktivní“ nebo „neaktivní“ (výstup 1 nebo 0), přičemž 1 znamená, že neuron je součástí řešení. Každý neuron má také stavovou funkci (popsanou níže), která je inicializována na 0.

Když je síť povolena, může každý neuron změnit svůj stav a výstup na základě stavů a ​​výstupů svých sousedů (těch, které se přesně vzdálí jednoho rytíře) podle následujících přechodových pravidel:

${ displaystyle U_ {t + 1} (N_ {i, j}) = U_ {t} (N_ {i, j}) + 2- součet _ {N v G (N_ {i, j})} V_ {t} (N)}$

${ displaystyle V_ {t + 1} (N_ {i, j}) = left {{ begin {array} {ll} 1 & { mbox {if}} , , U_ {t + 1} ( N_ {i, j})> 3 0 & { mbox {if}} , , U_ {t + 1} (N_ {i, j}) <0 V_ {t} (N_ {i, j}) & { mbox {jinak}}, end {pole}} vpravo.}$

kde ${ displaystyle t}$ představuje diskrétní časové intervaly, ${ displaystyle U (N_ {i, j})}$ je stav neuronového spojovacího čtverce ${ displaystyle i}$ na čtverec ${ displaystyle j}$, ${ displaystyle V (N_ {i, j})}$ je výstup neuronu z ${ displaystyle i}$ na ${ displaystyle j}$, a ${ displaystyle G (N_ {i, j})}$ je množina sousedů neuronu.

Ačkoli jsou možné odlišné případy, síť by se měla nakonec sblížit, což nastane, když žádný neuron časem nezmění svůj stav ${ displaystyle t}$ na ${ displaystyle t + 1}$. Když se síť sblíží, buď zakóduje rytířskou prohlídku, nebo sérii dvou nebo více nezávislých obvodů na stejné desce.

Varianty

	A	b	C	d	E	F	G	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	A	b	C	d	E	F	G	h

Obrázek 1: Bílý rytíř se při svém prvním tahu pohybuje z d1 na e3; d1 je nyní „spáleno“, což je označeno „X“, jedná se o čtverec, na který žádný rytíř nemůže po zbytek hry přistát.

	A	b	C	d	E	F	G	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	A	b	C	d	E	F	G	h

Obrázek 2: Možná pozice v koncovce. Teď je na řadě černý rytíř, ale nemá se kam pohnout, proto bílý rytíř vyhrává.

Klání

Klání je hráč pro dva hráče abstraktní strategie desková hra což lze považovat za variantu rytířského turné pro dva hráče. Lze jej také považovat za šachovou variantu.^[24][25] Používá kostkovanou desku 8 x 8 a dvě Šachoví rytíři jako jediné herní kousky. Každý hráč má jednoho rytíře jiné barvy než ten druhý. Rytíři se pohybují jako ve hře Šachy, ale pole, které opustí (po provedení tahu) se stane „spáleno“, to znamená, že na něj již nelze pohnout. Jak hra postupuje, je k dispozici k přesunutí méně čtverců. Cílem je zabránit tomu, aby rytíř soupeře provedl tah na svém tahu.

Gerry Quinn vytvořil freewarovou verzi hry a hru nazval Joust. Quinn to založil na starém Amiga Počítačová hra ve veřejné doméně (PD), i když si není jisté, zda se jedná o konečný původ hry, a jestli ji tak Amiga nazvala. Podle Quinna ve variantě Amiga začínají rytíři každého hráče ve středu hrací desky. V Quinnově variantě rytíři začínají na náhodném čtverci na opačných stranách desky.

Klání by nemělo být zaměňováno s 1982 videohra stejného jména.

Hra rytířů

Hra s názvem Amiga Hra rytířů vytvořený Charlesem N. Jacobem mohla být hra, na kterou Quinn odkazoval.^[26] Byla to sharewarová hra hraná na Amigově Workbench. Tato hra uvádí, že „Hra rytířů funguje na všech Amigách s Pracovní stůl 1.3 nebo vyšší ". Hra bohužel nezmiňuje, kdy byla vytvořena nebo vydána, proto není známo, zda předchází Quinnově verzi. Rytíři však začínají na opačných stranách desky, a ne ve středu desky, jak je výslovně uvedeno Quinn. K dispozici je také možnost, aby se rytíři navzájem zajali, a tak zvítězili alternativním způsobem. Hra je také částečně vyprávěna ve francouzštině a možná pochází z kanadského Quebecu, jak naznačují kontaktní údaje autora na kartě O aplikaci.

Existuje několik dalších variant, jako je misere verze, kde pokud váš rytíř nemůže provést legální tah, pak vyhrajete.^[24] Počáteční pozice může být také v jiné části desky, jako jsou rohy. Lze použít různé velikosti desek. Místo rytířů mohou být použity další šachové figurky, jako je král, královna, věž nebo biskup. Může být také přidán granát, to znamená, že se hráč může rozhodnout „vypálit“ další pole, které ještě nebylo spáleno a není aktuálně obsazeno. Granátování může být omezeno na typ šachové figurky použitý ve hře, například při hře s rytíři může hráč granovat pouze nespálený čtverec, což je rytířský krok pryč. Nebo se hráči mohou dohodnout na granátování jakéhokoli nespáleného čtverce, který není obsazen nikde na desce. Hráči se také mohou rozhodnout, zda by mělo být povoleno granátování před nebo po dokončení tahu.

Viz také

• Abu Bakr bin Yahya al-Suli
• George Koltanowski
• Nejdelší nekřížená rytířská cesta
• Osm královen puzzle

Poznámky

externí odkazy

• OEIS sekvence A001230 (počet neorientovaných uzavřených rytířských prohlídek na šachovnici 2 x X 2 n)
• H. C. von Warnsdorf 1823 v Knihách Google
• Úvod do rytířských zájezdů od George Jellissa
• Rytířské zájezdy doplňují poznámky George Jellissa
• Philip, Anish (2013). "Zobecněný pseudo-rytířský cestovní algoritmus pro šifrování obrazu". Potenciály IEEE. 32 (6): 10–16. doi:10.1109 / MPOT.2012.2219651.