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/.
Pozdrav, Mladen.