Huszárvándorlás-probléma

A huszárvándorlás-probléma, huszárkörút vagy sakktábla bejárása huszárral egy huszár lépéssorozata a 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.^[1] 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

A huszárkörút-probléma egy sajátos Hamilton-út-probléma a gráfelméletbő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.^[2]

Története

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^[3] (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ő:

से	ना	ली	ली	ली	ना	ना	ली
ली	ना	ना	ना	ना	ली	ली	ली
न	ली	ना	ली	ले	ना	ली	ना
ली	ली	ली	ना	ना	ना	ना	ली

átírva

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.^[2]^[4]

Körutak száma

Egy 8×8-as táblán pontosan 26 534 728 821 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.^[5]

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 637 920; 165 575 218 320; 19 591 828 170 979 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 algoritmikusak, mások csak heurisztikák.

Brute force-algoritmusok

A brute force-módszer (kimerítő keresés) a gyakorlatban csak a legkisebb táblaméreteken alkalmazható;^[6] például egy 8×8-as táblán mintegy 4·10⁵¹ lépéssorozat lehetséges,^[7] 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ó."^[6]

„Oszd meg és uralkodj” módszerek

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ó.^[4]^[8]

Megoldás neurális hálózattal

A huszárvándorlás-probléma jól megoldható neurális hálózat segítségével is.^[9] 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:

U_{t+1}(N_{i,j})=U_{t}(N_{i,j})+4-\sum _{N\in G(N_{i,j})}V_{t}(N)

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.

ahol $t$ diszkrét időintervallumot jelképez, $U(N_{i,j})$ pedig az $i$ mezőt $j$ mezővel összekötő neuron állapota, $V(N_{i,j})$ az $i$ -t $j$ -vel összekötő neuron kimenete, $G(N_{i,j})$ 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 $t$ és $t+1$ 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

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,^[10] illetve a Squirrel és Cull^[11] á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ú 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ó.^[10] A huszárvándorlás-probléma ennek egy speciális esete.^[12]

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.^[12] 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.^[13]

Jegyzetek

↑ Deitel, H. M.; Deitel, P. J. (2003). Java How To Program Fifth Edition (5th ed.). Prentice Hall. 326–328. o. ISBN 978-0131016217.
1 2 Conrad, A.; Hindrichs, T.; Morsy, H.; Wegener, I. (1994). "Solution of the Knight's Hamiltonian Path Problem on Chessboards". Discrete Applied Mathematics. 50 (2): 125–134. doi:10.1016/0166-218X(92)00170-Q. {{cite journal}}: Unknown parameter |lastauthoramp= ignored (|name-list-style= suggested) (súgó)
↑ Satyadev, Chaudhary. Kavyalankara of Rudrata (Sanskrit Text, with Hindi translation);. Delhitraversal: Parimal Sanskrit Series No. 30.
1 2 Cull, P.; De Curtins, J. (1978). "Knight's Tour Revisited" (PDF). Fibonacci Quarterly. 16: 276–285.
↑ Weisstein, Eric W. "Knight's Tour" (angol nyelven). Wolfram MathWorld.
1 2 Simon, Dan (2013), Evolutionary Optimization Algorithms, John Wiley & Sons, 449–450. o, ISBN 9781118659502, The knight's tour problem is a classic combinatorial optimization problem. ... The cardinality N_x of x (the size of the search space) is over 3.3×10¹³ (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.
↑ "Enumerating the Knight's Tour".
↑ Parberry, Ian (1997). "An Efficient Algorithm for the Knight's Tour Problem" (PDF). Discrete Applied Mathematics. 73: 251–260. doi:10.1016/S0166-218X(96)00010-8. 2013. szeptember 27. dátummal az eredeti (PDF) címről archiválva. Hozzáférés: 2017. április 5.
↑ Y. Takefuji, K. C. Lee. "Neural network computing for knight's tour problems." Neurocomputing, 4(5):249–254, 1992.
1 2 Pohl, Ira (1967. július). "A method for finding Hamilton paths and Knight's tours". Communications of the ACM. 10 (7): 446–449. doi:10.1145/363427.363463.
↑ Squirrel, Douglas; Cull, P. (1996). "A Warnsdorff-Rule Algorithm for Knight's Tours on Square Boards" (PDF). Hozzáférés: 2011. augusztus 21.
1 2 Alwan, Karla; Waters, K. (1992). Finding Re-entrant Knight's Tours on N-by-M Boards (PDF). ACM Southeast Regional Conference. New York, New York: ACM. 377–382. o. doi:10.1145/503720.503806. Hozzáférés: 2008. október 28.
↑ Dally, Simon (ed.). Century/Acorn User Book of Computer Puzzles. ISBN 071260541X.

További információk

A Wikimédia Commons tartalmaz Huszárvándorlás-probléma témájú médiaállományokat.

Fordítás

Ez a szócikk részben vagy egészben a Knight's tour című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Informatikai portál • összefoglaló, színes tartalomajánló lap

[1] Deitel, H. M.; Deitel, P. J. (2003). Java How To Program Fifth Edition (5th ed.). Prentice Hall. 326–328. o. ISBN 978-0131016217.

[Conrad1994-2] 1 2 Conrad, A.; Hindrichs, T.; Morsy, H.; Wegener, I. (1994). "Solution of the Knight's Hamiltonian Path Problem on Chessboards". Discrete Applied Mathematics. 50 (2): 125–134. doi:10.1016/0166-218X(92)00170-Q. {{cite journal}}: Unknown parameter |lastauthoramp= ignored (|name-list-style= suggested) (súgó)

[3] Satyadev, Chaudhary. Kavyalankara of Rudrata (Sanskrit Text, with Hindi translation);. Delhitraversal: Parimal Sanskrit Series No. 30.

[Cull1978-4] 1 2 Cull, P.; De Curtins, J. (1978). "Knight's Tour Revisited" (PDF). Fibonacci Quarterly. 16: 276–285.

[5] Weisstein, Eric W. "Knight's Tour" (angol nyelven). Wolfram MathWorld.

[Simon01a-6] 1 2 Simon, Dan (2013), Evolutionary Optimization Algorithms, John Wiley & Sons, 449–450. o, ISBN 9781118659502, The knight's tour problem is a classic combinatorial optimization problem. ... The cardinality N_x of x (the size of the search space) is over 3.3×10¹³ (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.

[7] "Enumerating the Knight's Tour".

[8] Parberry, Ian (1997). "An Efficient Algorithm for the Knight's Tour Problem" (PDF). Discrete Applied Mathematics. 73: 251–260. doi:10.1016/S0166-218X(96)00010-8. 2013. szeptember 27. dátummal az eredeti (PDF) címről archiválva. Hozzáférés: 2017. április 5.

[9] Y. Takefuji, K. C. Lee. "Neural network computing for knight's tour problems." Neurocomputing, 4(5):249–254, 1992.

[pohl-10] 1 2 Pohl, Ira (1967. július). "A method for finding Hamilton paths and Knight's tours". Communications of the ACM. 10 (7): 446–449. doi:10.1145/363427.363463.

[11] Squirrel, Douglas; Cull, P. (1996). "A Warnsdorff-Rule Algorithm for Knight's Tours on Square Boards" (PDF). Hozzáférés: 2011. augusztus 21.

[alwan-waters-12] 1 2 Alwan, Karla; Waters, K. (1992). Finding Re-entrant Knight's Tours on N-by-M Boards (PDF). ACM Southeast Regional Conference. New York, New York: ACM. 377–382. o. doi:10.1145/503720.503806. Hozzáférés: 2008. október 28.

[13] Dally, Simon (ed.). Century/Acorn User Book of Computer Puzzles. ISBN 071260541X.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]