There is a theory that for a puzzle game to interesting it has to be NP-hard. Something about how otherwise your brain is too good a latching onto the "trick" and the game is boring.