Post on 28-Jan-2015
description
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.