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átan Á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:

1. m és n értéke egyaránt páratlan
2. m = 1, 2 vagy 4
3. 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:

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

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

További információk

• (A001230 sorozat az OEIS-ben)
• H. C. von Warnsdorf 1823 in Google Books
• Introduction to Knight's tours by George Jelliss
• Knight's tours complete notes by George Jelliss

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.