The advance doors now blink. They always spawn east or west in the starting room and I've removed the bad door. This should make the objective clear now as well as adding the opportunity to kill rooms in order to escape.
Preset puzzles would not work because the player would simply execute them by rote. I've tried this already. The challenge of getting to the final door through a random maze seems to throw up more interesting puzzles for me because I've never seen them.
Sorry, by pre-generated I didn't really mean previously designed.
Whenever generating a room, you can probe its difficulty. The breadth and depth of solutions, in a general sense, describes how difficult a room will be. Since your enemies are pure reflex agents and the player has only 4 available actions, searching the state space should be easy. Generally speaking, the breadth inversely describes how 'puzzling' the room is. You may not be able to divine an algorithm to create rooms with narrow solution sets, but you can generate and toss those that are too broad and shallow.
Players tend to want long and narrow decision paths to always have some solution, even if it is sub-optimal.
Obviously, in an adventure game, we don't WANT to screw somebody if their first move is a mistake, but we can analyse how much mistakes are punished by the increased length of that solution path. Creating an algorithm to generate maps with desired properties is a very tough problem, but creating an analyzer to toss bad gens isn't.
Just a thought.
