[areyousure]

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-883...

See also https://erikdemaine.org/papers/NCL_TCS/

[moritzwarhier]

Yes, correct, and mentioned in the abstract. Sorry, I was imprecise and wrong.

Thanks for the links!