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.


Comments (6)


You're crazy.

June 10, 2007, 4:19 p.m. #

oah, that's weird. I mean - wtf ?

June 10, 2007, 11:17 p.m. #

I tried to run your example under windows (ghostview 4.7, ghostscript 8.57) but it chokes. The error is

<code>gsapi_run_string_continue returns -101</code>

(I spare you all the dump). Any idea?
ciao, .mau.

June 11, 2007, 6:21 p.m. #

Hi .mai., Sorry to hear you're having problems. I'm not really in the position to give support for MS-Windows, but I've added a PDF link to the post. Hopefully you'll have better luck with that. Take care, lamby.

June 11, 2007, 6:42 p.m. #

the PDF version works like a charm - it's just too fast, I'll have to search for a slower pc :-)

June 11, 2007, 6:59 p.m. #

**Wenn Drucker zu Rechnern werden ...**

... hat ihnen vermutlich jemand die passende Postscript-Datei gesendet. Denn Postscript als Druckbeschreibungssprache ist weit machtiger als man allgemein hin annimmt. Um die folgenden Beispiele anzuschauen benotigst du einen Postscript-Viewer. Je nac...

June 13, 2007, 10:56 p.m. #