[es] - Problem n kraljica

Humanoid
Hrvatska

Član broj: 10689
Poruke: 63
*.cmu.carnet.hr

ICQ: 170788654

Profil

^{05.12.2003. u 23:13 - pre 248 meseci}

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?!

Prikačeni fajlovi

checker.pas - 1.69k

Odgovor na temu

noviKorisnik
Dejan Katašić
Novi Sad

Član broj: 13216
Poruke: 4533
*.bankmeridian.com

Sajt: www.novikorisnik.net

+5 Profil

Re: Problem n kraljica

^{06.12.2003. u 09:21 - pre 247 meseci}

Citat:

Humanoid:
...treba ispisati tri moguca rjesenja(stupce pijuna) i broj mogucih rjesenja

Prvo,on nadje rjesenja,ali nekim slucajem ona su drukcije poredana od onih koja bi trebala biti u izlaznoj datoteci koja se trazi.

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...

Citat:

Drugo,prespor je kod zadnjeg slucaja (13+).

Kupi brži računar :D Pazi, ovo je normalno jer rešavanje problema nije linearno.

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

Odgovor na temu

Humanoid
Hrvatska

Član broj: 10689
Poruke: 63
*.cmu.carnet.hr

ICQ: 170788654

Profil

Re: Problem n kraljica

^{07.12.2003. u 06:24 - pre 247 meseci}

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?

Odgovor na temu

sspasic
Sasa Spasic

Član broj: 3261
Poruke: 175
*.medianis.net

Jabber: sspasic@elitesecurity.org
ICQ: 35454521

Profil

Re: Problem n kraljica

^{07.12.2003. u 10:44 - pre 247 meseci}

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.

Odgovor na temu

filmil
Filip Miletić
Oce Technologies B.V., inženjer
hardvera
Arcen, NL

Član broj: 243
Poruke: 2114
*.adsl.zonnet.nl

Jabber: filmil@jabber.org
ICQ: 36601391

+3 Profil

Re: Problem n kraljica

^{07.12.2003. u 11:48 - pre 247 meseci}

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

Odgovor na temu

Humanoid
Hrvatska

Član broj: 10689
Poruke: 63
*.cmu.carnet.hr

ICQ: 170788654

Profil

Re: Problem n kraljica

^{09.12.2003. u 13:54 - pre 247 meseci}

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...

Odgovor na temu

sspasic
Sasa Spasic

Član broj: 3261
Poruke: 175
*.medianis.net

Jabber: sspasic@elitesecurity.org
ICQ: 35454521

Profil

Re: Problem n kraljica

^{09.12.2003. u 17:22 - pre 247 meseci}

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.

Odgovor na temu

Humanoid
Hrvatska

Član broj: 10689
Poruke: 63
*.cmu.carnet.hr

ICQ: 170788654

Profil

Re: Problem n kraljica

^{09.12.2003. u 17:56 - pre 247 meseci}

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?

Odgovor na temu

sspasic
Sasa Spasic

Član broj: 3261
Poruke: 175
*.medianis.net

Jabber: sspasic@elitesecurity.org
ICQ: 35454521

Profil

Re: Problem n kraljica

^{09.12.2003. u 21:24 - pre 247 meseci}

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

Odgovor na temu

Rapaic Rajko
Bgd

Član broj: 4105
Poruke: 810
80.93.225.*

+62 Profil

Re: Problem n kraljica

^{10.12.2003. u 10:46 - pre 247 meseci}

Citat:

Humanoid:
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...

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

Odgovor na temu

Humanoid
Hrvatska

Član broj: 10689
Poruke: 63
*.cmu.carnet.hr

ICQ: 170788654

Profil

Re: Problem n kraljica

^{10.12.2003. u 21:20 - pre 247 meseci}

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.

Odgovor na temu

Humanoid
Hrvatska

Član broj: 10689
Poruke: 63
*.cmu.carnet.hr

ICQ: 170788654

Profil

Re: Problem n kraljica

^{13.12.2003. u 06:37 - pre 247 meseci}

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

Prikačeni fajlovi

checker.pas - 1.97k

Odgovor na temu