The idea is this: In the puzzle game, include some random events. This could be handled like in an RPG (critical hits and misses, for example) or in a board game (roll the dice to see how far you can move on your turn) or in any other manner.

But here's the catch: in any given stage, the Random Number Generator always generates the same sequence of numbers. Perhaps there is even a way to view the sequence in some way. (For example, imagine a card game where you are allowed to look at, but not change, the cards that can be drawn.) This means that part of the strategy becomes manipulating the RNG so that you get good results when you really need them.

There are a couple interactions with other features that are worth noting:
1. If you save in the middle of the level, the RNG state is saved, so reloading won't let you get a different result.
2. If there is an Undo feature, and you undo a move that has a random result, the RNG state will be rolled back so you don't get a different result if you try again. (Yes, this can be used to peek at what the next random number will be. This is intentional.)

Edit: Added a missing word. Oops!

You meant "so you don't get a different result if you try again"? Otherwise, I'm not sure I understand point 2.

Fixed. Yes, I sometimes make mistakes, like everyone else.

Are you making a game?
The idea is actually quite clever. Added to your last question I saw I think you might actually have the basics of a decent game, mechanic wise.

Answer to you question: Yes a puzzle / RPG game with a say battle system like that would be interesting. Move "x" and do "e" knowing the next computer move is "y" doing "f" means you have to actually plan your steps knowing in advance where the opponent would be looking to go.
Done right it would make a challenging, yet fair and skill based game.
Balance would be the kicker.

You can actually do something like this in the later DROD titles. The engine is now mature enough that it is easy to create an invisible character to serve as a RNG, updating a global 'random number' variable. Each room using the RNG would need its own copy of that character. Scripts that needed a random number would just look at the global variable that the RNG character updates.

Because DROD is completely deterministic, your two criteria regarding saving and undo would automatically work as you want. The saved game state for a room is just a playback of the moves you make to solve it.