ksudoku is a fully-featured Sudoku puzzle generator and solver for KDE. With it you can generate and play 3D and 2D puzzles of different sizes and levels. The main algorithm is fast and extendable to any general graph coloring problem.
About the easiest sudoku to play when using the mouse. Just a pity it is not available as a Gnome port, because the KDE libraries needed makes it terribly slow to load in a Gnome environment.