Solving the Sokoban problem

Sokoban je igra s preprostimi pravili, vendar pa je reševanje kar velik zalogaj tako za človeka kot tudi računalnik. Ta problem je NP-težek, kar pomeni, da zanj domnevno ne obstaja polinomsko časovno omejen algoritem. Da najdemo optimalno rešitev, moramo pregledati vsa stanja. Zato se za reševanje uporabljajo iskalni algoritmi. Če želimo najti rešitev v krajšem času, moramo poiskati in implementirati kakovostno hevristiko. Vendar pa tudi trenutno najboljši programi za reševanje tega problema še dandanes niso sposobni najti rešitve za vse primereto ne čudi, saj je problem NP-težek. Teoretični del te diplomske naloge je analiza problema Sokoban in NP-težkih problemov. Praktični del pa implementacija lastnega algoritma, ki smo ga primerjali z znanim algoritmom JSoko.Sokoban is a game with simple rules, but finding solutions is a hard task for both people and computers. Sokoban is a NP-hard problem, which means that we probably cannot find every optimal solution in polynomial time. Instead, we must check all possible states in order to find the optimal solution. Thus, search algorithms are used for solving Sokoban. If we want to find a solution in a reasonable time, we need to find and implement good heuristics. Of course, because Sokoban is NP-hard, even the best current algorithms cannot find solutions to all Sokoban puzzles. The theoritical part of the thesis is analysis of the Sokoban problem and NP-hard problems. Practical part consists of description of our algorithm. We also tested our algorithm and compared it to a well-known algorithm JSoko