MINISTERUL EDUCAȚIEI,CERCETĂRII,TINERETULUI ȘI SPORTULUICOLEGIUL TEHNIC MĂTĂSARI

ATESTAT PROFESIONAL

Prof. îndrumătorSăceanu Ion

Elev:Popescu Florin Cristian

Profil: Matematică-Informatică

Colegiul Tehnic Mătăsari

Clasa a XII-a B

1

MINISTERUL EDUCAȚIEI,CERCETĂRII,TINERETULUI ȘI SPORTULUICOLEGIUL TEHNIC MĂTĂSARI

PROBLEMA CELOR N DAME

Prof. îndrumător:Săceanu Ion

Elev:Popescu Florin Cristian

Profil: Matematică-Informatică

Colegiul Tehnic Mătăsari

Clasa a XII-a B

2

CUPRINS

Argumentarea temei alese………………………………………………………………4Problema celor n dame ……………………………………………………………....... 5Prezentarea tehnicii Backtracking………………………………………………………..6

Aplicaţie problema celor 8 dame....................................................................................13Aflarea soluţiei:.................................................................................................................13

1.Stiva:...............................................................................................................................15

2. Exemplificarea lucrului cu stiva:...................................................................................16

3.Tehnica backtracking:....................................................................................................16

4. Exemplu practic: aranjarea mobilei într-o casă:..........................................................18

5. Metoda backtracking.....................................................................................................19

6. Generarea permutărilor................................................................................................20

7. Problema generării aranjamentelor:.............................................................................21

8. Problema damelor la general:.......................................................................................22

Bibliografie……………………………………………………………………………...27

3

Argumentarea temei alese

Crearea unui soft educational este o artă care seamănă cu rezolvarea unui

puzzle. În activitatea sa omul lucrează cu informaţia. Metodele şi tehnicile de organizare

a informaţiei au evoluat împreună cu dezvoltarea echipamentelor de calcul şi cu evoluţia

tehnicilor şi limbajelor de programare.

Învătământul modern presupune utilizarea unor mijloace de prezentare a

informaţiei într-o formă dinamică şi care sa simuleze realitatea. Se ştie că fiinţa umană

invaţă mai uşor prin joc. Acest proiect ajută elevii să inveţe mai usor tehnica

backtracking prin prezentarea unei interfeţe în cazul problemei damelor.

Softul educaţional reflectă necesitatea cunoaşterii limbajelor de programare in

scopul punerii în valoare a disciplinei <INFORMATICA>.

În acest scop mi-am ales tema “Tehnica Backtraking aplicată la problema

damelor care descrie în mod grafic importanţa si necesitatea tehnicii Backtraking în

diverse aplicaţii.

4

Problema celor n dame

METODA BACKTRACKING

Stiva este acea formă de organizare a datelor (structură de date) cu proprietatea că operaţiile de introducere şi scoatere a datelor se fac în vârful ei.

Stivele se pot simula utilizând vectori.Fie ST(i) un vector. ST(1), ST(2), ..., ST(n) pot reţine numai litere sau

numai cifre. O variabilă K indică în permanentă vârful stivei.Exemplificăm, în continuare, modul de lucru cu stiva:

În stiva iniţial vidă se introduce litera A, vârful stivei va fi la nivelul 1 (k-1);

introducem în stivă litera B, deci k va lua valoarea 2;

scoatem din stivă pe B (A nu poate fi scos);

scoatem din stivă pe A; stiva rămâne vidă

În mod practic la scoaterea unei variabile din stivă, scade cu 1 valoarea variabilei ce indică vârful stivei, iar atunci când scriem ceva în stivă, o eventuală valoare reziduală se pierde:

Pe un anumit nivel se retine, de regulă, o singură informaţie (literă sau cifră), însă este posibil; aşa cum va rezulta din exemplele, prezentate în lucrare, să avem mai multe informaţii, caz în care avem de a face cu stive duble, triple, etc.

