ksudoku is a full-featured Sudoku puzzle generator and solver for KDE. With it,
you can generate and play 3D and 2D puzzles of different sizes and levels, 
and the GUI is good for playing, saving, printing, solving and dubbing 
puzzles.  The main algorithm is fast and extendable to any general graph 
coloring problem. 

This requires OpenGL.