Leptonica, the image processing and analysis C library, has a Sudoku module. It's not clear to me why, but nonetheless I wrote bindings to it.
It can solve a Sudoku puzzle, and generate new ones.