Pocket Sudoku is the definite sudoku application for Pocket PC (Windows Mobile). It can currently generate sudoku puzzles using five different difficuties, solve any valid puzzle, show pencil marks, hint you when you’ve got stuck, and much more…

http://sourceforge.net/projects/pocketsudoku/