Întreaga teorie a recursivităţii se bazează pe structura de tip stivă.

5

A

BA

A

Prezentarea tehnicii 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).

Tehnica Backtracking are la bază un principiu extrem de simplu:- se construieşte soluţia pas cu pas: x1, x2 …,xn

- dacă se constată că, pentru o valoare aleasă, nu avem cum să ajungem la soluţie, se renunţă la acea valoare şi se reia căutarea din punctul în care am rămas.

Concret: - se alege primul element x, ce aparţine lui A; - presupunând generate elementele x1,x2 …,xk , aparţinând mulţimilor

A1, A2 …,Ak , se alege (dacă există) xk+1 , primul element disponibil din

mulţimea Ak+1 , apar două posibilităţi :1) Nu s-a găsit un astfel de element, caz în care caz în care se reia

căutarea considerând generate elementele x1,x2 …,xk+1 , iar aceasta se reia de la următorul element al mulţimii Ak rămas netestat;

6

2) A fost găsit, caz în care se testează dacă acesta îndeplineşte anumite condiţii de continuare apărând astfel două posibilităţi:

- îndeplineşte, caz în care se testează dacă s-a ajuns la soluţie si apar din nou două posibilităţi

- s-a ajuns la soluţie, se tipăreşte soluţia si se reia algoritmul considerând generate elementele x1,x2 …,xk , (se caută în continuare, un alt element al mulţimii Ak , rămas netestat);

- nu s-a ajuns la soluţie, caz în care se reia algoritmul considerând generate elementele x1,x2 …,xk , si se caută un prim element xk+2 € Ak.

- nu le îndeplineşte caz în care se reia algoritmul considerând generate elementele x1,x2 …,xk , iar elementul xk-1 se caută între elementele mulţimii A, rămase netestate.

Algoritmii se termină atunci când nu există nici un element x1 € A1

netestat.Observaţie: tehnica Backtracking are ca rezultat obţinerea tuturor

soluţiilor problemei. În cazul în care se cere o sigură soluţie se poate forţa oprirea, atunci când a fost găsită.

Am arătat că orice soluţie se generează sub formă de vector. Vom considera că generarea soluţiilor se face intr-o stivă. Astfel, x1 € A1, se va găsi pe primul nivel al stivei, x2 € A2 se va găsi pe al doilea nivel al stivei,... xk € Ak se va găsi pe nivelul k al stivei. În acest fel, stiva (notată ST) va arăta astfel:

ST

Nivelul k+1 al stivei trebuie iniţializat (pentru a alege, în ordine, elementele mulţimii k+1 ). Iniţializarea trebuie făcută cu o valoare aflată (în relaţia de ordine considerată, pentru mulţimea Ak+1 ) înaintea tuturor valorilor posibile din mulţime. De exemplu, pentru generarea permutărilor mulţimii {1,2.....n}, orice nivel al stivei va lua valori de la 1 la n. Iniţializarea unui nivel (oarecare) se face cu valoarea 0. Procedura de iniţializare o vom numi

7

...

xk

…

…

x2

x1

INIT şi va avea doi parametri: k (nivelul care trebuie iniţializat si ST (stiva)).

Găsirea următorului element al mulţimii Ak (element care a fost netestat) se face cu ajutorul procedurii SUCCESOR (AS,ST,K). Parametrul AS (am succesor) este o variabilă booleană. În situaţia în care am găsit elementul, acesta este pus în stivă şi AS ia valoarea TRUE, contrar (nu a rămas un element netestat) AS ia valoarea FALSE..

Odată ales un element, trebuie văzut dacă acesta îndeplineşte condiţiile de continuare (altfel spus, dacă elementul este valid). Acest test se face cu ajutorul procedurii VALID (EV,ST,K).

Testul dacă s-a ajuns sau nu la soluţia finală se face cu ajutorul funcţiei SOLUTIE(k) iar o soluţie se tipăreşte cu ajutorul procedurii TIPAR. Prezentăm în continuare rutina Backtracking:

