FWIW there's a proof of Sokoban being NP-complete in a Cambridge University student publication called Eureka [0], edition 54.
So, quite a lot more complex than one might think.
[0] https://archim.org.uk/publications/
In fact it's even PSPACE-complete, which is (probably) much, much harder!
In fact it's even PSPACE-complete, which is (probably) much, much harder!