A lovagmozgás problémája

A lovag lépésének  problémája az, hogy megtaláljuk az útvonalat egy sakklovagnak , aki egyszer áthalad a tábla összes mezőjén.

Ez a probléma legalább a 18. század óta ismert . Leonhard Euler egy 1759-es nagyszabású munkáját szentelte neki: "Egy különös kérdés megoldása, amely, úgy tűnik, semmiféle kutatásnak nem tárgya" [1] . Goldbachnak [2] írt levelében a következőkről számolt be:

... Egy valamikor felvetett probléma felidézése alkalmat adott a közelmúltban néhány finom kutatásra, amelyben a hétköznapi elemzésnek, úgy tűnik, nincs haszna... Végre találtam egy világos módot, hogy minél többet megtaláljak. tetszőleges megoldásokat (számuk azonban nem végtelen), próbák nélkül.

Problémafelvetés

A gráfelmélet szempontjából a lovag minden egyes útvonala a sakktábla összes négyzetén keresztül megfelel egy Hamilton-útnak (vagy egy ciklusnak, ha az útvonal zárt) egy gráfban , amelynek csúcsai a tábla négyzetei, és két mezőt egy él, ha egy ló mozdulatával egyikből a másikba kerülhet.

Egy 8 × 8-as táblánál az összes lezárt lovagi útvonal (Hamilton-ciklusok) száma az elkerülő út irányának figyelembevétele nélkül 13 267 364 410 532 [3] . Az összes nyitott útvonal száma (az elkerülő irányt figyelembe véve) 19 591 828 170 979 904.

Megoldási módszerek

Euler-módszer

Euler módszere szerint először a lovag egy tetszőleges útvonalon mozog, amíg az összes lehetséges lépést ki nem meríti. Ezután a megmaradt, át nem hagyott cellákat hozzáadjuk az elkészített útvonalhoz, annak elemeinek speciális permutációja után.

Tekintsük a következő útvonalat példaként:

55 58 29 40 27 44 19 22
60 39 56 43 harminc 21 26 45
57 54 59 28 41 tizennyolc 23 húsz
38 51 42 31 nyolc 25 46 17
53 32 37 a 47 16 9 24
ötven 3 52 33 36 7 12 tizenöt
egy 34 5 48 b tizennégy c tíz
négy 49 2 35 6 tizenegy d 13

Először próbáljunk meg egy nyitott útvonalból zárt útvonalat készíteni. Ehhez fontolja meg, hogy az 1-es és 60-as mezőkből merre léphet. Az 1-es mezőből a 2-es, 32-es és 52-es mezőbe, valamint a 60-ból 29-be, az 51-es és 59-es mezőbe. Ebben a két halmazban vannak olyan mezők, amelyek eggyel különböznek. , nevezetesen - 51 és 52. Ennek köszönhetően az útvonal egy részének megfordításával lezárhatóvá tehető. Ehhez fordított sorrendben számozza át a mezőket 52-ről 60-ra. Ezt követően egy zárt útvonalat kapunk:

57 54 29 40 27 44 19 22
52 39 56 43 harminc 21 26 45
55 58 53 28 41 tizennyolc 23 húsz
38 51 42 31 nyolc 25 46 17
59 32 37 a 47 16 9 24
ötven 3 60 33 36 7 12 tizenöt
egy 34 5 48 b tizennégy c tíz
négy 49 2 35 6 tizenegy d 13

Most már beilleszthet néhány be nem járt cellát az útvonalba. Mivel az útvonalunk zárt, tetszőleges helyen megszakítható, és az egyik végére megfelelő, át nem járt cellák lánca rögzíthető. Például, ha megszakítjuk a láncot az 51-es cellában (a cellák átszámozásával és utolsóvá tételével, elsőként pedig az 52-vel), meghosszabbíthatjuk a láncunkat a , b és d cellákkal, amelyekből a 61, 62 és 63 cellák lesznek.

Vandermonde módszer

Vandermonde megpróbálta aritmetikára redukálni a feladatot. Ehhez a lovag útvonalát a tábla mentén x / y törtek sorozataként jelölte meg , ahol x és y  a tábla mezőjének koordinátái. Nyilvánvaló, hogy a lovag mozdulatainak megfelelő törtek sorában két szomszédos tört számlálóinak különbsége csak 1 vagy 2 lehet, annak ellenére, hogy a nevezőik közötti különbség 2, illetve 1. Ráadásul a számláló és a nevező nem lehet 1-nél kisebb és 8-nál nagyobb.

A megfelelő sorozat megtalálásának módszere hasonló Euler módszeréhez, de csak páros dimenziós táblák esetén teszi lehetővé a lovagok útjainak megtalálását.


Warnsdorf- szabály

A Warnsdorf-szabály , amely egyfajta mohó algoritmus a lovag útvonalának megtalálására, a következőképpen fogalmazódik meg:

A tábla megkerülésekor a lovag azt a mezőt követi, ahonnan a minimális számú, még át nem haladt mezőre lehet menni. Ha több ilyen mező van, akkor bármelyikbe léphet.

Sokáig azt hitték, hogy a Warnsdorff-szabály hibátlanul működik. Később számítógépek segítségével a második részében pontatlanságot állapítottak meg: ha több alkalmas mező van, akkor nem mindegyik egyenlő, és egy tetszőleges mezőválasztás zsákutcába vezetheti a lovat. A gyakorlatban azonban a Warnsdorff-szabály második részének szabad felhasználása mellett is kicsi a zsákutcába kerülés valószínűsége. [négy]

