Huszárvándorlás-probléma forrásának megtekintése

A '''huszárvándorlás-probléma''', '''huszárkörút''' vagy '''sakktábla bejárása huszárral''' egy [[Huszár (sakk)|huszár]] lépéssorozata a [[sakktábla|sakktáblán]], amely alatt a huszár a tábla minden mezőjét pontosan egyszer érinti. Ha az utolsó mező megegyezik a kiinduló mezővel, a körút zárt, másképp a körút nyitott.

A sakktábla bejárása huszárral matematikai probléma. Olyan [[algoritmus]] létrehozása, mely megkeresi ezt a bejárást, ismert számítástechnikai feladat.<ref>{{cite book|first1=H. M.|last1=Deitel|first2=P. J.|last2=Deitel|title=Java How To Program Fifth Edition.|url=https://archive.org/details/javahowtoprogram00deit_1|publisher=[[Prentice Hall]]|isbn=978-0131016217|edition=5th|pages=[https://archive.org/details/javahowtoprogram00deit_1/page/326 326]–328|date=2003}}</ref> A huszárkörút problémája különböző méretű sakktáblákon fennáll, nemcsak a 8×8-ason, sőt a szabálytalan (nem téglalap) alakú táblákon is.

== Elmélet ==
[[Fájl:Knight's_graph_showing_number_of_possible_moves.svg|balra|bélyegkép|270x270px|A grafikon megmutatja a huszárkörút minden lehetséges változatát egy szabványos 8x8-as sakktáblán. A csomópontok számai a lehetséges lépések számát jelzik abból a pozícióból.]]
A huszárkörút-probléma egy sajátos [[Hamilton-út]]-probléma a [[gráfelmélet]]ből. A zárt huszárkörút megtalálása hasonló a [[Hamilton-kör]] problémájához. A Hamilton-út problémájától eltérően a huszárkörutat meg lehet oldani lineáris időben.<ref name="Conrad1994">{{Cite journal|last=Conrad|first=A.|year=1994|title=Solution of the Knight's Hamiltonian Path Problem on Chessboards|journal=Discrete Applied Mathematics|volume=50|issue=2|pages=125–134|doi=10.1016/0166-218X(92)00170-Q|first2=T.|last2=Hindrichs|first3=H.|last3=Morsy|lastauthoramp=yes|first4=I.|last4=Wegener}}</ref>

== Története ==
[[Fájl:Turk-knights-tour.svg|bélyegkép|250x250px|A huszár útja, Turk megoldása. Ez az egyéni megoldás zárt típusú (kör típusú), és így a tábla bármely pontján befejezhető]]
A legkorábbi ismert említése a huszárkörút problémájának a 9. századba nyúlik vissza. [[Rudrata]] ''Kavyalankara''<ref>{{cite book|author=Satyadev, Chaudhary|title=Kavyalankara of Rudrata (Sanskrit Text, with [[Hindi]] translation);|publisher=Parimal Sanskrit Series No. 30|location=Delhitraversal}}</ref> (5.15) c., szanszkrit nyelvű költészeti munkájában egy huszárkörút mintája egy fél táblán úgy van ábrázolva, mint bonyolult poétikai ábra ''(citra-alaṅkāra)'', ''turagapadabandha'' vagy ''rendezés huszárlépésben'' néven. Ugyanazt a verset négy, egyenként nyolc szótagos sorban el lehet olvasni balról jobbra vagy követve a huszárkörút vonalát. Mivel a szanszkrit átírására használt indiai írásrendszer szótag alapú, minden szótag egy mezőt jelenthet a sakktáblán. Rudrata példája a következő:
{| style="border:0; text-align:center;"
|से
|ना
|ली
|ली
|ली
|ना
|ना
|ली
|-
|ली
|ना
|ना
|ना
|ना
|ली
|ली
|ली
|-
|न
|ली
|ना
|ली
|ले
|ना
|ली
|ना
|-
|ली
|ली
|ली
|ना
|ना
|ना
|ना
|ली
|}

átírva

{| style="border:0; text-align:center;"
|se
|nā
|lī
|lī
|lī
|nā
|nā
|lī
|-
|lī
|nā
|nā
|nā
|nā
|lī
|lī
|lī
|-
|na
|lī
|nā
|lī
|le
|nā
|lī
|nā
|-
|lī
|lī
|lī
|nā
|nā
|nā
|nā
|lī
|}

Például az első sor olvasható balról jobbra vagy az első négyzetből a 2. sor 3. szótagjára (2.3) lépve, majd 1.5 – 2.7 – 4.8 – 3.6 – 4.4 – 3.2.

Az első matematikusok egyike, aki a huszárkörúttal kísérletezett, [[Leonhard Euler]] volt. Az első eljárás a huszárkörút megtalálására a Warnsdorf-szabály volt, amelyet 1823-ban írt le  H. C. von Warnsdorf.

A 20. században többek között az [[Oulipo]] írók csoportja is használta. A legjelentősebb példa a 10×10-es huszárkörút, amely meghatározza a fejezetek sorrendjét [[Georges Perec]] ''[[La Vie mode d’emploi]]'' regényében. A [[2010-es sakkvilágbajnokság]] döntőjében, [[Visuvanádan Ánand]] és [[Veszelin Topalov]] között, a 6. játszmában Anand 13 egymást követő huszárlépést tett (igaz, mindkét huszárt használva); online kommentátorok azon tréfálkoztak, hogy Anand a játék során a huszárkörút problémáját próbálta megoldani.

== Létezés ==
Schwenk bebizonyította, hogy minden m×n-es táblán, ahol m≤n, mindig létezik egy zárt huszárkörút, ''kivéve'', ha az alábbi feltételek valamelyike igaz:
# ''m'' és ''n'' értéke egyaránt páratlan
# ''m'' = 1, 2 vagy 4
# ''m'' = 3 és ''n'' = 4, 6 vagy 8.
Cull és munkatársai, valamint Conrad és munkatársai bebizonyították, hogy minden téglalap alakú táblán, amelynek a kisebbik mérete legalább 5, létezik egy (esetleg nyitott) huszárkörút.<ref name="Conrad1994" /><ref name="Cull1978">{{cite journal|last=Cull|first=P.|year=1978|title=Knight's Tour Revisited|journal=Fibonacci Quarterly|volume=16|pages=276–285|url=http://www.fq.math.ca/Scanned/16-3/cull.pdf|author2=De Curtins, J.}}</ref>

== Körutak száma ==
Egy 8×8-as táblán pontosan 26&nbsp;534&nbsp;728&nbsp;821&nbsp;064 irányított zárt körút létezik. Az irányítatlan zárt körutak száma ennek a fele, mivel mindegyik körút fordítva is bejárható. Egy 6×6-os táblán 9862 irányítatlan zárt körút van.<ref>{{MathWorld|urlname=KnightsTour|title=Knight's Tour}}</ref>

Az irányított nyitott körutak száma egy n×n-es táblán, ahol n = 1, 2, … :
: 1; 0; 0; 0; 1728; 6&nbsp;637&nbsp;920; 165&nbsp;575&nbsp;218&nbsp;320; 19&nbsp;591&nbsp;828&nbsp;170&nbsp;979&nbsp;904.

== Körutak megtalálása számítógéppel ==
Számos módszer létezik a huszárvándorlás-probléma adott méretű táblán történő megoldására. Egyes módszerek [[algoritmus|algoritmikusak]], mások csak heurisztikák.

=== Brute force-algoritmusok ===
[[File:Knight's Tour of 130x130 Square Board.png|thumb|A Warnsdorf-szabály alapján létrehozott hatalmas (130×130-as) négyzetes nyitott huszárvándorlás.]]
A [[brute force-módszer]] (kimerítő keresés) a gyakorlatban csak a legkisebb táblaméreteken alkalmazható;<ref name=Simon01a>{{citation|title=Evolutionary Optimization Algorithms|first=Dan|last=Simon|publisher=John Wiley & Sons|year=2013|isbn=9781118659502|pages=449–450|url=https://books.google.com/books?id=gwUwIEPqk30C&pg=PA449|quote=The knight's tour problem is a classic combinatorial optimization problem. ... The cardinality ''N<sub>x</sub>'' of ''x'' (the size of the search space) is over 3.3×10<sup>13</sup> (Löbbing and Wegener, 1995). We would not want to try to solve this problem using brute force, but by using human insight and ingenuity we can solve the knight's tour without much difficulty. We see that the cardinality of a combinatorial optimization problem is not necessarily indicative of its difficulty.}}</ref> például egy {{nowrap|8×8}}-as táblán mintegy 4{{e|51}} lépéssorozat lehetséges,<ref>{{cite web |url=http://www.josiahland.com/?p=781 |title = Enumerating the Knight's Tour}}</ref> ami jóval meghaladja a modern számítógépek (vagy akár számítógép-hálózatok) lehetőségeit. Ennek a számnak a mérete azonban megtévesztő a feladat nehézségére nézve, ami „az emberi belátás és találékonyság segítségével […] különösebb nehézség nélkül megoldható."<ref name=Simon01a/>

=== „Oszd meg és uralkodj” módszerek ===
[[Divide et impera (informatika)|Oszd meg és uralkodj]]-algoritmus segítségével, tehát a tábla kisebb részekre való osztásával, a kisebb részeken a huszárkörút megszerkesztésével, majd ezek összefűzésével, a feladat a legtöbb téglalap alakú táblán [[polinom idő]]ben megoldható.<ref name=Cull1978/><ref>{{cite journal|last = Parberry|first = Ian|title = An Efficient Algorithm for the Knight's Tour Problem|journal = Discrete Applied Mathematics|volume = 73|year = 1997|pages = 251–260|doi = 10.1016/S0166-218X(96)00010-8|url = http://larc.unt.edu/ian/pubs/algoknight.pdf|accessdate = 2017-04-05|archiveurl = https://web.archive.org/web/20130927194856/http://larc.unt.edu/ian/pubs/algoknight.pdf|archivedate = 2013-09-27}}</ref>

=== Megoldás neurális hálózattal ===
[[Fájl:Knight's_Tour_24x24.svg|bélyegkép|250x250px|Neurális hálózattal talált, zárt huszárkörút egy 24×24-es táblán]]
A huszárvándorlás-probléma jól megoldható [[neurális hálózat]] segítségével is.<ref>Y. Takefuji, K. C. Lee. "Neural network computing for knight's tour problems." ''Neurocomputing'', 4(5):249–254, 1992.</ref> A hálózat úgy van összerakva, hogy minden érvényes huszárlépést egy [[mesterséges neuron]] reprezentál, melyek kezdeti állapota véletlenszerűen „aktív” vagy „inaktív” (1 vagy 0 kimenet), ahol az 1 érték arra utal, hogy a neuron része a végső megoldásnak. Minden neuron rendelkezik egy (alább leírt) állapotfüggvénnyel, melynek kezdeti értéke 0.

A hálózat futtatásakor minden neuron megváltoztathatja az állapotát a (pontosan egy huszárlépésre lévő) szomszédai állapotai és kimenetei alapján, a következő szabályok szerint:

::<math>
U_{t+1} (N_{i,j}) = U_t(N_{i,j}) + 4 - \sum_{N \in G(N_{i,j})} V_t(N)
</math>

::<math>
V_{t+1} (N_{i,j}) = \left\{
\begin{array}{ll}
1 & \mbox{ha}\,\, U_{t+1}(N_{i,j}) > 3\\
0 & \mbox{ha}\,\, U_{t+1}(N_{i,j}) < 0\\
V_t(N_{i,j}) & \mbox{egyébként},
\end{array} \right.
</math>

ahol <math>t</math> diszkrét időintervallumot jelképez, <math>U(N_{i,j})</math> pedig az <math>i</math> mezőt <math>j</math> mezővel összekötő neuron állapota, <math>V(N_{i,j})</math> az <math>i</math>-t <math>j</math>-vel összekötő neuron kimenete, <math>G(N_{i,j})</math> pedig a neuron szomszédainak halmaza.

Bár divergáló esetek elvileg elképzelhetők, a hálózatnak végül konvergálnia kell; ez akkor történik meg, ha <math>t</math> és <math>t+1</math> között egy neuron sem változtat állapotot. Ha a hálózat konvergált, az eredményül kapott hálózat vagy huszárvándorlást kódol, vagy két (esetleg több) egymástól független huszárvándorlást ugyanazon a táblán.

=== Warnsdorf-szabály ===
{{Sakkdiagram
| tright
|
|  |  |  |  |  |  |  |  
|  |  |  |  |  |  |  |  
|x3|  |x7|  |  |  |  |  
|  |  |  |x7|  |  |  |  
|  |nl|  |  |  |  |  |  
|  |  |  |x7|  |  |  |  
|x2|  |x5|  |  |  |  |  
|  |  |  |  |  |  |  |  
|A Warnsdorf-szabály grafikus ábrázolása. A mezőkre írt szám azt mondja meg, hány helyre léphet a huszár az adott mezőről. Ebben az esetben a szabály azt írja elő, hogy a legkisebb számot tartalmazó, tehát a 2-essel jelölt mezőre lépjünk.}}

A Warnsdorf-szabály a huszárvándorlás megtalálására alkalmazott [[heurisztika]]. A huszárral mindig olyan mezőre igyekszünk lépni, melyre a lehető legkevesebbféleképpen lehet lépni. Amikor a szóba jövő mezők lehetséges bejövő lépéseinek számát kalkuláljuk, nem vesszük figyelembe a már meglátogatott mezőkről kiinduló lépéseket. Természetesen kialakulhatnak döntetlenek, ezek feloldására több módszer létezik, köztük a Pohl,<ref name="pohl" /> illetve a Squirrel és Cull<ref>{{cite web|url=https://github.com/douglassquirrel/warnsdorff/blob/master/5_Squirrel96.pdf?raw=true |title=A Warnsdorff-Rule Algorithm for Knight's Tours on Square Boards |accessdate=2011-08-21 |last=Squirrel |first=Douglas |author2=Cull, P.  |year=1996 }}</ref> által kidolgozottak.

A szabály általánosabban bármely gráfra alkalmazható. Gráfelméleti fogalmakkal operálva, minden lépés a legalacsonyabb [[fokszám (gráfelmélet)|fokszámú]] szomszédos csúcsra történik. Bár a [[Hamilton-út probléma]] általánosságban [[NP-nehéz]], számos, a gyakorlatban előforduló gráfon ezzel a heurisztikával [[lineáris idő]]ben megoldható.<ref name="pohl">{{cite journal|last = Pohl|first = Ira|title = A method for finding Hamilton paths and Knight's tours|journal = Communications of the ACM|volume = 10|issue = 7|date = July 1967|pages = 446–449|url =http://portal.acm.org/citation.cfm?id=363463|doi = 10.1145/363427.363463}}</ref> A huszárvándorlás-probléma ennek egy speciális esete.<ref name="alwan-waters">{{cite conference| first=Karla |last=Alwan|author2=Waters, K. | title=Finding Re-entrant Knight's Tours on N-by-M Boards|conference=ACM Southeast Regional Conference| publisher=[[Association for Computing Machinery|ACM]]| location=New York, New York| pages=377–382| year=1992| url=http://portal.acm.org/citation.cfm?id=503806#.pdf| accessdate=2008-10-28| doi = 10.1145/503720.503806}}</ref>

A heurisztikát elsőként H. C. von Warnsdorf írta le 1823-ban megjelent "Des Rösselsprungs einfachste und allgemeinste Lösung" c. írásában.<ref name="alwan-waters" />
A problémát tetszőleges kiindulási helyzetből a Warnsdorf-szabályt használva megoldó számítógépi programot Gordon Horsington publikálta 1984-ben a ''Century/Acorn User Book of Computer Puzzles'' c. könyvben.<ref>{{cite book|title=Century/Acorn User Book of Computer Puzzles|editor-first=Simon|editor-last=Dally|ISBN=071260541X}}</ref>

== Jegyzetek ==
{{jegyzetek}}

== További információk ==
{{Commonskat|Knight's Tours}}
* {{OEIS|A001230}}
* [https://books.google.com/books?id=w5FZAAAAYAAJ&printsec=frontcover&dq=h.+c.+von+warnsdorf&hl=en&sa=X&ei=2QZmU9-jJIaXO8-hgKgL&ved=0CDEQ6AEwAA#v=onepage&q=h.%20c.%20von%20warnsdorf&f=false H. C. von Warnsdorf 1823 in Google Books]
* [http://www.mayhematics.com/t/1n.htm Introduction to Knight's tours by George Jelliss]
* [http://www.mayhematics.com/t/t.htm Knight's tours complete notes by George Jelliss]

== Fordítás ==
{{fordítás|en|Knight's tour|oldid=773806848}}

[[Kategória:Sakktörténelem]]
[[Kategória:Gráfelmélet]]
[[Kategória:Gráfalgoritmusok]]
[[Kategória:Hamilton-utak és -körök]]
[[Kategória:Matematikai problémák]]