9
$\begingroup$

I am looking for some puzzles like Sokoban or 15-puzzle but more difficult to solve and satisfy the following requirements:

  1. The number of possible moves at each step should be limited, let's say < 10.

  2. Easy to generate a lot of levels (unique instances of puzzle). Let's say > 10**8.

  3. One player.

  4. Ideally has a terminate state at each level (game over).

  5. Has a lightweight implementation (or can be implemented easily).

  6. Difficult to be solved with tree search.

For example Sokoban satisfies all items except 2. Any suggestions would be greatly appreciated. Thanks!

$\endgroup$
  • 1
    $\begingroup$ Have you looked at Simon Tatham's puzzles (available as an app and open source): chiark.greenend.org.uk/~sgtatham/puzzles $\endgroup$ – Dr Xorile Nov 17 '18 at 20:54
  • $\begingroup$ @DrXorile Thank you for reference, but most of them (except 15 puzzle) have a lot of movements at each step! I am interested in puzzles where the movements are just going right, left, up, down and so on. $\endgroup$ – Math-fort Nov 17 '18 at 21:14
6
$\begingroup$

Many PuzzleScript games satisfy your requirements, although

  1. I'm not sure how interesting generated levels would be, and
  2. Some games include one action button in addition to the directional inputs.

In a similar vein, you may want to check out other sokoban-likes including A Good Snowman Is Hard to Build, Snakebird, Pipe Push Paradise, Stephen's Sausage Roll, and Fidel Dungeon Rescue.

See the PuzzleScript gallery for lots of other examples.

edit: HyperRogue may also be of interest to you - unlike the other games it is procedurally generated, usually has 7/8 inputs per turn (6/7 directions + wait), and is extremely difficult to solve with tree search given the hyperbolic geometry.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.