Programs: Computation and Complexity Theory

In case you didn't know, Sokoban is a very old computer game in which the player has to help a warehouse worker push a number of boxes to the designated positions through a labirynth of corridors. The main difficulty is that the boxes can only be pushed, not pulled, so it's quite easy to put them in such position that they can't be moved anymore. You can try the game e.g. here.

The goal of this project was to create such algorithm that would automatically solve any Sokoban boards given on the input. It had to find not only a correct solution, but also do it in a sufficiently short time... The algorithm is based on A* (A-Star) Algorithm.