Головоломки типа Sokoban считаются NP-трудными, потому что вычисление оптимального алгоритма прохождения игры требует большого количества перемещений персонажа и ящиков. 2

Это связано с тем, что в игре сильное ветвление дерева решений и большая его глубина. 45 Чтобы найти верное решение, нужно перебрать много вариантов. 1 На некоторых уровнях количество «правильных» ходов, ведущих к выигрышу, может достигать тысячи. 1

В 1995 году было доказано, что задача решения уровней Sokoban — NP-трудна. 45