A nyolc vezér-probléma további részletei
A visszalépéses kereséssel megoldható feladatok klasszikusának számító nyolc vezér problémát Carl Fridrich Gauss fogalmazta meg 1850-ben. A feladat megoldásaként azt kell eldönteni, hogy nyolc vezér elhelyezhető-e egy sakktáblán úgy, hogy ne üssék egymást. Ha igen, akkor hogyan oldható meg a feladat, és létezik-e több megoldás. A visszalépéses keresés módszere sok kombinatorikai probléma megoldására is alkalmas. Alapelve a szisztematikus próbálgatás, ami nagyon munkaigényes, ezért a számítógépek elterjedésével nőtt meg igazán a módszer gyakorlati jelentősége.(Carl Fridrich Gauss (1777-1855))
A visszalépéses kereséssel megoldható problémák klasszikusának számít, a Gauss által 1850-ben megfogalmazott nyolc vezér-probléma. A feladat célkitűzése egyszerűen megfogalmazható. Helyezzünk el nyolc vezért (királynőt) egy sakktáblán úgy, hogy egyik se legyen ütésben bármely másik által. Kérdés lehet, hogy van-e egyáltalán megoldása a problémának, és ha igen, akkor hány jó megoldás található.
Ha a nyolc vezér-probléma átfogalmazásával n vezér-problémáról beszélünk, az nem jelenti a feladat kellő általánosítását, hiszen továbbra is igaz a feladatot leíró sorozatokra, hogy minden sorozat elemei azonosak. A sorozatok rendezettek, a sorozatok elemeinek értéke megegyezik a sorszámukkal és az egyes sorozatok elemszáma azonos a sorozatok számával, hiszen a sakktábla négyzet alakú.
Az általános adatszerkezet alkalmazása a nyolc vezér-probléma megoldásában
A nyolc vezér-probléma megoldása során jelentős számú rossz elhelyezést kiküszöbölhetünk, ha a sakktábla egyes soraihoz egy-egy vezért rendelünk, azaz adott sorba nem helyezünk egynél több figurát. Így kizárjuk a soron belüli ütés lehetőségét. Ez azt jelenti, hogy az i. figurához azokat az i. soron belüli lehetséges pozícióinak a sorozatát rendeltük, ahova a soron belül elhelyezhetjük. Jelöljük ezeket 1-től 8-ig. Ezek a számok alkotják az i. sorozatot.
Nem nehéz belátni, hogy az általános adatszerkezet túlzott a feladat megoldása céljából, hiszen minden sorozat elemei azonosak, mi több rendezettek és ráadásul a sorozatok elemeinek értéke megegyezik a sorszámukkal is.
Az adatszerkezet átalakítása a feladat sajátságainak megfelelően
A nyolc vezér problémában rejlő specialitások (minden sorozat elemei azonosak, a sorozatok rendezettek, a sorozatok elemeinek értéke megegyezik a sorszámukkal), lehetővé teszik az adatszerkezet egyszerűsítésének lehetőségét. Nem szükséges tehát a sorozatok elemeinek tárolása, hiszen számlálással előállíthatók. Nem kell továbbá különbséget tenni a sorozatok elemének értéke és sorszáma között, mert azok egyenlők.
A megoldó-algoritmus funkcionális elemei
Ütésmentes hely keresése az i. vezér számára. Az i. vezér számára kijelölt pozíció vizsgálata (összevetése az i-nél kisebb sorszámú figurák pozícióival.)
21. századi közoktatás - fejlesztés, koordináció (TÁMOP-3.1.1-08/1-2008-0002)
