Papers About Sokoban

Complexity

Joe Culberson of the University of Alberta proved Sokoban to be PSPACE complete in Sokoban is PSPACE-complete (1997).

Dorit Dor and Uri Zwick of Tel Aviv University proved Sokoban to be PSPACE hard in 1995 in Sokoban and other motion planning problems and considered a few generalizations.

Finding Solutions

Andreas Junghanns and Jonathan Schaeffer at the University of Alberta wrote about solving sokoban problems in Sokoban: A Challenging Single-Agent Search Problem, which was presented at the IJCAI workshop on Using Games as an Experimental Testbed for Artificial Intelligence Research in August, 1997.

Junghanns and Schaeffer update and extend their paper in Sokoban: Evaluating Standard Single-Agent Search Techniques in the Presence of Deadlock.

Making Levels

Yoshio Murase, Hitoshi Matsubara and Yuzuru Hiraga of the University of Library and Information Science in Japan presented Automatic Making of Sokoban Problems at the Pacific Rim Conference on AI in 1996.