Pripreme za algoritme(25)

 Problem n kraljica

Potrebno je generirati sve moguće rasporede n kraljica na poopćenoj šahovskoj ploči dimenzija n*n takvih da se nijedan par kraljica međusobno ne napada.
Uočimo prvo jednu bitnu činjenicu: svaki takav raspored sadrži točno jednu kraljicu u svakom stupcu. Stoga je za odabir jednog rasporeda dovoljno u svakom retku odabrati poziciju na kojoj će se nalaziti kraljica. Zato jednu poziciju n kraljica na ploči pamtimo kao niz od n pozicija. Pri postavljanju nove kraljice razmatramo samo pozicije u trenutnom retku koje nisu "napadnute" od već postavljenih kraljica.
Glavna funkcija programa (rekurzivna) trebala bi izgledati ovako :
procedura postavi_kraljicu (red)
i : integer
begin
if red >= n then
ispis_rasporeda_kraljica
else
begin
for i = 1 to n
begin
if ploca[red,i] "nije napadnuta" then
begin
ploca[red,i] = kraljica
postavi_kraljicu (red+1)
end
end
end
end

Ploča na koju raspoređujemo kraljice (ploca) i njezina dimenzija (n) deklarirane su radi uštede memorije kao globalne varijable. Naime, program u svakom trenutku koristi samo jednu ploču, pa je puno bolja ideja deklarirati ploču kao globalnu varijablu, nego kao parametar rekurzivne funkcije čime bi se dodatno opteretila memorija. Stupci i reci su indeksirani kao 1,2,...,n. Za n = 6 rješenje bi

bilo ovakvo :

Evo toliko od algoritama za danas još do školskog je ostalo par analiza zadataka i jedan algoritam.
Pozdrav!