Sudokus in the free newspapers are a great way to pass some time in the train/metro (when you have no book left to read). Sudoku programs can be fun too, but some of them lack interesting features (like writing down possible numbers, giving just a hint and not the entire solution)

Gentoo portage has ksudoku, with some special sudoku types (including 3D ones), and a "Give hint" button, that reveals one of the missing numbers. KDE application though...

GNUstep users, there is a new application under development, it only has classic 9-by-9 sudoku formats, but the author is rapidly adding new features. Available in the gnustep overlay (and soon in your favorite portage tree)

And now another new application (spotted on the linux game tome): Sudoku Sensei. It allows custom sudoku formats, including the Samurai variant (9 grids in one), a great hint system (that lists all "rules" that can be applied to rule out a number), tutorials, undo/redo, basic printing, ... You can find a not-so-pretty ebuild in my overlay

Now I just need to get my printer back in working order to print some nice grids (another item on my TODO list)