k:=1; init(1,st);while k>0 do begin

repeat succesor (as, st, k) ; . if as then valid(ev,st,k) until (not as) or (as and ev) ;if as then

if solutie(k) then tipar else begin k:=k+l; init ( k, st ); end;

else k:=k-1 end;

Observaţie: Problemele rezolvate prin această metodă necesită un timp îndelungat. Din acest motiv, este bine să utilizăm metoda numai atunci când nu avem la dispoziţie un alt algoritm mai eficient. Cu toate că există probleme pentru care nu se pot elabora alţi algoritmi mai eficienţi, tehnica backtracking trebuie aplicată numai în ultimă instanţă.

Fiind dată o tablă de şah, de dimensiune n, xn, se cer toate soluţiile de aranjare a n dame, astfel încât să nu se afle două dame pe aceeaşi linie, coloană sau diagonală (dame să nu se atace reciproc).

Exemplu: Presupunând că dispunem de o tablă de dimensiune 4x4, o soluţie ar fi următoarea:

8

DD

DD

Observăm că o damă trebuie să fie plasată singură pe linie. Plasăm prima damă pe linia 1, coloana 1.

A doua damă nu poate fi aşezată decât în coloana 3.

Observăm că a treia damă nu poate fi plasată în linia 3. Încercăm atunci plasarea celei de-a doua dame în coloana 4.

A treia damă nu poate fi plasată decât în coloana 2.

În această situaţie dama a patra nu mai poate fi aşezată.

9

D

DD

DD

DD

D

Încercând să avansăm cu dama a treia, observăm că nu este posibil să o plasăm nici în coloana 3, nici în coloana 4, deci o vom scoate de pe tablă. Dama a doua nu mai poate avansa, deci şi ea este scoasă de pe tablă. Avansăm cu prima damă în coloana 2.

A doua damă nu poate fi aşezată decât în coloana 4.

Dama a treia se aşează în prima coloană.

Acum este posibil să plasăm a patra damă în coloana 3 si astfel am obţinut o soluţie a problemei.

Algoritmul continuă în acest mod până când trebuie scoasă de pe tablă prima damă.

Pentru reprezentarea unei soluţii putem folosi un vector cu n componente (având în vedere că pe fiecare linie se găseşte o singură damă).

10

D

DD

DD

D

DD

DD

Exemplu pentru soluţia găsită avem vectorul ST ce poate fi asimilat unei stive.

Două dame se găsesc pe aceeaşi diagonală dacă si numai dacă este îndeplinită condiţia: |st(i)-st(j)|=|i-j| ( diferenţa, în modul, între linii si coloane este aceeaşi).

ST(4)

ST(3) În general ST(i)=k semnifică faptul că pe linia i dama ocupă

poziţia k. ST(2)

ST(1)

Exemplu: în tabla 4 x4 avem situaţia:st(1)= 1 i = 1 st(3)= 3 j = 3|st(1) - st(3)| = |1 – 3| = 2 |i – j| = |1 – 3| = 2

sau situaţia

st(1) = 3 i = 1st(3) = 1 j = 3|st(i) - st(j)| = |3 – 1| = 2|i – j| = |1 – 3| = 2

Întrucât doua dame nu se pot găsi în aceeaşi coloană, rezultă că o soluţie este sub formă de permutare. O primă idee ne conduce la generarea tuturor permutărilor si la extragerea soluţiilor pentru problema ca două dame să nu fie plasate în aceeaşi diagonală. A proceda astfel, înseamnă că lucrăm conform strategiei backtracking. Aceasta presupune ca imediat ce am găsit două dame care se atacă, să reluăm căutarea.

lată algoritmul, conform strategiei generate de backtracking:- În prima poziţie a stivei se încarcă valoarea 1, cu semnificaţia că în

linia unu se aşează prima damă în coloană.- Linia 2 se încearcă aşezarea damei în coloana 1, acest lucru nefiind

