Problem kraljica

[Ryssa]

Evo jedan kombinatorni problem pa ako se nekome da probati razmislit ili da me nekako uputi...imamo šahovsku ploču dimenzija 8x8...Na početku biramo k kraljica koje postavljamo na ploču tako da se niti jedna kraljica ne napada...Polja na koja stavljamo k kraljica biramo sami i ako kraljicu stavimo na nedopušteno mjesto (gdje je izložena drugim kraljicama) program javlja da je mjesto nedopušteno i dopušta da ponovno biramo mjesto. Dakle na šahovskoj ploči imamo k fiksnih kraljica. Program treba izračunati koliko maximalno kraljica može biti na šahovskoj ploči ako znamo da je k kraljica već postavljeno na ploču.

[goranm]

Nije jasno zelis li:

program ciji je input k i raspored kraljica, a output maksimalan broj kraljica koji se moze naknadno postaviti, ili

maksimalan broj kraljica koji se moze postaviti za svaki dopusten raspored k kraljica

Ako je ovo prvo, onda je to jednostavna setnja po 8x8 matrici. Ako je ovo drugo, onda broj ovisi o rasporedu. Postoji jedan raspored za k=4 kraljica u kojem je maksimalan broj 7 i drugi za koji je maksimalan broj 8.

_________________
The Dude Abides

[Ryssa]

Mislila sam na ovaj prvi slučaj kada imamo k fixnih kraljica i njih više ne premiještamo nego nas zanima koliko se još može dodati kraljica da se međusobno ne napadaju. Program samo vraća ukupan mogući br kraljica na ploči (k fixnih + max br kraljica koje možemo dodati). Je li to onda modificirani slučaj problema 8 kraljica (rekurzija) i koristi li se backtracking? Naime uvjet je da se program izvede u 2 sec.

[goranm]

[Ryssa]

Nema uvjeta na složenost, samo da vrijeme izvršavanja mora biti max 2 sec, valjda se to misli na neko prosječno današnje računalno, ne znam. Hvala ipak

[satja]

Prekrizis sva napadnuta polja. Na sve nacine odaberes gdje ces staviti prvu kraljicu (na neko polje koje nije prekrizeno), prekrizis polja koja ona napada i daljnje kraljice postavljas na isti nacin rekurzivno. To je mnogo efikasnije nego da odmah biras sve mogucnosti i onda provjeravas nenapadanje.

Moze se to jos optimizirati. U globalnoj varijabli pamtis najbolje dosad pronadjeno rjesenje (M) i ako vidis da u trenutnoj grani rekurzije imas (broj_postavljenih_kraljica + broj_neprekrizenih_polja) <= M, tu granu mozes odmah odrezati jer iz nje neces poboljsati rjesenje. Osim toga, jasno je da ne mozes postaviti vise od 8 - K kraljica pa ako rekurzija dodje do te dubine, mozes prekinuti sve daljnje trazenje jer je sigurno pronadjen optimum.