Simon Tatham's Portable Puzzle Collection is free and completely open source. It includes 17 different puzzle games so far, one of which is called SOLO -- which is the Sudoku solver. Runs on Windows, Mac, Unix, Palm OS, etc. He seems to be adding new apps quite frequently as well as continually updating the existing ones.
SOLO will automatically solve 9x9, 16x16, 25x25, etc. There are no bells and whistles -- if you use it to solve a puzzle yourself, you can enter pencil-marks manually. There are no other solving aids.