posibil întrucât avem doua dame pe aceeaşi coloană.

11

3

1

4

2

DD

DD

DD

DD

- În linia 2 se încearcă aşezarea damei în coloana 2 , însă acest lucru nu este posibil, pentru că damele se găsesc pe aceiaşi diagonală (|st(1)-st(2)|=|1-2|);

- Aşezarea damei 2 în coloana 3 este posibilă.- Nu se poate plasa dama 3 în coloana 1, întrucât în liniile 1-3 damele

ocupa acelaşi coloană.- Şi această încercare eşuează întrucât damele de pe 2 şi 3 sunt pe

aceeaşi diagonală.- Damele de pe 2-3 se găsesc pe aceeaşi coloană.- Damele de pe 2-3 se găsesc pe aceeaşi diagonală.- Am coborât în stivă mutând dama de pe linia 2 şi coloana 3 în coloana

4.

Algoritmul se încheie atunci când stiva este vidă. Semnificaţia procedurilor utilizate este următoarea:

INIT - nivelul k al stivei este iniţializat cu 0;SUCCESOR - măreşte cu 1 valoarea aflată pe nivelul k al stivei în

situaţia în care aceasta este mai mică decât n şi atribuie variabilei EV valoarea TRUE, în caz contrar, atribuie variabilei EV valoarea FALSE;

VALID - validează valoarea pusă pe nivelul k al stivei, verificând dacă nu avem două dame pe aceeaşi linie (st(k)=st(i)), sau dacă nu avem două dame pe aceeaşi diagonală (st(k)-st(i)=|k-i|)caz în care variabilei EV i se atribuie FALSE; în caz contrar, variabilei EV i se atribuie TRUE;

SOLUTIE - verifică dacă stiva a fost completată până la nivelul n inclusiv;

TIPAR - tipăreşte o soluţie.

12

Aplicaţie,problema celor opt dame

Problema celor opt dame, aşezate pe o tablă de 8x8, cunoscută la nivel mondial ca şi The 8 Puzzle Queens, problema standard, consta în aşezarea a opt dame pe table 8x8, care nu trebuie să se atace între ele. Pentru a găsii soluţia corectă, nu trebuie să existe două dame pe aceasi linie, coloană, sau diagonală.

Istoric:Problema a fost prima dată propusă în 1848 de către jucătorul de şah Max Bezzel

şi peste câţiva ani de mai mulţi matematiceni printre care şi Johann Carl Friedrich Gauss care a lucrat la acesta problemă şi la problemă generală. Prima soluţie a fost găsită de Franz Nauck în 1850. Tot Nauck a generalizat problema. În 1874, S. Gunther a propus o metodă de găsire a solutilor folosind determinantul.

Edsger Dijkstra a folosit această problemă în 1972 pentru a ilustra ceea ce noi numim structura de programare. El a publicat o descriere foarte detaliată a primului algoritm de backtracking.

Aflarea solu ţ iei: Problema pare destul de complicată, fiind 4.426.165.368 de cazuri posibile de a

pune cele opt dame pe tabla de 8x8 şi doar 92 de soluti corecte. Dintre cele 92 de soluţii, există doar 12 cazuri unice sau fundamentale.

Caz 1

Caz 2.

13

a b c d e f g hX 8

X 7X 6

X 5X 4

X 3X 2

X 1

a b c d e f g hX 8

X 7X 6

X 5X 4

X 3X 2

X 1

Caz 3.

Caz 4.

Caz 5.

Caz 6.

Caz 7.

Caz 8.

14

a b C d e f g hX 8

X 7X 6

X 5X 4

X 3X 2

X 1

a b c d e f g hX 8

X 7X 6

X 5X 4

X 3X 2

X 1

a b c d e f g hX 8

X 7X 6

X 5X 4

X 3X 2

X 1

a b c d e f g hX 8

X 7X 6

X 5X 4

X 3X 2

X 1

a b c d e f g hX 8

X 7X 6

