Here's a puzzle at the beginning of Hexologic.
Simple, right? Tap the only space until it has two dots in it.
Okay, let's go a little bit further. Bigger board, throw in some spaces that are locked to a given number of dots:
Nice. This feels a little bit like a Sudoku puzzle, but with a ruleset that's optimized for a phone interface. It's just a matter of looking for the spot that has only one possible value and cascading from there. Not too bad.
The board can get pretty big, but the logic of figuring out whether each space should have one, two, or three dots remains straightforward. A good time-killer.
Once you start throwing other mechanics into the game, though, it starts to feel different. The dots in the long row have to total eleven, but the sum of the dots on each side of the > symbol have to satisfy the mathematical expression. Now we're getting somewhere.
Hexologic has thrown a handful of different mechanics at me in the 67 levels I've played so far out of just short of 100 in the game. I wish there were more! The difficulty curve is extremely gentle but the back ~half of the game is enough to get you thinking.
It costs a couple dollars in mobile app stores and apparently came out last year! I stumbled across it on the App Store a couple nights ago and have been pleasantly surprised.