Probleme 2
Sa se aseze n tute pe o tabla de sah cu n linii si n coloane astfel incat sa nu se poata ataca una pe alta.
Aceasta problema este de fapt problema de generare a permutarilor, insa, de data aceasta, vom afisa o schema a tablei de sah pentru a arata pozitiile unde se gasesc turele.
2 ture se pot se ataca daca sunt pe aceiasi linie sau pe aceiasi coloana.
Datorita faptului ca vom completa pe rand liniile de pe tabla de sah, punand pe fiecare linie cate o tura, nu este nevoie sa punem conditii pentru a nu a aprea 2 ture pe aceiasi linie.
x[k] reprezinta coloana de pe linia k ocupata de tura.
Nu este gresit nici daca afisarea se face ca si la permutari insa este greu de urmarit pozitia turelor pe tabla.
In plus, la aceasta problema vom numara si solutiile.
De exemplu, daca se introduce n=5 solutiile se vor afia astfel:
solutia 7
T * * * *
* * T * *
* T * * *
* * * T *
* * * * T
solutia 8
T * * * *
* * T * *
* T * * *
* * * * T
* * * T *
Numarul de solutii pentru n=5 este de 120.
Observam ca numarul minim este 1 (prima coloana) si numarul maxim este n(ultima coloana).
Datorita faptului ca vom completa liniile succesiv, acestea nu au cum sa se repete, prin urmare singura conditie este sa nu se repete coloanele.
Avem solutie daca s-au asezat pe tabla toate cele n ture.
var x:array[1..50]of byte;
k,n,nr:byte;valid:boolean; f:text;
procedure posibil(k:integer;var valid:boolean);
var i:integer;
begin
valid:=true;
for i:=1 to k-1 do
if(x[k]=x[i])then valid:=false;/*2 ture nu se pot afla pe aceiasi coloana*/
end;
function solutie(k:integer):boolean;
begin /*avem solutie cand am asezat toate cele n ture*/
if(k=n) then solutie:=true
else solutie:=false;
end;
procedure afisare(k:integer);
var i,j:byte;
begin
nr:=nr+1;
writeln(f,'solutia ',nr);
for i:=1 to k do
begin
for j:=1 to k do
if (x[i]=j) then write(f,'T ') /*daca pe linia i este completata coloana j, vom specifica acest lucru*/
else write(f,'* ');
writeln(f);
end;
writeln(f);
end;
procedure back;
begin
k:=1;
x[k]:=0;
while(k>0) do begin
valid:=false;
while(not valid)and(x[k]<n) do
begin
x[k]:=x[k]+1;
posibil(k,valid);
end;
if(not valid) then k:=k-1
else if(solutie(k)) then afisare(k)
else begin
k:=k+1;
x[k]:=0;
end;
end;
end;
begin
write('numarul de linii si coloane=');readln(n);
assign(f,'ture.txt');
rewrite(f);
nr:=0;
back;
close(f);
end.
Sa se aseze n nebuni pe o tabla de sah cu n linii si n coloane fara a se putea ataca unul pe altul.
Vom aseza, pe rand, cate un nebun pe linie, prin urmare liniile nu se repeta.
x[k] - coloana ocupata pe linia k de catre un nebun.
2 nebuni se pot ataca unul pe altul daca ei se gasesc pe aceiasi diagonala. Putem gasi formula pentru diagonala punand pe axa XOY pe x[k], x[i], i, k care reprezinta de fapt, coloanele si respectiv liniile pe care se afla cei 2 nebuni. Vom schita astfel pe OX coloanele x[k], x[i] si pe OY liniile k si i. Vom avea astfel 4 situatii si vom deduce ca cei 2 nebuni se gasesc pe aceiasi diagonala daca abs(x[k]-x[i])=abs(k-i). Remintim ca functia abs se foloseste pentru calcularea modulului.
Pentru n=5 se gasesc 125 de solutii pe care le vom shita sub forma de mai jos:
solutia 120
* * * * N
* * * * N
N * * * *
* * * * N
* * * * N
solutia 121
* * * * N
* * * * N
* N * * *
* * * * N
* * N * *
Observam ca valoarea minima este 1 (prima coloana) si valoarea maxima este n (ultima coloana).
Avem solutie cand au fost asezati toti cei n nebuni, fiecare pe cate o linie.
2 nebuni nu se pot ataca daca se gasesc pe aceiasi diagonala.
var x:array[1..50]of byte;
k,n,nr:byte;valid:boolean; f:text;
procedure posibil(k:integer;var valid:boolean);
var i:integer;
begin
valid:=true;
for i:=1 to k-1 do
if(abs(x[k]-x[i])=abs(k-i))then valid:=false; /*cei doi nebuni nu trebuie sa se atace - nu trebuie sa fie pe aceiasi diagonala*/
end;
function solutie(k:integer):boolean;
begin /*avem solutie cand am asezat pe tabla cei n nebuni*/
if(k=n) then solutie:=true
else solutie:=false;
end;
procedure afisare(k:integer);
var i,j:byte;
begin
nr:=nr+1;
writeln(f,'solutia ',nr);
for i:=1 to k do
begin
for j:=1 to k do
if (x[i]=j) then write(f,'N ')
else write(f,'* ');
writeln(f);
end;
writeln(f);
end;
procedure back;
begin
k:=1;
x[k]:=0;
while(k>0) do begin
valid:=false;
while(not valid)and(x[k]<n) do
begin
x[k]:=x[k]+1;
posibil(k,valid);
end;
if(not valid) then k:=k-1
else if(solutie(k)) then afisare(k)
else begin
k:=k+1;
x[k]:=0;
end;
end;
end;
begin
write('numarul de linii si coloane=');readln(n);
assign(f,'nebuni.txt');
rewrite(f);
nr:=0;
back;
close(f);
end.
Sa se aseze n dame (regine) pe o tabla de sah cu n linii si n coloane astfel incat sa nu se poata ataca una pe alta.
Problema este o combinatie intre problema turelor (prima problema de pe pagina) si problema nebunilor (cea de-a doua problema de pe pagina).
2 dame nu se pot ataca daca nu se gasesc pe aceiasi linie, coloana sau diagonala.
Punand damele pe rand, cate una pe o line k=1...n nu e nevoie sa verificam daca damele se gasesc pe aceiasi linie.
2 dame se gasesc pe aceiasi coloana daca exista i=1...k-1 astfel incat x[k]=x[i].
2 dame se gasec pe aceiasi diagonala daca exista i=1...k-1 astfel incat abs(x[k]-x[i])=abs(k-i).
Solutiile (in numar de 10 pentru n=5) arata in felul urmator:
solutia 3
* D * * *
* * * D *
D * * * *
* * D * *
* * * * D
solutia 4
* D * * *
* * * * D
* * D * *
D * * * *
* * * D *
Observam ca valoarea minima este 1(prima coloana) si valoarea maxima este n (ultima coloana).
Avem solutie cand s-au depus toate cele n dame.
In functia posibil vom trata cazurile in care prin depunerea unei regine pe linia k in pozitia x[k] exista posibilitatea ca pe tabla de sah sa fie 2 dame care sa se poata ataca una pe alta.
var x:array[1..50]of byte;
k,n,nr:byte;valid:boolean; f:text;
procedure posibil(k:integer;var valid:boolean);
var i:integer;
begin
valid:=true;
for i:=1 to k-1 do
if(abs(x[k]-x[i])=abs(k-i))or(x[i]=x[k])then valid:=false; /*2 dame nu pot sa se afle pe aceiasi coloana sau pe aceiasi diagonala*/
end;
function solutie(k:integer):boolean;
begin /*am ajuns la o solutie cand s-au depus pe tabla toate cele n dame*/
if(k=n) then solutie:=true
else solutie:=false;
end;
procedure afisare(k:integer);
var i,j:byte;
begin /*afisam solutia*/
nr:=nr+1;
writeln(f,'solutia ',nr);
for i:=1 to k do
begin
for j:=1 to k do
if (x[i]=j) then write(f,'D ')
else write(f,'* ');
writeln(f);
end;
writeln(f);
end;
procedure back;
begin
k:=1;
x[k]:=0;
while(k>0) do begin
valid:=false;
while(not valid)and(x[k]<n) do
begin
x[k]:=x[k]+1;
posibil(k,valid);
end;
if(not valid) then k:=k-1
else if(solutie(k)) then afisare(k)
else begin
k:=k+1;
x[k]:=0;
end;
end;
end;
begin
write('numarul de linii si coloane=');readln(n);
assign(f,'dame.txt');
rewrite(f);
nr:=0;
back;
close(f);
end.
