Ați jucat vreodată șah? Dacă da, știți deja că regina este cea mai importantă piesă și că poate muta orice număr de pătrate pe verticală, orizontală sau diagonală. Dacă nu ați făcut-o, nu vă faceți griji: astăzi, vom învăța doar cum să plasăm 8 regine pe tabla de șah astfel încât nicio regină să nu se poată deplasa pe o căsuță ocupată de o altă regină. În jargonul șahist, spunem că reginele nu se vor putea ataca între ele. Cum reușim să facem acest lucru? Folosim backtracking.
Algoritmul de backtracking găsește o soluție la probleme în care trebuie respectate anumite constrângeri. Acesta testează toate soluțiile posibile până când o găsește pe cea corectă. Să încercăm un exemplu, cu patru regine și o tablă mică. Vom începe prin a plasa prima regină:
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. Acesta vă va arăta și multe alte strategii de calcul care vă ajută să rezolvați probleme interesante!
Acum că știți cum funcționează backtracking-ul, putem rezolva problema celor 8 regine în mărime naturală. Mai jos, există o tablă de șah cu care vă puteți juca pentru a vă exersa abilitățileși pentru a găsi o soluție. Începeți prin a plasa prima regină făcând clic pe pătratul din stânga sus al tablei de șah. Veți vedea că regina pe care ați plasat-o va fi listată în lista „Regine curente”.
Regine curente
Acum puteți plasa o altă regină într-o poziție care le va împiedica să se atace între ele. Prima noastră regină este în a8, a doua, de exemplu, poate fi plasată pe c7. Continuați să plasați regine până când nu mai există niciun pătrat sigur pe tabla de șah. În acel moment, este timpul să dați înapoi făcând clic pe „undo”. Acest lucru va șterge ultima regină pe care ați plasat-o și vă va permite să alegeți un alt pătrat pentru a o plasa. De asemenea, puteți elimina o regină de pe tablă făcând clic direct pe ea.
Prin intermediul jocului interactiv, puteți începe să vă faceți o idee despre mersul înapoi. Ca oameni, poate deveni dificil pentru noi să ținem evidența tuturor plasărilor anterioare ale reginei. Aici ne ajută programarea! Mai jos, puteți găsi o animație generată de un program care își demonstrează abilitățile impecabile de backtracking:
Pseudocod:
- Începeți prin a plasa prima regină pe pătratul din stânga sus al tablei de șah.
- Dacă am plasat cele 8 regine, am terminat. În caz contrar, este posibil să plasăm o altă regină într-o poziție sigură?
- Dacă da, atunci marcați acest lucru ca parte a soluției și reveniți la punctul 2.
- Dacă nu, atunci schimbați poziția reginei anterioare (backtracking) și reveniți la punctul 2.
.