Hit some major snags with my idea today.
The basic aim for this game was to generate puzzle rooms that were quite difficult yet guaranteed to be solvable.
The game play would involve a race against the clock to solve them as well as possible.
To make it a bit more interesting, I wanted to give the player some tactical choices in each room. Do you take your time, trying to get the solution completely worked out? Do you try and rush through it, only partially solving it? Maybe you focus on objectives that give bonus time to draw out the game or you could focus on the objectives that increase score for a faster but possibly higher scoring game. I also had some ideas for character progression within each game by essentially modifying the rules of how you can interact with the world.
The current approach I've been trying is to generate somewhat random/empty rooms where the player is standing by the exit and then do a backward search of possible actions, filling the room with things the player will have to deal with. Since all the monsters/interactions in the game are deterministic, I'm able to run things backward "fairly easily".
The problem I'm having is that the number of possible interactions is so vast, any kind of exhaustive search is impossible. To generate a puzzle requiring enough actions to be challenging, I need some kind of heuristic that allows me to search in the direction of "interesting puzzle to solve..."
The best rooms I've been able to generate so far are ones without any monsters - just straight up sokoban puzzles. They're not too bad, just not quite what I had in mind. I'm basically handing a scrambled rubix cube to the player in each room.
I think I need to take a break and rethink my approach.
Does anyone one know of any games that are able to procedurally generate challenging/interesting puzzles that are guaranteed to be solvable?