Problema săriturii calului
ELEV: Zirbo Alin
CLASA:a XI-a B
Enunţul problemei
Se dă o tablă de şah cu dimensiunea n*n. Un
cal se găseşte în linia 1 şi coloana 1. Găsiţi un şir de
mutări ale calului astfel încât acesta să acopere
întreaga tablă fără a trece
printr-o căsuţă de două ori.
Pentru n=5 avem o tablă de
dimensiunea 5 linii şi 5 coloane
Algoritmul de rezolvare
Cele 8 poziţii în care poate sări calul sunt:
i-2
j-1
i-2
j+1
i-1
j-2
i-1
j+2
i,j
i+1
j-2
i+1
j+2
i+2
j-1
i+2
j+1
Toate elementele la început sunt egale cu 0 asta însemnând că
iniţial nu s-a trecut pe la nici un pătrat. Calul porneşte de pe poziţia
a[1,1] care va fi egal cu 1.
Numărul soluţiilor notat cu ns este la început 0 şi se măreşte cu 1
când se apelează procedura de afişare a matricii.
De la elementele a[i,j] sare dacă poate într-una dintre cele 8 direcţii
adică dacă trebuie să nu sară în afara tablei şi să nu mai fi trecut pe
acolo.
Dacă sare pe una din cele 8 poziţii se procedează astfel:
1. Elementele din matrice de pe acea poziţie primeşte ca valoare
pas.
2. Dacă pasul la care s-a ajuns este n*n, adică pas=n*n, atunci se
afişează matricea altfel se autoapelează asupra acestui element.
3. Elementele din matrice de pe acea poziţie primeşte valoarea 0.
Pentru a ajunge de la a[i,j] la una din cele 8 poziţii se folosesc
vectorii de direcţie: pentru linie di (-2,-1,1,2,2,1,-1,-2), pentru
coloană dj (1,2,2,1,-1,-2,-2,-1).
Implementarea algoritmului
ns - numărul soluţiilor
n – numărul de linii şi coloane
a – matrice pătratică
i,j – indicii elementului la care s-a ajuns
di – vector de poziţie pentru linie
dj – vector de poziţie pentru coloană
pas – pasul la care s-a ajuns
k – direcţiile
i1, j1 – coordonatele noii poziţii
Programul:
Program cal;
Type sir=array[1..8] of integer;
mat=array[1..20,1..20] of integer;
const di: sir=(-2,-1,1,2,2,1,-1,-2);
dj: sir=(1,2,2,1,-1,-2,-2,-1);
Var a:mat;
i,j,n,ns,pas:integer;
Procedure afis_mat;
Begin
ns:=ns+1;
writeln (‘solutia cu numarul’, ns, ‘este:’);
for i:=1 to n do begin
for j:=1 to n do
write(a[i,j]:3);writeln;end;
end;
procedure calul(var a:mat; i,j,pas:integer);
var k,i1,j1:integer;
cond:boolean;
begin
for k:=1 to 8 do begin
i1:=i+di[k];
j1:=j+dj[k];
cond:=(i1 in [1..n]) and (j1 in [1..n]) and (a[i1,j1]=0);
if cond then begin
a[i1,j1]:=pas;
if pas=n*n then afis_mat
else calul(a,i1,j1,pas+1);
a[i1,j1]:=0; end;
end;
Begin
write(‘n=‘);readln(n);
For i:=1 to n do
for j:=1 to n do a[i,j]:=0; a[1,1]:=1; ns:=0;
pas:=2;
calul(a,1,1,pas);
readln;
End.
