3 ms·

For the interested, proof that Sokoban is NP-hard. https://www.archim.org.uk/eureka/archive/Eureka-54.pdf#page=28 https://www.archim.org.uk/eureka/archive/Eure

For the interested, proof that Sokoban is NP-hard. https://www.archim.org.uk/eureka/archive/Eureka-54.pdf#page=28 https://www.archim.org.uk/eureka/archive/Eureka-54.pdf#page=...

saghm 2y ago
Interesting... Back in college when I was applying to places (I can't remember whether it was an internship or a full-time job), one place gave me an online challenge that from what I remember was basically identical to this game. They had provided a minimal API in JavaScript for interacting with the state, and I remember being embarrassed that the only solution I could come up with was brute force. I had forgotten about this until I saw the animation on the Wikipedia page just before reading this comment, but now I'm amused that my solution might have been optimal after all!
RodgerTheGreat 2y ago
It's a little worse than that (probably); it's also PSPACE-complete: https://www.semanticscholar.org/paper/Sokoban-is-PSPACE-complete-Culberson/7a73f74c2943e5aafef364735302a36ee2f17b26 https://www.semanticscholar.org/paper/Sokoban-is-PSPACE-comp...