Sokoban is a type of transport puzzle, in which the player pushes boxes around a maze, viewed from above, and tries to put them in predetermined areas. Only one box  may be pushed at a time, and boxes cannot be pulled. The numbers of boxes is equal to designated locations. The puzzle may have limited the number of steps. The puzzle is usually implemented as a video game.
Sokoban was created in 1981 by Hiroyuki Imabayashi, and was published in 1982 by Thinking Rabbit, a software house based in Takarazuka, Japan.

Scientific research on Sokoban

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 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.
Some Sokoban puzzles can be solved automatically by using a single-agent search algorithm, such as IDA*, enhanced by several techniques which make use of domain-specific knowledge. This is the method used by Rolling Stone, a Sokoban solver developed by the University of Alberta GAMES Group. The more complex Sokoban levels are, however, out of reach even for the best automated solvers.
In actual games available, however, a lot of the levels are easily solved by "elimination": all immediate moves except one end in blocking the game; as you eliminate these moves you quickly and easily find out there is only one option for the next immediate move, even though you don't yet (have to) see the full consequences of that move. This all without having to think too many steps ahead.