C++-ban lenne egy huszáros feladatom de nem tudom megoldani?

Elvileg egy backtrack módszer kellene az ellenőrzéshez, de a csekély számú lehetőség miatt ez most elhagyható, és végigcsinálhatod az összes lehetőséget izomból.

Először a dolog algoritmusát kell megalkotnod, vagyis végiggondolnod és leírnod magadnak azt, hogy te hogyan oldanád meg a feladatot saját kézzel, táblán, figurával.

Jelöld meg az összes mezőt el nem értnek (-).

Egy mezőn állva szerintem 8 különböző lépési lehetőség van, ezeknek a kiválasztását végezd valamilyen egységes elv szerint, megszámozva őket. Válaszd az első lépést, és jegyezd fel egy N elemű vektorban, a kezdőpozíciót és hogy 1. Arról a mezőről szintén léphetsz 8 féle módon, bár az ugyanoda való visszalépést kizárhatod. Válaszd itt is az 1. irányt, a vektor 2. eleme is 1. Így tovább N lépésig. Ha közben lelépsz a tábláról, akkor nem kell tovább folytatni. Végül megjelelöd az elért mezőt.

Aztán a backtrack módszer szerint a vektorban visszalépsz egy szintet, a figurát "visszateszed" a feljegyzett mezőre, megnézed, hogy ott az előbb hányadik irányt választottad, és most kipróbálod az eggyel nagyobb számút. Ha túljutsz a 8 lehetséges irányon, akkor még egyet visszalépsz a vektorban és így tovább. Ha a feladvány kezdőmezőjéről végigpróbáltad mind a 8 lépésirányt, akkor végeztél. Primitív, de működő megoldás. Próbáld ki először táblán, papírral, tollal, utána menni fog programban is.

Ezt nyelvre átültetni már a te feladatod.

#4 Az alap függvényben nyilván 8 lehetséges pozíciót kell vizsgálnod (ennyi helyre léphet elméletileg a ló), de ezek közül lehetnek olyanok, melyek a táblán kívülre vezetnek, ezért azok eleve kiesnek. Tehát van nyolc vizsgálat, ezek mindegyike végén meghív(hat)ja saját magát a függvény.

Arra kell még ügyelni, hogy a függvény reentráns legyen, azaz ne használjon statikus változókat, mert akkor nyilván összezavarná saját futását. Tehát a függvény lokális adatokkal dolgozzon! Amikor a függvény megkapja a Sor, Oszlop és Lépésszám adatokat a híváskor, akkor ezekkel fog számolni (a Lépésszámot növeli, Sor és Oszlop pedig a pozíció kiértékeléshez kell). Ha megvan a módosított Sor és Oszlop (ahová a ló léphet), akkor a függvény hívásakor ezeket a módosított értékeket kapja meg és a Lépésszámot.

Kérdező, a lehetséges lépések egy klasszikus "fa" gráffal ábrázolhatók. (Mint a lemezes könyvtárszerkezet vagy egy szőlőfürt.) Persze az algoritmus készítője tudja, hogy az ágak a valóságban miféle lépést jelentenek, a gráf az elvi vázlat. Balról haladva a tetejéről indulsz, elmész egy ág végéig. Utána az utolsó ágon vissza, a csomópontnál tovább lefelé a következő ágon az út végéig. Aztán vissza, következő ág stb. Ha az egy csomópontból kiinduló ágak elfogytak, akkor vissza eggyel, és eszerint folytatva. Amikor a gráf legfelső pontjából is felfelé akarnál lépni, akkor az eljárás véget ért. Rajzold le, érteni fogod, nagyon egyszerű elv. A programban annyi a feladat, hogy egy vektort (tömböt) kell használni, és mindig azt tárolni benne, hogy az adott számú csomópontnál hányadik ágon indulsz tovább.

Ezen az elven nagyon fellelkesültem, amikor nagyon régen először hallottam róla, hiszen így egy sakkjátszma is csak egy ugyanilyen algoritmus ellen lehet elveszíthető. Aztán kiderült, hogy a szükséges idő brutálisan sok. Ennek ellenére Commodore 64-esre írtam egy olyan programot, amely a peg solitaire játékra ( [link] keres megoldásokat. Amíg Basicben futott, elég szenvedős volt. De átírtam assemblybe, és pár nap alatt annyit találtam, mint a nyű. Még akkor is, amikor leszűkítettem a szabályt arra, hogy csak a középen maradó golyó a teljes megoldás. Valahol még meg is vannak elmentve, azt hiszem, bár jóval a vége előtt leállítottam. Szóval az algoritmus tényleg működőképes minden olyan feladványnál, ahol a választható lépések besorszámozhatók.