You would enjoy pretty much all of the games by Zachtronics, including Infinifactory. They're all puzzle-oriented though, as far as I know, rather than sandbox.

Seconding Zachtronics; TIS-100 is an amazing game.

It's hard to call TIS-100 a "game", it's more "fictional, slightly gamified IDE"

Potato, potato. :)

Hmm, it might not be "full sandbox", but they are... flexible puzzles, which can be solved in various ways with different tradeoffs or optimizations.

I think that distinguishes them from other kinds of puzzle-games where you're hunting for "The One Predefined Secret" to make your solution.