Sudoku solver that can create a graph of the solution _process_

[sschwarzer]

Hello Thomas!

In April I attended your optimization course and that inspired me to write a Sudoku solver in Racket. :-) Different from other solvers, this one can create dot files which you can render with GraphViz to get a graph of the solution process! Here is an example for the Sudoku puzzle from Wikipedia. The README explains how to interpret the diagram.

You can see which digits enabled the algorithm to recurse further. Conversely, you can see where it didn't find any more promising branches and continued with others. As an alternative to the dot file, you can generate a text file that shows the solution process. This file uses indentation to show the recursion level.

Links:

• Source code. Here's the module with the actual solver.
• Example graph for the Wikipedia puzzle
• Ready-to-run binaries for different platforms. (You can also install the solver as a Racket package, explained in the README.)

By the way, I find it also interesting to try the program on "anormal" inputs, for example an empty puzzle without any digits to start with. This makes it even clearer how the algorithm works.

The software is MIT-licensed. Feel free to use it or the generated diagrams in your course. :-)

Of course, everyone else is also invited to use the program. Actually, that's why I entered a ticket here instead of writing an email. :-)