Problem n kraljica

Rjesavam jedan zadatak koji je identican problemu n kraljica(ajde,tu su umjesto kraljica pijuni koje treba postaviti na plocu tako da bude samo 1 u redu,stupcu i dijagonali(bilo kojoj),a treba ispisati tri moguca rjesenja(stupce pijuna) i broj mogucih rjesenja).Rjesavam to pomocu DFS-a koji ide otprilike:
1 search(col)
2 if filled all columns
3 print solution and exit

4 for each row
5 if board(row, col) is not attacked
6 place queen at (row, col)
7 search(col+1)
8 remove queen at (row, col)

OK,program radi.Ali ne dobro!
Prvo,on nadje rjesenja,ali nekim slucajem ona su drukcije poredana od onih koja bi trebala biti u izlaznoj datoteci koja se trazi.
Drugo,prespor je kod zadnjeg slucaja (13+).
Kako ga srediti da radi kako spada?!

Redosled rešenja zavisi od algoritma koji primenjuješ. Recimo, koristiš pretragu po različitim pravcima/smerovima (kojim redom biraš pravce za proveru), pretražuješ u dubinu po pravcu ili u širinu po pravcima...Kupi brži računar :D Pazi, ovo je normalno jer rešavanje problema nije linearno.

Potpis

BoxUp
interesantna logička igra
Monty Hall paradoks - interaktivni demo

Kako to mislis,po pravcima?
Problem je u tome sto ne znam BFS,a nije stvar u racunalu jer se to MORA izvrsiti u zadanom vremenu na TESTNOM racunalu.
Kako uopce radi BFS?

Pogledah u knjizi 'Algoritmi u programskom jeziku C'.
Izgleda da je DFS dovoljan uz par optimizacija:
1. Pokusaj da onu proveru da li je polje napadnuto napravis ne pretragom ostatka tabele vec uvedi flagove za sve redove/kolone/dijagonale, pa cim smestis kraljicu na tablu flagove za odgovarajuce pravce postavi na 'zauzeto' i proveru radi tako sto ces proveriti odgovarajuca 4 flag-a za polje.
2. Pokusaj da rekurzivni DFS transformises u ne-rekurzivni

E sad, da li ce na tom racunaru ovo biti dovoljno brzo... moras da probas.

N kraljica je prototipski AI problem, za koga ne postoji rešenje koje je posebno mnogo pametnije od običnog „bektrekinga“ (fin način da se kaže: isprobavanje svih mogućih varijanti).

Da bi se izvršavanje ubrzalo obično se koriste „pametne“ strukture poput uređenih binarnih stabala odlučivanja (ordered binary decision diagrams, OBDD). Sa donjeg linka može se preuzeti program koji N kraljica rešava superbrzo, korišćenjem datih struktura. Na žalost program zavisi od cele biblioteke (buddy), tako da verovatno nije praktičan kao „odgovor“ na pitanje.

http://www-2.cs.cmu.edu/~runej/publications/umop.html

Ono s flagovima ne radi:Recimo da postavis kraljicu na 1,1 i sve u redu i stupcu i dijagonalno oznacis sa 'zauzeto',a onda,recimo dodjes na 3,2,koje nije zauzeto,ponovis postupak sa oznacivanjem.Gle sad ovo,kad se vracas sa slijedeceg reda/stupca i maknes kraljicu sa 3,2, ono sto si za (3,2) oznacio sa zauzeto(redovi,stupci,dijagonale) sada "oslobodis",oslobodio si medju ostalim i 3,3.Eto ti problema:3,3 se prikazuje kao slobodno,a nije jer ga napada (1,1).Postoji li jos koji nacin?Ja bih probao BFS kad bih znao kako radi,a ne znam...

Hm - imam utisak da se nismo razumeli oko flagova.

Imas tablu NxN.
Ako kraljice redjas odozdo na gore trebaju ti flagovi za zauzete kolone i dijalonale (u oba smera). Dakle:
bool zauzete_kolone[N], zauzete_diagonale_45_stepeni[2*N-1], zauzete_kolone_135_stepeni[2*N-1].

Kada kraljicu stavis na tablu postavis tacno po jedan flag za odgovaraciji kolonu, odgovajucu dijagonalu pod 45 (glavna) i pod 135 stepeni (sporedna).
Kada kraljicu sklanjas te flagove brises.

Da li je dozvoljeno na nekom polju postaviti kraljicu proveravas tako sto proveris tacno po jednu kolonu, dijagonalu pod 45 i dijagonalu pod 135 stepeni.
Preslikavanje (red, kolona) -> (broj_kolone, broj_dijagonale_45, broj_dijagonale_135) je jednoznacno.

Nije bas da kuzim sto mislis,ali proucit cu to sto si napisao i javiti ti.U medjuvremenu sam shvatio da idem rekurzivno po redovima,a ne stupcima-->vrijedi li idalje ovo sto si napisao?

Da, vazi.
Ako ides red po red - imas flagove za kolone. Ako ides kolonu po kolonu imas flagove za redove.

Postoji prosto resenje: umesto boolean flag-ova koristis integer flag-ove (inicijalna vrednost 0).
Dakle, postoji tabela integera n*n. Stavis prvu kraljicu na neko polje, i zatim uradis INCREMENT flag-ova svih odgovarajucih polja, znaci postavi se vrednost 1. Zatim stavis drugu kraljicu, i takodje uradis increment odgovarajucih flag-ova (opet vrednost 1). Medjutim, ako se neka polja nalaze u "zoni delovanja" obe kraljice, njihov flag ce biti 2.
Sada obrnuto: maknemo jednu kraljicu i time uradimo DECREMENT odgovarajucih polja...itd. itd. Mislim da je ideja ocigledna.
Pozdrav

Rajko

Uspio sam danas nesto teoretski napraviti u Pascalu(na papiru) pomocu flagova(ono s incrementom bilo bi presporo).Pricekaj koji dan da probam u praksi.

Kao sto sam rekao,evo programa.
Da bi radio,mora postojati datoteka checker.in u kojoj pise broj redova (n). Nije bas da se iz njega moze vidjeti nesto,ali eto.Barem demonstrira vrijeme:-)

Hvala

---

...do iduceg susreta

Goran