I'm thinking of games with non-linear puzzle solving, multiple puzzle solutions, and hidden actions that can be taken for additional points. I can think of a few other adventure games with non-linearity, but very few that also had multiple puzzle solutions.
Huh, I think the Quest for Glory games fall closest to the mark -- most puzzles had three solutions, one for each class specialist.
Quest for Glory seconded.
Malcolm's Revenge has multiple paths. Blade Runner too.
Last Express is the most interesting one in my eyes - not only it has different solutions, but also real-time situations: if you do nothing time still passes and the game continues, but you may have lost valuable info or failed to complete a task.
I think (but I'm not sure) that Hand of Fate had some different ways you could solve puzzles as well... so the Kyrandia series seem to fit in general (the first one was linear, but had items needed for puzzles in random spots and trial-and-error puzzles are common).
Actually, I Have No Mouth And I Must Scream has you solving puzzles in several ways as well... in which way you solve certain puzzles dictates on how "pure of heart" the characters ends up.
Yeah, the Kyrandia series is always one I've been meaning to look at, but I dislike the aesthetic so strongly that I just can't bring myself to play them.
I want to love Kyrandia 1 and 2 much more than I do; they have a charm and they are full of beauty and whimsy. But they have some pretty fundamental cruel gameplay problems.
(Really what I want to do is make a submission for the original Kyrandia game for the Worldgroup BBS system, http://www.youtube.com/watch?v=RSBBy2QE-lw )
I actually managed to see past that, but yeah... they are pretty cruel in a Sierra kind of way sometimes.
The combination of the randomness with one-way passages and what could potentially be extremely long sessions of "walking dead" play (where winning is unattainable, but play continues) make me recommend it only with reservations. I remember Kyrandia 2 also had endless variations on a pattern-matching puzzle I never really wrapped my head around, and I nearly shat myself when I saw the Tower of Hanoi at the end. (I recall some similar issues with Fate of Atlantis. This isn't the kind of game I was hoping to play, but I need to get around it in order to get back to the good stuff!)
That's why god invented the Internet. If you play a game like that for the first time now, you don't have to worry about getting stuck anymore. ;)
Unlike me, who played all of them when they first came out. If you did get stuck you had to sit and hope that the next issue of the gaming magazines would have hints to help you along. That was quite a pain. :/
That Hanoi puzzle is an absolute, complete, utter nightmare.
Generally, I find Kyrandia games disappointing, what with their weak and confusing puzzles, and their awful "one cursor for everything" interaction.
Malcolm's Revenge is by far my favorite of the bunch, is pretty funny too.