Bejárhatók-e a huszár "nagy lóugrásával" a sakktábla sötét mezői?
Első közelítésben nézzük át a klasszikus Huszár lépésének
szabályait.
Huszár – csak L alakban léphet (függőlegesen 2-t és vízszintesen egyet, vagy fordítva) és ez az egyetlen bábu, amely átugorhatja a másikat, amelyik az útjában van. A huszár különleges lépését lóugrásnak is nevezik. A huszár tehát gyakorlatilag nem lép, hanem ugrik és mindig egy más színű mezőre érkezik meg, eredeti helyzetéhez viszonyítva.
Definiálok egy figurát, legyen a neve ideiglenesen Qhuszár, amely szintén L alakban léphet: függőlegesen 3-t és vízszintesen egyet, vagy fordítva. Ez is átugorhatja a másikat, amelyik az útjában van.
Ennek a figurának a különleges lépését "nagy lóugrásnak"
neveztem el és nem az ellenkező színű mezőre érkezik meg az eredeti helyzetéhez viszonyítva. Tehát azonos színű mezőkön ugrálhat. Ha játékba hoznánk, akkor a sakk játszmában az ellenfél futó párja közül csak az egyik lehetne veszélyes a számára. De most nem akarok a részletekbe menni, hogy mennyire értelmes az
itt definiált figura és lépése, mennyire lehetne vele a klasszikus huszár helyett értelmes partikat játszani. Ha valaki olvasott már valami hasonlóról, kérem tájékoztasson.
Helyezzük el a Qhuszárt a sakktábla bal alsó a1-es sötét mezejére. A kérdés az, hogy ezzel a figurával és hozzárendelt lépésével bejárható-e a sakktábla összes sötét mezője (összesen 31 lépéssel)
úgy, hogy minden mezőt csak egyszer érinthet?
válasza:487002 megoldás van, bár ebben benne vannak a szimmetrikusan azonosak is, szóval bizonyára ennek pont a fele.
Az első amit a programom talált, ez:
-- 26 -- 30 -- 22 -- 24
31 -- 21 -- 25 -- 29 --
-- 16 -- 28 -- 20 -- 18
27 -- 09 -- 17 -- 23 --
-- 32 -- 14 -- 10 -- 04
15 -- 11 -- 05 -- 19 --
-- 08 -- 02 -- 12 -- 06
01 -- 13 -- 07 -- 03 --
Az utolsó pedig persze pont a tükörképe:
-- 06 -- 04 -- 18 -- 24
03 -- 19 -- 23 -- 29 --
-- 12 -- 10 -- 20 -- 22
07 -- 05 -- 17 -- 25 --
-- 02 -- 14 -- 28 -- 30
13 -- 11 -- 09 -- 21 --
-- 08 -- 32 -- 16 -- 26
01 -- 15 -- 27 -- 31 --
A közepe felé meg pl. ez van:
-- 04 -- 18 -- 26 -- 32
09 -- 27 -- 31 -- 19 --
-- 14 -- 08 -- 28 -- 30
05 -- 03 -- 17 -- 25 --
-- 10 -- 12 -- 22 -- 20
13 -- 15 -- 07 -- 29 --
-- 06 -- 02 -- 16 -- 24
01 -- 11 -- 23 -- 21 --
válasza:A megoldások közül 10360 darab (illetve ennek a fele, ha a szimmetriát kizárjuk) cirkuláris, vagyis visszajut a kiindulási pontra. Ilyen pl. ez:
-- 06 -- 04 -- 18 -- 24
03 -- 19 -- 23 -- 29 --
-- 12 -- 10 -- 20 -- 22
07 -- 05 -- 17 -- 25 --
-- 02 -- 14 -- 28 -- 30
13 -- 11 -- 09 -- 21 --
-- 08 -- 32 -- 16 -- 26
01 -- 15 -- 27 -- 31 --
Kedves bongolo!
Közöttünk már volt eszmecsere matek témákban. Köszönettel
vettem a fáradozásaidat. És nem kevés a megoldások száma, ahogy a klasszikus esetben. Viszont bajban vagyok az azonosítóiddal, mert a klasszikus a1-h8 mező azosítások
helyett a {01, 02, ..., 31,32} halmazból veszed az eredményt. Az utolsó megoldásodnál, ha a sötét mezőket sor folytonosan rendezem még értem, hogy 06(d2)-ról hogyan jutunk el a 04(g1) mezőre, de innen hogyan jutunk a 18(c5) mezőre, ami nálam inkább 15(f4) vagy 16(h4) lehetne. Ha tisztáztuk ezt, akkor még néhány kérdéssel zavarnálak. A megoldások között hogyan értendő a tükörkép? Továbbá az a bizonyos megoldó programod tud-e a standard-tól eltérő táblán (például 4X16 mezős táblán) is
megoldásokat generálni. Végül ne vedd túlzott kíváncsiságnak, vajon a két-három lépéses sakkfeladványokat is meg tudja oldani?
Köszönettel. Sz. Gy.
válasza:Kedves Gyula!
A megoldásokat úgy kell értelmezni a válaszomban, hogy az a 8×8-as sakktábla 64 mezője. A bal alsó az A1 sötét mező, abban van a 01 szám, mert az a lépéssorozat első pozíciója. A világos mezőkben -- van, azokat nem lehet elérni. A második pozíciót a 02 jelenti, ez nagy lóugrásra van az A1 mezőtől kezdve valahol (vagy jobbra, vagy felfelé). A harmadik pozícióra került a 03, stb.
A cirkuláris megoldásnál a 32-edik pozíció szintén nagy lóugrásra van a 01-től. (Egyébként az első két megoldás is cirkuláris, nem csak amit a második levelemben írtam).
Tükörkép: az első két megoldás, amiket írtam, azok pl. egymás tükörképei, ahol az A1-H8 átló a tükrözés tengelye. Az első megoldásban a második pozíció a D2, míg a másodikban a tükörképe, vagyis a B4. A harmadik pozíciók is egymás tükrözései, stb. Valójában ez a két megoldás nem két különböző megoldás, csak más a körbejárás iránya. Az elsőnél jobb3+fel irányba indultunk, a másodiknál meg fel3+jobb irányba, és ugyanígy a többi lépés is tükrözve van.
A programom most 8×8-ason működik, de bizonyára könnyen lehet más méretre is átírni. Sakkfeladványokat nem tud, nem sakkprogram, csak a nagy lóugrás van benne implementálva :) Pici program egyébként, 70 sor az egész.
válasza:Számítógép programozó a hivatalos pénzkereső foglalkozásom, úgyhogy egy ilyen nem túl bonyolult back-track-es programot illik kevesebb mint egy óra alatt összehozni :)
Ez az egyébként:
pastebin com / R8z0XNAM
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!