White Jigsaw, by Taro Ito of gamedesign.jp, solves a lot of those problems. There's no picture, the pieces can't be rotated or flipped over, and it starts off small: a 4x3 puzzle of 12 totally white pieces. That's right, it's not called White Jigsaw for nothing. The game is not hard by any means, but it's not really intended to be. It's intended to be evil, but in a nice way.
You begin each level the way your grandma taught you: the edges first, working your way in. By the third level you're taking guesses at some of the middle pieces, and you're probably right most of the time. Soon you're staring at a 11x8 88-piece monster and wondering how you got there, and why can't you just stop? I got hooked on the pattern matching, scanning the available pieces, searching for that one pattern I'd locked into my head, and feeling that rush as the last handful of pieces click into place.
The thing about jigsaw puzzles is that the finish is what you're playing for, and this is no exception. The designer has taken away the picture, but by feeding the puzzles to you in ever-increasing sizes you get drawn in little by little to his masochistic master plan. I couldn't help myself: every time I finished a level I felt flush with joy that I'd earned the right to move on to the next level, only to be crestfallen at what I'd gotten myself into.
Be careful, this game is utterly addictive.