Soko-Ban

Sokoban can be studied using the theory of computational complexity. The problem of solving Sokoban puzzles has been proven to be NP-hard. This is interesting also for artificial intelligence researchers, because solving Sokoban can be compared to designing a robot which moves boxes in a warehouse. Further work has shown that solving Sokoban is also PSPACE-complete.

Sokoban is difficult not only due to its branching factor (which is comparable to chess, but still much lower than that of go), but also its enormous search tree depth; some levels require more than 1000 "pushes". Skilled human players rely mostly on heuristics; they are usually able to quickly discard futile or redundant lines of play, and recognize patterns and subgoals, drastically cutting down on the amount of search.