June 10th 2007

Sudoku solver in PostScript


Download: .PS or .PDF

There seems to have been a bit of fuss over this Sudoku solver implemented in SQL.

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.

Anyway, here is an example PostScript board (PDF version). It was labelled "Fiendish" in The Times. The board can be easily changed at the top of the PostScript file.

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.


You can subscribe to new posts via email or RSS.