Message Boards Message Boards

Solving Sudoku puzzles with Graph Theory

9 Replies

This is a nice follow-up to your previous post, especially because DepthFirstSearch doesn't lead to a timely solution. However, it's well-known that Sudoku is a good use case for Donald Knuth's DancingLinksX algorithm, so it's also possible to compare times with FindExactCover. Using the MRV-heuristic, we can achieve a $2\times$ speed-up solving the puzzle as an exact cover problem. There is a debug-Reap with the WFR, which says that the solution here takes only $68$ steps to fill in the $55$ missing values, but I would have to read the source code again to see exactly what counts as a "step". If another semi-random heuristic is used, the step count explodes to more than $15K$.

Regarding plausible submissions for the games book, this could be even better than the queen's problem, but again, to fit with the multi-computational theme, we need more information about what's going on under-the-hood. In concrete terms, that means printing (ideally) a graph of the search tree explaining how a particular path is found through the space of all possibilities.

Code is here:

POSTED BY: Brad Klee
Posted 9 months ago

Well, it turns out that this graph method is not yet without flaws. If a digit 1 to 9 is missing from the hints it will also be missing from the solution, with errors thrown. Try these hint matrices:


POSTED BY: Hans Milton

Thanks a lot for noticing that flaw! I have just corrected it, and hopefully, everything it's working correctly now!

enter image description here -- you have earned Featured Contributor Badge enter image description here Your exceptional post has been selected for our editorial column Staff Picks and Your Profile is now distinguished by a Featured Contributor Badge and is displayed on the Featured Contributor Board. Thank you!

POSTED BY: Moderation Team
Posted 9 months ago

Interesting. But there seems to be a problem. I downloaded your notebook and evaluated graphHints, sudokuSolve and puzzle. But running sudokuSolve[puzzle] does not give a solution. Many error messages. At the beginning:

enter image description here

At end:

enter image description here

POSTED BY: Hans Milton

You can try evaluating the puzzle again. I tried it in a new notebook, and it seems to be working. Please let me know if you still encounter any errors.

Posted 9 months ago

Sorry, still same problem. Earlier, before my first post, I tried on two different PC´s and also in Wolfram Cloud. Same negative result on all three platforms.

For your info my PC´s has MMA v13.3. One is on Windows 11, the other on Windows 10.

POSTED BY: Hans Milton

Yes, you are right! I encountered the same error in the cloud. Please try running it again. I believe the error occurred due to a pair of parentheses that got deleted during the conversion of the blog. I've reorganized the code to use fewer parentheses and edit it in the blog and the comment. Thank you so much for catching that! Please let me know if it works now or if you encounter any other issues!

Posted 9 months ago

It works just fine now. I have tried it out on some of my previously solved Sudokus. Your method is quite fast, also in (traditionally) difficult cases!

POSTED BY: Hans Milton
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
or Discard

Group Abstract Group Abstract