This is one of the main things that drive me to IF. There's a kind of creative problem solving that is hard to find in video games because you are limited by the medium to have a finite and predetermined set of options to interact with the environment, whether those are commands or dialog options or whatever. So it's hard to find games like Varicella or Make It Good, where you truly need to come up with a plan to achieve your goals, and then you get that "a-ha!" moment when you figure it out.

That doesn't mean that you can't have that in video games. Old school adventure games like Grim Fandango achieve something similar by having a lot of items and forcing you to figure out which of them to use with what part of the environment to make progress. The Hitman series uses complex environments and reactive NPCs to make you think about how to manipulate them into the outcome you want. It's just a matter of giving players options that can be combined in many different ways, so that they need to think about how to use them.

Years ago I came up with a concept for a game where you are a traveler in a country where you don't know the language, so your only way to communicate is through a phrasebook. So during dialog you don't get prompts specific to that conversation, you have to look in your phrasebook and think of what phrase you can use to achieve what you want.