I am looking for some puzzles like Sokoban or 15-puzzle but more difficult to solve and satisfy the following requirements:
The number of possible moves at each step should be limited, let's say < 10.
Easy to generate a lot of levels (unique instances of puzzle). Let's say > 10**8.
Ideally has a terminate state at each level (game over).
Has a lightweight implementation (or can be implemented easily).
Difficult to be solved with tree search.
For example Sokoban satisfies all items except 2. Any suggestions would be greatly appreciated. Thanks!