Problema celor n dame

ElevElev: Fanea : Fanea Sandu Clasa a Sandu Clasa a XI-a BXI-a B

Enunţul problemeiFiind dată o tablă de şah cu

dimensiunea n*n, 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ă (damele să nu atace reciproc).

n=4 4X4

4 dame

n=4 4X4

4 dame

Soluţia 1

Soluţia 2

n=4 4X4

4 dame

2

4

1

3

3

1

4

2

st

st

Exemplul

Algoritmul de rezolvarePentru rezolvare se vor folosi:

k – variabilă întreagă, care reprezintă linia pe care se aşează a k-a damă

st– vector cu componente întregi cu proprietatea:stk reprezintă coloana pe care se aşază a k-a

damăDeoarece tabla are n linii şi n coloane k={1,…,n} şi stk={1,…,n} st=(st1, st2 ,…, stn) unde stkЄ{1,…,n}

kЄ{1,…,n}Următoarele desene ilustrează când dama k şi dama i se află pe aceeaşi diagonală: k-i=stk-sti(trebuie ca damele să fie aşezate în colţurile unui

pătrat cu latura k-i, respectiv stk-sti)

k

i

sti stk

k

i

stk

sti

k-i=sti-stk (trebuie ca damele să fie aşezate în colţurile unui pătrat cu latura k-i, respectiv sti -stk)

Trebuie verificat că dama k nu se află pe aceeaşi coloană sau pe aceeaşi diagonală cu dama i, unde i=1…k-1, adică trebuie arătat că: stk <>sti şi k-i<>|stk -sti| pentru i=1…k-1

Implementarea algoritmului

k – este o valoare întreagă pe care o reprezintă linia pe care se aşează a k a damă

st – este un vector cu componente întregi cu proprietatea că coloane pe care se aşează atunci a k a damă

n – numărul de linii şi de coloane

Programul

program dame;type stiva=array[1..20] of integer;var st:stiva;

n,k:integer;as, ev:boolean;

procedure init(k:integer; var st:stiva);beginst[k]:=0;end;procedure succesor(var as:boolean; var st:stiva; k:integer);begin

if st[k]<n then begin st[k]:=st[k]+1; as:=true; end

else as:=falseend;

procedure valid(var ev:boolean; st:stiva; k:integer);var i:integer;begin

ev:=true;for i:=1 to k-1 do if (st[k]=st[i]) or (abs(st[k]-

st[i])=abs(k-i)) then ev:=false;end;function solutie(k:integer):boolean;begin

if k=n then solutie:=true else solutie:=false;end;procedure tipar;var i:integer;begin

for i:=1 to n do write(st[i],' ');writeln;

end;

BEGIN write('n= '); readln(n);k:=1;init(k,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+1; init(k, st); end

else k:=k-1; end;readln;

END.