utorak, 8. siječnja 2013.

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!

2 komentara:

  1. Kraljice u šahu mogu napadati i u stupcu i dijagonalno, ne samo u retku!

    OdgovoriIzbriši
    Odgovori
    1. Sama ideja programa je uredu, ali kada sam radio slike nisam mislio da se neće vidjeti u kojem retku se nalazi određena kraljica. Tako da je sve uredu što se samoga članka tiće, samo ću sliku kada školsko završi promjeniti.
      https://docs.google.com/viewer?a=v&pid=sites&srcid=ZGVmYXVsdGRvbWFpbnxsb3Zyb3NocnxneDo1OTVhZmQzZGE5YjEzZGZm
      U gornjem linku nalazi ti se to u Google docu pa tamo možeš možda bolje pogledati u kojem se retku nalazi kraljica.
      Hvala na uočenoj progrešci!

      Izbriši