Sakkoztál már valaha? Ha igen, akkor már tudod, hogy a vezér a legfontosabb bábu, és hogy tetszőleges számú mezőt mozoghat függőlegesen, vízszintesen vagy átlósan. Ha még nem, ne aggódj: ma csak azt fogjuk megtanulni, hogyan kell 8 királynőt úgy elhelyezni a sakktáblán, hogy egyetlen királynő se tudjon egy másik királynő által elfoglalt mezőre lépni. A sakkzsargonban azt mondjuk, hogy a királynők nem tudják megtámadni egymást. Hogyan érjük ezt el? Backtrackinget használunk.
A backtracking algoritmus olyan problémákra talál megoldást, amelyekben bizonyos megkötéseket be kell tartani. Addig teszteli az összes lehetséges megoldást, amíg meg nem találja a helyeset. Próbáljunk ki egy példát, négy vezérrel és egy kis táblával. Kezdjük az első vezér elhelyezésével:
The second step is to place the second queen in a safe position, and then the third one:
At this point, there is no safe square on which we can place the last queen. So, we will change the position of the previous one. This is backtracking!
As you can see, there is no other square to safely place the third queen, different than the one we tried. Hence, this will require multiple backtracks. We will have to go back again and change the position of the second queen we placed.
We will have to perform multiple backtracks again to place all queens correctly and finally obtain a solution:
If you want to learn more how multiple backtracking steps inevitably lead you to a solution, check out Computer Science Distilled. Sok más számítási stratégiát is megmutat, amelyek segítenek érdekes problémák megoldásában!
Most, hogy már tudod, hogyan működik a backtracking, megoldhatjuk a teljes méretű 8 királynő problémát. Az alábbiakban egy sakktáblát találsz, amellyel játszhatsz, hogy gyakorold a képességeidetés megtaláld a megoldást. Kezdd azzal, hogy a sakktábla bal felső négyzetére kattintva elhelyezed az első királynőt. Látni fogod, hogy az általad elhelyezett királynő az “Aktuális királynők” lista alatt fog szerepelni.
Az aktuális királynők
Most egy másik királynőt is elhelyezhetsz olyan pozícióba, hogy azok ne támadhassák egymást. Az első vezérünk az a8-on van, a másodikat például a c7-re helyezhetjük. Addig folytassuk a királynők elhelyezését, amíg nem marad biztonságos négyzet a sakktáblán. Ekkor ideje visszalépni a “visszavonás” gombra kattintva. Ezzel törlöd az utoljára elhelyezett királynőt, és választhatsz egy másik négyzetet a királynő elhelyezéséhez. Egy királynőt úgy is eltávolíthatsz a tábláról, hogy közvetlenül rá kattintasz.
Az interaktív játékkal játszva elkezdhetsz ráérezni a visszalépésre. Emberként nehézzé válhat számunkra, hogy nyomon kövessük az összes korábbi királynő elhelyezését. Ebben segít a programozás! Az alábbiakban egy program által generált animációt találsz, amely bemutatja hibátlan visszalépési képességeit:
Pszeudokód:
- Az első királynőt a sakktábla bal felső négyzetére helyezzük.
- Ha mind a 8 királynőt elhelyeztük, akkor végeztünk. Ellenkező esetben lehetséges-e egy másik királynőt biztonságos helyre tenni?
- Ha igen, akkor ezt jelöljük meg a megoldás részeként, és térjünk vissza a 2. ponthoz.
- Ha nem, akkor változtassuk meg az előző királynő helyzetét (visszalépés), és térjünk vissza a 2. ponthoz.