Let's define 'non-linear' as having a variety of possible routes to take from point A to point B. With that in mind, we know about non-linear narrative design (The Witcher 2) and non-linear level design (Dishonored). But what about non-linear puzzle design?
I'd hold up Spacechem as the pinnacle of a non-linear puzzle game, because not only does it have a mindbogglingly high number of different conceptual solutions to a particular puzzle, every concept can also have many structural variations that affect its speed and efficiency, with often a trade-off between the two. I think the game is in a league all of its own, but it can't be the only game that allows its players to be creative with their solutions.
Most puzzle games I've played have absolutely no non-linearity about them. That includes puzzle platformers: Braid in particular got on my nerves because the 'game guide' says you just have to keep at it trying to solve the puzzles, and you'll feel smart when you eventually get it. I don't, because all I'm doing is looking at a problem and trying to figure out the one particular solution that the designer wants me to discover. It may require a lot of thinking, but in the end it's simply a way of fitting round pegs into round holes.
So what other puzzle games are there that allow you creativity in your solutions? Is there a game that is to Spacechem what Dishonored is to Deus Ex? Or the other way around?