Problema celor 8 regine

1. Sarcina lucrării

Să se scrie un program ce rezolvă următoarea problema:

Problema celor 8 dame:Se cere să se găseasca toate soluţiile de aşezare pe tabla de şah a 8 regine astfel încît ele să nu să se atace.Se consideră că ele se atacă dacă sînt pe aceeaşi linie, coloană sau diagonală.

Desemenea se cere prezentarea grafica a citorva solutii pentru vizualizare mai buna a a raspunsurilor. De folosit metoda backtracking si libraria graphics.h

2. Introducere

Problema celor 8 regine reprezintă un exemplu bine cunoscut de utilizare a algoritmilor cu revenire. Această problemă a fost investigată de K.F. Gauss în 1850, care însă nu a rezolvat-o complet, întrucât până în prezent nu a fost găsită o soluţie analitică completă. În schimb ea poate fi rezolvată prin încercări, necesitând o mare cantitate de muncă, răbdare, exactitate şi acurateţe, atribute în care maşina de calcul excelează asupra omului chiar atunci când acesta este un geniu.

Specificarea Problemei celor 8 regine: pe o tablă de şah trebuiesc plasate 8 regine astfel încât nici una dintre ele să nu le ameninţe pe celelalte. Se observă imediat că aceasta este o problemă de tip(n,m): Deoarece există 8 regine care trebuiesc plasate, deci soluţia necesită 8 paşi, pentru fiecare din cele 8 regine existând, după cum se va vedea, 8 posibilităţi de a fi aşezate pe tabla de şah.

Sunt necesare câteva precizări. Deoarece din regulile şahului se ştie că regina ameninţă toate câmpurile situate pe aceeaşi coloană, rând sau diagonală în raport cu câmpul pe care ea se află, rezultă că fiecare coloană a tablei de şah va putea conţine o singură regină. Astfel alegerea poziţiei celei de-a i-a regine poate fi restrânsă numai la coloana i. În consecinţă: parametrul i din cadrul algoritmului devine indexul coloanei în care va fi plasată regina i, procesul de selecţie se restrânge la una din cele 8 valori posibile ale indicelui j care precizează rândul în cadrul coloanei. În concluzie: Avem o problemă tipică . Soluţionarea ei necesită 8 paşi (aşezarea celor 8 regine), fiecare într-una din cele 8 poziţii ale coloanei proprii (8 posibilităţi). Arborele de apeluri recursive este de ordinul 8 şi are înălţimea 8. În continuare se impune alegerea modalităţii de reprezentare a poziţiei celor 8 regine pe tabla de şah.

Soluţia imediată este aceea a reprezentării tablei cu ajutorul unei matrice t de dimensiuni 8x8 , dar o astfel de reprezentare conduce la operaţii greoaie şi complicate de determinare a câmpurilor disponibile. Pornind de la principiul că de fiecare dată trebuiesc utilizate reprezentările directe cele mai relevante şi mai eficiente ale informaţiei, în cazul de faţă nu se vor reprezenta poziţiile reginelor pe tabla de şah ci faptul că o regină a fost sau nu plasată pe un anumit rând sau pe o anumită diagonală.

Deci pentru a alcatui algoritmul dat avem nevoie de a face cunostinta cu metoda backtracking de asemenea pentru usurarea lucrului am apelat la exemplele de cod logic care ne permit sa facem alegerea optima a solutiei intr-un timp destul de scurt.

3. Tehnica Backtracking

Această tehnică se foloseşte în rezolvarea problemelor care îndeplinesc simultan următoarele condiţii:

- soluţia lor poate fi pusă sub forma unui vector S=x1,x2, .,xn, cu x1 € A1, x2 € A2 .,xn € An

- mulţimile A1, A2 , ., An sunt mulţimi finite, iar elementele lor se consideră că se află într-o relaţie de ordine bine stabilită;

- nu se dispune de o altă metodă de rezolvare, mai rapidă

- x1 x2 ., xn pot fi la rândul lor vectori;

- A1, A2 ., An pot coincide.

La întâlnirea unei astfel de probleme, dacă nu cunoaştem această tehnică, suntem tentaţi să generăm toate elementele produsului cartezian A1,A2 .,An si fiecare element să fie testat dacă este soluţie. Rezolvând problema în acest mod, timpul de execuţie este atât de mare, încât poate fi considerat infinit, algoritmul neavând nici o valoare practică.

De exemplu, dacă dorim să generăm toate permutările unei mulţimi finite A, nu are rost să generăm produsul cartezian AxAx.xA, pentru ca apoi, să testăm, pentru fiecare element al acestuia, dacă este sau nu permutare (nu are rost să generăm 1.1,1.1, pentru ca apoi să constatăm că nu am obţinut o permutare, când de la a doua cifră 1 ne puteam da seama că cifrele nu sunt distincte).

Pentru fiecare problemă se dau relaţii între componentele vectorului x, care sunt numite condiţii interne; soluţiile posibile care satisfac condiţiile interne se numesc soluţii rezultat. Metoda de generare a tuturor soluţiilor posibile si apoi de determinare a soluţiilor rezultat prin verificarea îndeplinirii condiţiilor interne necesită foarte mult timp.

Metoda backtracking evită această generare şi este mai eficientă. Elementele vectorului x, primesc pe rând valori în ordinea crescătoare a indicilor, x[k] va primi o valoare numai daca au fost atribuite valori elementelor x1. x[k-1]. La atribuirea valorii lui x[k] se verifica îndeplinirea unor condiţii de continuare referitoare la x1.x[k-1]. Daca aceste condiţii nu sunt îndeplinite, la pasul k, acest lucru înseamnă ca orice valori i-am atribui lui x[k+1], x[k+1], . x[n] nu se va ajunge la o soluţie rezultat.