Yet Another Dancing Links Solver/Generator (with graphs!)

jmelloy

I've written a generic dancing links solver in Python, and have an example solving of both 8 queens and Sudoku. The sudoku portion also generates a Sudoku, but takes longer than it could (about 3 seconds).

I caught a wild hair this weekend, and wrote a script to demonstrate how a dancing links solver branches and fails.

Here's a link to my graph (the spam-prevention on this website is frighteningly efficacious):

cavernum dot net slash dlsudoku

The nodes are clickable and will show the board at any state.

There's also a link to my svn repository with the (horrifically un-documented) source. It will work with any sudoku, and uses graphviz to create the graphs.

As you look at the graph, you can see the choices it makes, and the squares that have multiple options. The (3,4) 5 notation means "Choose 5 at position (3,4)".

For the not faint of heart, here's the graph for the easter monster:
cavernum dot net slash dlsudoku slash easter dot html

Interestingly enough, when dancing links is solving the easter monster, it makes two choices as its first two moves. After exhausting possibilities for those two branches, it doesn't branch at all after that.

If you need a better explanation of what you're seeing, let me know.

Adak · Posted: Tue Apr 22, 2008 8:14 pm Post subject:

Congratulations on your program, JM. I haven't had a chance to visit your site yet, but certainly will soon.