Problema damelor

Problema celor opt dame, asezate pe o tabla de 8x8, cunoscuta la nivel mondial ca si The 8 Puzzle Queens, problema standard, consta in asezarea a opt dame pe table 8x8, care nu trebuie sa se atace intre ele. Pentru a gasi solutia corecta, nu trebuie sa existe doua dame pe aceasi linie, coloana, sau diagonala.

Istoric:

Problema a fost prima data propusa in 1848 de catre jucatorul de sah Max Bezzel si peste cativa ani de mai multi matematiceni printre care si Johann Carl Friedrich Gauss care a lucrat la acesta problema si la problema generala. Prima solutie a fost gasita de Franz Nauck in 1850. Tot Nauck a generalizat problema. In 1874, S. Gunther a propus o metoda de gasire a solutilor folosind determinantul.

Edsger Dijkstra a folosit aceasta problema in 1972 pentru a ilustra ceea ce noi numim structura de programare. El a publicat o descriere foarte detaliata a primului algoritm de backtracking.

Aflarea solutiei:

Problema pare destul de complicata, fiind 4.426.165.368 de cazuri posibile de a pune cele opt dame pe tabla de 8x8 si doar 92 de soluti corecte. Dintre cele 92 de solutii, exista doar 12 cazuri unice sau fundamentale.

Caz 1

Caz 2.

Caz 3.

a b c d e f g h

X 8

X 7

X 6

X 5

X 4

X 3

X 2

X 1

a b c d e f g h

X 8

X 7

X 6

X 5

X 4

X 3

X 2

X 1

Caz 4.

Caz 5.

Caz 6.

a b C d e f g h

X 8

X 7

X 6

X 5

X 4

X 3

X 2

X 1

a b c d e f g h

X 8

X 7

X 6

X 5

X 4

X 3

X 2

X 1

a b c d e f g h

X 8

X 7

X 6

X 5

X 4

X 3

X 2

X 1

a b c d e f g h

X 8

X 7

X 6

X 5

X 4

X 3

X 2

X 1

Caz 7.

Caz 8.

Caz 9.

Caz 10.

a b c d e f g h

X 8

X 7

X 6

X 5

X 4

X 3

X 2

X 1

a b c d e f g h

X 8

X 7

X 6

X 5

X 4

X 3

X 2

X 1

a b c d e f g h

X 8

X 7

X 6

X 5

X 4

X 3

X 2

X 1

a b c d e f g h

X 8

X 7

X 6

X 5

X 4

X 3

X 2

X 1

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ă;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

a b c d e f g h

X 8

X 7

X 6

X 5

X 4

X 3

X 2

X 1

a b c d e f g h

X 8

X 7

X 6

X 5

X 4

X 3

X 2

X 1

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

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

2. Acum putem extrage farfuria roşie.

2. Exemplificarea lucrului cu stiva:1. n stiva iniţial vidă se introduce elementul A şi vârful stivei va fi nivelul 1 (k=1).2. Introducem în stivă elementul B, deci vârful stivei va fi nivelul 2 (k=2).3. 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).4.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:- 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).

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.

Î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:

         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{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 atacă dacă ele se află pe aceeaşi linie, pe aceeaşi coloana sau pe aceeaşi diagonala. Aceată problema fuctioneaza doar pentru n=1 sau n>=4.

De exemplu, daca n=4, o solutie este reprezentata in figuria a.modul de obtinere al solutiei este prezent in figurile urmatoare, de la b la i.

a)

x

x

x

x b)

x

c)

x

x

d)

x

x

e)

x

x

x

f)

x

g)

x

x

h)

x

x

x

i)

x

x

x

x

Comentarii referitoare la figurile anterioare.b) Observam ca dama trebuie sa fie plasata singura pe linie. Prozitionam prima

dama pe linia 1,coloana1.c) A doua dama nu poate fi asezata decat in coloana 3.d) Observam ca a treia dama nu poate fi plasata in linia 3.Incercam atunci plasarea

celei de-a doua dame in coloana 4.e) A treia dama nu poate fi plasata decat in coloana 2.f) In aceasta situatie dama a patra nu mai poate fi asezata. Incercand sa avansam cu

dama a treia , observam ca nu este posibil sa plasam nici in coloana a-3-a, nici in coloana a-4-a, deci o vom scoate de pe tabla. Dama a doua nu mai poate avansa, deci si ea este scoasa de pe tabla .Avansam cu prima dama in coloana a-2-a.

g) A doua dama nu poate fi asezata decat in coloana a-4-a.h) Dama a treia se aseaza in prima coloana.i) Acum este posibil sa plasam a patra data in coloana 3 si astfel am obtinut o

solutie a problemei.

Algoritmul continua in acest mod pana cand trebuie scoasa de pe tabla prima dama.

Pentru cautarea si reprezentarea unei solutii folosim un vector cu n componente,numit sol.Prin sol[i] intelegem coloana in care se gaseste dama de pe linia i.

Solutia cu ajutorul vectorului sol.

2 4 1 3

Doua dame se gasesc pe aceeasi diagiagonala daca si numai daca 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 |2=2

Intrucat doua dame nu se pot gasi in aceeasi coloana, rezulta ca o solutie este sub forma de premutare. O prima idee ne conduce la generarea tuturor permutarilor si la extragerea solutilor pentru problema. Daca procedam astfel , inseamna ca nu lucram conform strategiei backtracking. Acesta ca inediat ce gasim doua dame care se ataca , sa reluam cautarea in alte conditii.

Fata de programul de n dame are o singura conditie suplimentara, in 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 in mai toate lucrarile in care este prezentata metoda backtracking.

Numar dame

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

x

x

x

x

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

Bibliografie

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