Nevezetes útvonalak

Janisch útvonal

ötven tizenegy 24 63 tizennégy 37 26 35
23 62 51 12 25 34 tizenöt 38
tíz 49 64 21 40 13 36 27
61 22 9 52 33 28 39 16
48 7 60 egy húsz 41 54 29
59 négy 45 nyolc 53 32 17 42
6 47 2 57 44 19 harminc 55
3 58 5 46 31 56 43 tizennyolc
Janisch útvonal

A ló útvonala, amelyet K. A. Yanish talált , egy félig varázslatos négyzetet alkot , és ha a táblát 180°-kal elfordítják, az útvonal első fele (1-től 32-ig terjedő számok) átmegy a másodikba (33-tól 64-ig terjedő számok). ). Az útvonal, amely egy igazi varázsnégyzet, nem létezik a 8 × 8 táblánál [5] .

Török útvonala

A „Török” sakkgép a lovag zárt útvonalát mutatta be, a jobb oldali ábrán látható.

Mnemonikus vers

A lovaggal egyszer körbejárhatod az összes sakkmezőt, emellett megteheted „vakon”, a „néző” kérésére bármelyik mezőn kezdve vagy befejezve, követheted a verset: [6]

Értékes ajándékokkal pirosítja az őszt,
Újabb életadó nap.
Kenyérvörösök sárga zsinórok,
Crystal Waters filozófiai lombkorona.

Két este kapaszkodó rügyek
Művész írta, Bezdonna Sineva.
Road Slag Kiss Worms,
Még mindig Phlox fűvel borított.

Füstöli a tea hatékony csokoládét,
Három porcelánpohár,
Szőke lány Dana Joy
Forshmak Divide hideg éllel.

Feleség nyomja törékeny barátnője
Ezen a hétvégén szeretne forgatni
Magát a sarkvidéki hóvihart értékelve,
Négynek dob egy görögdinnye labdát.

Kabócasarok, alig beszélő,
Sandman ablakot ad Ficusnak.
Bár a teára szomjazók elégedettek,
A tulajdonos Noisily bort adományoz.

Foxtrot Six Girls magával ragadott,
A változatos táncok fantasztikusabbak, mint apa,
Alig lépő csirke jött ki,
És a Wandering Drake eltűnt.

A bronznyárfa teste pirosra vált,
Reigns Shadows áttört hossza.
Csendes, mint az autógumik
A mocsári szél magokat ad.

Nyolc lámpás kiméra ragyog,
Bogár érkezik, taps, ott.
Kívánatos ősz, ha befejeződik
A vidám munka legértékesebb maradéka.

Az első betűk a mozdulatok koordinátáit állítják be:

Aleet Autumn = A1; Értékes ajándékok = C2; stb.

Minden versszakba beillesztenek egy tippet, hogy ne keverjék össze a strófák sorrendjét: még EGY, KÉT este, HÁROM értem stb.

Általánosítás tetszőleges táblákra

Lezárt útvonalak

A lezárt útvonalak száma az irányt figyelembe véve kétszer akkora. Zárt útvonalak léteznek a táblákon minden páros számára ( A001230 sorozat az OEIS -ben ).

Útvonalak megnyitása

A nem négyzet alakú táblák esetében a nem zárt lovagi séta csak akkor létezik, ha a következő feltételek teljesülnek: ha a tábla egyik oldala 3, akkor a másik oldala 4 vagy legalább 7 legyen; ha mindkét oldal nagyobb, mint 3, akkor a lovag minden táblán megkerülhető, kivéve a 4 × 4-et. Különös tekintettel arra, hogy nem zárt útvonalak léteznek négyzetes táblákon az összes számára . [7] A táblákon lévő nyitott utak száma az A165134 sorozatot alkotja az OEIS -ben .

Lásd még

Jegyzetek

  1. ↑ Euler, Leonhard, Solution d'une question curieuse que ne paroit soumise à aucune analiz Archivált : 2017. szeptember 30., a Wayback Machine , Mémoires de l'académie des sciences de Berlin, 15 (1759) 1766, p. 310-337.
  2. ↑ How Euler Did It Archiválva : 2017. augusztus 8. a Wayback Machine -nél .
  3. ↑ Brendan McKay. Knight's Tours 8x8 sakktáblán  (határozatlan idejű)  // Technikai jelentés TR-CS-97-03. — Department of Computer Science, Australian National University, 1997. Archiválva az eredetiből 2013. szeptember 28-án.
  4. ↑ E. Geek. 2. fejezet Kaméleonló // Sakk és matematika . - M . : Nauka, 1983. - (Kvantumkönyvtár).
  5. ↑ Eric W. Weisstein, Nincsenek mágikus lovagtúrák a sakktáblán Archiválva : 2017. szeptember 8., a Wayback Machine , MathWorld Headline News.
  6. ↑ V. Panov. Egy trükk titka  // Tudomány és élet . - 1969. - 5. sz .
  7. ↑ A. Conrad, T. Hindrichs, H. Morsy, I. Wegener. A Knight's Hamilton Path feladat megoldása sakktáblákon   // Discr . Appl. Math. : folyóirat. - 1994. - 1. évf. 50 . - 125-134 . o . - doi : 10.1016/0166-218X(92)00170-Q .

Linkek