X 5X 4

X 3X 2

X 1

a b c d e f g hX 8

X 7X 6

X 5X 4

X 3X 2

X 1

Caz 9.

Caz 10.

Caz 11.

Caz 12.

1.Stiva:Stiva este o listă pentru care singurele operaţii permise sunt:• adăugarea unui element in stivă;• eliminarea, consultarea sau modificarea unui element introdus in

stivă;

15

a b c d e f g hX 8

X 7X 6

X 5X 4

X 3X 2

X 1

a b c d e f g hX 8

X 7X 6

X 5X 4

X 3X 2

X 1

a b c d e f g hX 8

X 7X 6

X 5X 4

X 3X 2

X 1

a b c d e f g hX 8

X 7X 6

X 5X 4

X 3X 2

X 1

Stiva funcţionează pe principiul LIFO (Last In First Out) - ultimul intrat, primul ieşit.

Atenţie: adăugarea sau scoaterea unui element din stivă se face prin acelaşi capăt, numit vârful stivei

Imaginaţi-vă o stivă de farfurii de culori diferite.

I. Pentru a scoate farfuria roşie trebuie să scoatem toate farfuriile aflate deasupra

acesteia.II. Acum putem extrage farfuria roşie.

2. Exemplificarea lucrului cu stiva:a) n stiva iniţial vidă se introduce elementul A şi vârful stivei va fi

nivelul 1 (k=1).b) Introducem în stivă elementul B, deci vârful stivei va fi nivelul 2

(k=2).

c) Vrem să scoatem din stivă elementul A. Se procedează în felul următor: scoatem din stivă elementul B, deoarece A nu se poate scoate deocamdată. Vârful stivei devine nivelul 1 (k=1).

d) Scoatem din stivă pe A.

3.Tehnica backtracking:. Există clase de probleme pentru care algoritmii se proiectează după o

anumită metodă de programare. Putem privi metoda de programare ca un şablon pe care îl putem aplica pentru rezolvarea unor clase de probleme cu un specific comun.

Tehnica backtracking se foloseşte în rezolvarea problemelor care au următoarele caracteristici:

16

- soluţia lor poate fi pusă sub forma unui vector:S= s1 s2 .... sn  unde s1єS1, s2єS2.... snєSn- mulţimile S1, S2... Sn sunt mulţimi finite, iar elementele lor se află intr-o relaţie de ordine bine stabilită.- nu avem la dispoziţie o altă metodă mai rapidă

Important:- nu în toate problemele n este cunoscut de la început;- S1,S2,....Sn, pot fi la rândul lor vectori;- în multe probleme, S1,S2,...Sn coincid;- tehnica backtracking are ca rezultat obţinerea tuturor soluţiilor problemei. De aceea dacă se doreşte o singură soluţie, trebuie forţată oprirea algoritmului.

Am arătat că soluţiile se generează sub formă de vector. Considerăm că acest vector este prelucrat ca o stivă.

Notăm vectorul stivă cu st şi n este dimensiunea acesteia.Vectorul st format din elementele (st[1], st[2],..., st[n]) aparţinând S1

x S2 x ... x Sn se numeşte soluţie finală.Mulţimea finită S = S1 x S2 x ... x Sn se numeşte mulţimea soluţiilor

posibile.Între elementele vectorului stivă st exista anumite relaţii. Aceste relaţii

le vom numi condiţii de validare.Vom spune despre st[1], st[2],..., st[k] că reprezintă o soluţie validă

dacă şi numai dacă sunt îndeplinite condiţiile de validare ale problemei.O soluţie validă devine soluţie finală dacă numărul k al nivelului în

stivă este egal cu n (dimensiunea stivei).

17

4. Exemplu practic: aranjarea mobilei într-o casă:

Un exemplu practic de utilizare a unui algoritm backtracking îl constituie problema aşezării mobilei într-o casă nouă.

Există multe posibilităţi de încercare dar în mod practic doar câteva vor fi luate în considerare.

