Brain Training games are quite interestings.
'Dr. Kawashima's Brain Training: How Old Is Your Brain?' has a large selection of sudoku puzzles, which are quite fun, and being on the DS you can quite easily put in little notes in each square to work out what goes where, which is something a bit messier to do with sudoku on paper.
Also, it teaches you tricks for sudoku too.