Сокобан (от яп. «складовщик») — логическая головоломка Хироюки Имабаяси 1981 года. Некоторые сложные уровни до сих пор не решены оптимально даже компьютерами.
Расставьте ящики на отмеченные позиции, только толкая.
Стратегия: прежде чем толкать ящик, мысленно проверьте весь путь до цели.
Sokoban был первой игрой, для которой профессиональные математики начали серьёзно изучать сложность как класс P/NP. В 1997 году доказано: общая задача Sokoban — PSPACE-полная, что означает её принципиальную алгоритмическую трудность.