The Strongest Sokoban Solver

(healeycodes.com)

45 points | by ibobev 3 days ago

9 comments

  • vintermann 1 hour ago
    Decades ago I built a Sokoban solver, then a more generic puzzle solver which could handle a wide range of similar games (such as Atomix). It's fun to see someone else finding all of these heuristics. Excluding dead squares and searching backwards to meet in the middle I definitively implemented, and I thought of many of these others too (though whether I got around to implementing them is another question!). This post is praiseworthy for showing how intuitive these tricks are once you know them.
  • ngruhn 24 minutes ago
    I did not know about Sokoban, but sounds like the rock pushing puzzle in Pokemon red/blue/yellow was inspired by it. There was this "Jev plays pokémon" livestream at some point and the model was stuck on this puzzle for hours
    • quibono 17 minutes ago
      There are a few games with similar mechanics, "Baba is you" comes to mind as a very popular one. These can get very complicated very quickly.
  • quibono 1 hour ago
    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/

    • mjdv 46 minutes ago
      In fact it's even PSPACE-complete, which is (probably) much, much harder!
      • quibono 19 minutes ago
        I've always struggled to understand what the difference is. Is PSPACE-completeness "worse" in a practical sense?

        I'm assuming P != NP (and NP != PSPACE).

  • xpct 1 hour ago
    > Just to be ultra clear here, as you may be skim reading...

    This caught me completely off-guard, and I was indeed skim reading. Nonetheless, very well written article!

  • ZiiS 42 minutes ago
    One of the clearest write-ups showing how coding agents can be applied to good engineering and help with comprehension.
  • asibahi 2 hours ago
    This is an interesting read ive been playing Jon Blow's latest game.

    Maybe i will apply some of these heuristics myself when solving puzzles.

  • skrebbel 1 hour ago
    Wow this is an excellent writeup! Hats off.
  • forrestthewoods 18 minutes ago
    Very cool. Thanks for sharing.
  • alphayc 34 minutes ago
    [flagged]