Problema celor 8 dame

Daca se considera 2 elemente pe aceeasi diagonala (i,j) ,(k,l)

i-j=k-l sau i+j=k+l

j-l=i-k j-l=k-i

adica se poate folosi conditia |j-l|=|k-i|.

Construim functia place(k) care returneaza true daca dama cu numarul de ordine k poate fi plasata pe coloana data de x(k). Operatiile care se fac sint:

- se testeaza daca x(k) != x(i) i=1,2,.k-1

- se testeaza daca nu alta dama in aceeasi diagonala.

Functia place lucreaza in O(k-1)

place(k)

return true

n_queen (n)

x(1..n) - vectorul de solutii

x(1)=0; k=1;

while (k>

}

else

k=k-1; // x(k) > n backtrack

}