That paper does not prove that Sokoban is NP-hard. It does, however, cite an earlier paper proving the stronger result that Sokoban is PSPACE-complete: Culbers

That paper does not prove that Sokoban is NP-hard. It does, however, cite an earlier paper proving the stronger result that Sokoban is PSPACE-complete: Culberson, Joseph. "Sokoban is PSPACE-complete." (1997). https://era.library.ualberta.ca/items/f551dfd8-c8e6-4e78-883d-3afbee5bce83 https://era.library.ualberta.ca/items/f551dfd8-c8e6-4e78-883... See also https://erikdemaine.org/papers/NCL_TCS/ https://erikdemaine.org/papers/NCL_TCS/