There''s a couple of different paradigms in puzzle games. I think one is clearly better than the other.
1. Examples like, Qix, Adventures of Lolo, Boxxle: Solve the room puzzle games. Often in these games, one mistake and you have to restart the room. 2. Or like Tetris, Tetris Attack, Dr. Mario. These game allow for much more flexibility and creativity by the player.
Of course these are different genres and don''t stand for direct comparison, but I''ll concentrate on type 2 because type 1 leads to player frustration more often.
What I find to be a key "fun" factor in these games is more easily demonstrated not in Tetris, but in Tetris Attack (Snes game, starring Yoshi) and Dr Mario. Notice in these 2 later games, you''ve got some idea of a "combo" and a "chain". Example, a) normal clear = 3 reds, b) combo clear = 3 reds and 3 yellows simultaneously, c) Chain clear = 3 reds clear and as a result then 3 yellows can clear.
I find that these chain and combo elements add a perfect learning curve to game and actually allow for near infinite skills improvement. Eventually you find that you''re limited by how fast you fingers can move the cursor, and not by you knowledge of the game system.
Another brilliant element of game design here is allowing a 2 player mode, where players have to adapt a strategy not only to their pieces, but to accomodate the moves/attacks of the other player.
I think chains, combos, and 2 player vs modes are the high points of puzzle game design thus far.