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!

  • $\begingroup$ If you don't mind that some instances of the problem would not have a valid solution, then Sokoben also satisfies item 2. To generate an instance sample a number of boxes and targets, then randomly place: the player, empty spaces, walls, boxes and targets. $\endgroup$
    – Cohensius
    Commented Nov 21, 2018 at 13:27
  • $\begingroup$ You should mention in your question that this is a cross-post of puzzling.stackexchange.com/questions/75387/puzzles-like-sokoban. $\endgroup$
    – user76284
    Commented Apr 28 at 3:59


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.