I always liked Portal for this reason. I mean, the game was linear, but within most of the puzzles you could experiment and find multiple solutions.
Games like Portal 2, Qube, Quantum Conundrum had this very occasionally, but generally there was one solution to each puzzle and you had to follow a pretty prescribed set of actions to nail it.
Weirdly, though not a classic, I remember Magrunner having a bit more of the portal 1 freedom to experiment. Though I might be misremembering.
The cool thing about Portal 1 was struggling to work out how to do all the puzzles, and then going back a second time and being able to do the puzzle in half the time due to some trick you’d learned. And then seeing the achievements and realizing there were a bunch of other tricks you could use to do it in 1/100th the time.
Not a ‘puzzle game’ exactly, but since my kids have been playing some of the Humongous Entertainment Adventure Games for kids, I really like that they are both randomized and non-linear… something I’ve never really seen other adventure games do.
Each game generally boils down to finding 4 things you need to reach the final area. But then the game will have 7-8 different areas, and it’ll spawn a random set of 5-6 things into some of those areas, with each area having a traditional set of adventure game interactions to achieve it.
So each game will be 50% different. Some items will be the same and the way to get them will be the same, but other items might not be there this time, or you might decide to go for a different subset of items.
I may be wrong, but I feel like there are several different ways to achieve a few of the puzzles as well.
Of course, it’s a kid’s game, so it’s relatively short and not particularly difficult, so the amount of extra work might be less feasible for grown-up adventure games, but it’s rather a refreshing change from the usual mostly linear adventure game format.