Pornind de la punctul iniţial când casa este goală, fiecare piesă de mobilă este plasată în anumite locuri.

Dacă toată mobila este aranjată şi proprietarul este mulţumit atunci algoritmul se încheie.

Dacă ne vom lovi de situaţia în care la un moment aranjamentul parţial obţinut este neplăcut, suntem nevoiţi să renunţăm la poziţia pe care am plasat ultima piesă şi să încercăm o altă amplasare a ei.

Dacă nu vom găsi o variantă satisfăcătoare, continuăm să renunţăm şi la poziţia penultimei piese aşezate, căutându-i o altă poziţie şi aşa mai departe.

18

În situaţia în care am renunţat la toate variantele atunci nu există nici un aranjament convenabil, deci problema nu are soluţii.

În caz contrar, o să obţinem soluţia problemei.Trebuie menţionat că algoritmul nu generează toate variantele posibile

de aranjamente. Plasarea unei piese nu va fi făcută direct în toate locurile disponibile

din casă. De exemplu, varianta de a aşeza biblioteca în bucătărie nu va fi luată

în considerare. Multe asemenea variante vor fi abandonate din start deoarece conduc

la obţinerea unor aranjamente neplăcute.

5. Metoda backtracking Va folosi o serie de proceduri şi funcţii care vor fi folosite totdeauna

cu acelaşi nume şi aceiaşi parametri:

procedure init(k, st);Rol: atribuie elementului situat pe nivelul k o valoare iniţialăParametri:          k - nivelul in stivă          st - stivă

procedure succesor(k, st, as);Rol: atribuie elementului st[k] din stivă valoarea următoare din mulţimea SkParametri:

19

         as - variabilă booleană care întoarce valoarea adevărat dacă elementul situat pe nivelul k are succesor          st - stivă          k - nivelul in stivă

procedure validare(k, st, ev);Rol: verifică dacă elementul pus pe nivelul k în stivă îndeplineşte restricţiile între elementele distinctiveParametri:          k - nivelul in stivă          st - stivă          ev - variabilă booleană care întoarce valoarea adevărat dacă elementul situat pe nivelul k este valid sau nu

function solutie(k): boolean;Rol: verifică dacă s-au determinat toate elementele din stivă ce constituie vectorul soluţie al problemeiParametri:          k - nivelul in stivă

procedure tipar;Rol: listează soluţia determinată

6. Generarea permutărilorUn creator de modă a pregătit trei melodii pentru a crea ambientul

muzical în timpul prezentării ultimei sale colecţii, dar încă nu s-a hotărât exact în ce ordine să le pună. El te roagă să-i generezi toate succedările posibile, astfel încat să o poată asculta pe fiecare şi s-o aleagă pe cea mai potrivită.

Observaţie:- prima melodie o notăm cu 1;- a doua melodie o notăm cu 2;- a treia melodie o notăm cu 3;- o succedare este validă când melodiile ce o compun sunt diferite între ele.

k<-1init(k,st)while k<0 do{

20

repeat { succesor (k,st,as) if as then validare ( k,st,ev) until (not as) or (as and ev) }if as then { if solutie(k) then tipar { else k<-k+1 init(k,st) } else k<-k-1 }}

7. Problema generării aranjamentelor:În continuare vă propunem următorul joc: folosindu-vă de algoritmul

prezentat anterior în problema creatorului de modă, sunteţi invitaţi să generaţi aranjamentele de trei elemente luate câte două. Tot ce trebuie să faceţi e să umpleţi nivelul în stivă cu elementul corespunzător. Elementele le "luaţi" din mulţimea din partea dreaptă a ecranului şi le "lăsaţi" în nivelul corespunzător din stivă. În partea de jos a ecranului aveţi punctajul obţinut.

Observaţie: elementul 0 este folosit pentru iniţializarea nivelului k din stivă.

8. Problema damelor la general:Să se găsească toate modalitaţile de a aranja n dame pe o tablă de şah

