If you find Sudoku boring you just need to add more constraints. For example, try solving one by considering some ordering on the entries (say, Left-to-Right then Top-to-Bottom) and only allow yourself to fill in entries in that order... then time yourself!
Sudoku is very boring. If I wanted to spend my time solving small value NP-complete problems I might as well go out and solve TSPs over and over again.
