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 Nov 21 '18 at 13:27

Your Answer

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

Browse other questions tagged or ask your own question.