11
$\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!

Improve this question
$\endgroup$
2
  • 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
    Commented Nov 17, 2018 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
    Commented Nov 17, 2018 at 21:14

1 Answer 1

Reset to default
8
$\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.

Improve this answer
$\endgroup$

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