In Easter 2005, when Sudoku fever kicked off in a big way in England, my Dad started writing a solver implemented in PostScript which I then modified so that it could perform backtracking. I also wrote a C# solver for my phone around the same time and later sneakily won a competition with it - I am now barred from entering competitions in that paper.
Best results are achieved if you view the PostScript directly in a viewer such as gv or GSview as you actually see the process of backtracking in solving the puzzle, the recursion depth and the set of possible symbols for each square - most PDF viewers are poor at displaying the process as they seem to render inside a different thread.
(In terms of solving the puzzle, we both found that by enforcing the simplest constraints and then 'guessing' was far easier and more efficient than performing any of the complicated constraints typically employed by human solvers. I'm certain I am not the first to notice that attempting to emulate the brain's method of solving a problem is usually a short-sighted approach for a computer.)
There are few other goodies in the file: replacing the final autotest with autotestR will recurse using the right-most possible symbol - if you get the same board with both of these then the initial board has a unique solution.
Also, if you can get your hands on a true PostScript printer, printing the file will result in the puzzle being solved in the hardware itself.