Su Doku
I loves me some Su Doku. I do the one in the Calgary Herald every day at lunch and if there's time (and the Herald one was easy) I'll print off the one from the London Times and do it as well.
Assuming your Su Doku pusher is a reputable one, each puzzle only has one answer and can be solved by logic -- no guessing required.
Perfect for me! Yay!