Ne znam da li neko jeste, verovatno da, ali nacin za to je jednostavan. Imas moguce poteze, probas jedan, pa onda opet jedan od mogucih sa te pozicije i tako dok ne upadnes u poziciju iz koje nemas nikakav moguci potez. Onda se vratis jedan korak i probas nesto drugo. Kad je level resen, koraci koje si izveo su resenje istog.
E sad, to se da optimizovati tako sto postoje stituacije koje ne smes imati (pa je dalje ispitivanje u tom smeru bespotebno) kao sto je ubacivanje sanduka u ugao, spajanje 4 komada u kvadrat i sl. (to mozes proveriti pri svakom potezu i smatrati da je to potez nakon kojeg nemas gde pa se vracas za jedan.
Ja sam se neshto malo interesovao za to, pre godinu-dve, i koliko sam shvatio, problem nije nimalo jednostavan. Naime, prostor pretrage je veoma veliki, stoga je i velika kompleksnost algoritma. Moj primarni resurs za to je bio http://www.cs.ualberta.ca/~games/Sokoban/.
Mislim da metod isprobavanja svakog poteza u datom slucaju stvarno nije efikasan, obzirom na shirinu prostora za pretragu.
Ako neko zeli da se bavi ovom problematikom, preporucio bih sledece ideje:
- napraviti putanje svake kuglice/sanduka/sta vec od pocetne pozicije do zavrsne pozicije/zavrsnih pozicija (objekat moze zavrsiti na vise razlicitih pozicija) (ovih putanja ima dosta, ali mnogo manje nego kombinacija poteza).
- problem prebaciti u 3D, gde ce koordinata u trecoj dimenziji predstavljati vreme, odnosno potez, pomeraj ili sta vec.
- ispitati koja kombinacija putanja je validna u 3d prostoru.
Umesto backtracka o kome pricate (pronalazenja resenja putem pokusaja i greske), mislim da bi bilo bolje koristiti A* algoritam, naravno, sve zavisi od velicine matrice i dostupne memorije...
Resenje ne bi bilo mnogo tesko, pravila su tacno odredjena...
Obichnim A* algoritmom ne mozesh da reshish nijedan (netrivijalan) sokoban nivo. Ova grupa (sa stranice koju sam naveo gore) je krenula sa modifikacijom A* koji se naziva IDA*, pa su dodavali poboljshanja i reshavali sve vishe i vishe nivoa. IDA* je reshila ukupno 0 problema :).
Resavanje sokoban nivoa
Registrovani: 7 ( bakara, Shadowed, kumkat, Texas Instruments, bojanum, Evans D, Darko_zed )