de dimensiuni n x n, astfel încât ele să nu se atace una pe alta. Două dame se

21

atacă dacă ele se află pe aceeaşi linie, pe aceeaşi coloana sau pe aceeaşi diagonala. Această problemă fuctioneaza doar pentru n=1 sau n>=4.

De exemplu, daca n=4, o soluţie este reprezentată în figuria a. modul de obţinere al soluţiei este prezent în figurile următoare, de la b la i.

a)

x

x

x

x b)

x

c)

d)

x

x

e)

x

x

22

x

x

x

f)

x

g)

x

x

h)

x

x

x

i)

x

x

x

x

Comentarii referitoare la figurile anterioare. Observăm că damă trebuie să fie plasată singura pe linie. Prozitionam prima damă pe linia 1,coloana1.

23

a) A doua damă nu poate fi aşezată decât în coloana 3.b) Observăm că a treia damă nu poate fi plasată în linia 3.Încercam

atunci plasarea celei de-a două dame în coloana 4.c) A treia damă nu poate fi plasată decât în coloana 2.d) În această situaţie damă a patra nu mai poate fi aşezată. Încercând să

avansăm cu damă a treia , observăm că nu este posibil să plasăm nici în coloană a-3-a, nici în coloană a-4-a, deci o vom scoate de pe tablă. Damă a doua nu mai poate avansa, deci şi ea este scoasă de pe tablă .Avansăm cu prima damă în coloană a-2-a.

e) A doua damă nu poate fi aşezată decât în coloană a-4-a.f) Damă a treia se aşează în prima coloană.g) Acum este posibil să plasăm a patra dată în coloana 3 şi astfel am

obţinut o soluţie a problemei.

Algoritmul continua în acest mod până când trebuie scoasă de pe tabla prima damă.

Pentru căutarea şi reprezentarea unei soluţii folosim un vector cu n componente,numit sol.Prin sol[i] înţelegem coloana în care se găseşte damă de pe linia i.

Soluţia cu ajutorul vectorului sol.

2 4 1 3

Două dame se găsesc pe aceeasi diagiagonala dacă şi numai dacă este indeplinita conditia:

| sol(i)-sol(j) | =| i-j |

sol(1)=1 i=1sol(3)=3 j=3 | sol(1)-sol(3) | =| 1-3 |2=2

sol(1)=3 i=1sol(3)=1 j=3 | sol(1)-sol(3) | =| 1-3 |

24

x

x

x

x

2=2

Întrucât două dame nu se pot găsi în aceeaşi coloană, rezultă că o soluţie este sub formă de premutare. O primă idee ne conduce la generarea tuturor permutărilor şi la extragerea solutilor pentru problema. Dacă procedăm astfel , înseamnă că nu lucrăm conform strategiei backtracking. Acesta ca inediat ce găsim două dame care se ataca , să reluăm căutarea în alte condiţii.

Faţă de programul de n dame are o singură condiţie suplimentară, în suprogramul valid.

Int valid(int k){ for(int i=1;i<k;i++) if(sol[k]==sol[i]) return 0; return 1;}

Problema este un exemplu folosit în mai toate lucrările în care este prezentată metoda backtracking.

Numar dame

1 2 3 4 5 6 7 8 9 10 11 12

Solutii unice

1 0 0 1 2 1 6 12 46 92 341 1.787

Total solutii

1 0 0 2 10 4 40 92 352 724 2.680 14.200

13 14 24 25 26

9.233 45.752 28.439.272.956.934 275.986.683.743.434 2.789.712.466.510.289

73.712 365.596 227.514.171.973.736 2.207.893.435.808.352

22.317.699.616.364.044

25

26

Bibliografie

• Manualul de informatică, cls. aXI-a • http://info.mcip.ro/?t=back• http://www.scribd.com/doc/8066145/Metoda-Backtracking• http://www.scritube.com/stiinta/informatica/Metode-de-programare3424121010.php

27