7
|
5138 Views
|
9 Replies
|
18 Total Likes
View groups...
Share
GROUPS:

# Solving Sudoku puzzles with Graph Theory

Posted 9 months ago
9 Replies
Sort By:
Posted 9 months ago
 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 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: hintsA={ {0,0,0,0,0,4,1,8,2},{0,0,0,0,0,0,0,0,5},{8,0,0,0,0,9,0,0,0}, {2,0,4,1,0,0,0,0,0},{0,0,0,0,0,0,7,0,4},{0,0,0,0,0,0,3,2,0}, {0,0,0,7,0,8,4,0,0},{7,0,3,4,0,0,0,1,0},{5,0,0,0,2,1,0,0,9} }; hintsB={ {9,8,0,0,0,0,0,0,3},{3,0,0,0,0,0,0,0,0},{0,0,0,0,7,0,0,0,0}, {0,0,0,0,0,0,0,2,8},{6,0,2,8,0,0,7,9,0},{0,5,0,0,0,0,0,0,0}, {0,7,8,3,0,5,2,0,0},{0,0,4,0,0,0,0,6,5},{0,0,0,0,0,4,0,8,0} }; 
Posted 9 months ago
 Thanks a lot for noticing that flaw! I have just corrected it, and hopefully, everything it's working correctly now!
Posted 9 months ago
 -- you have earned Featured Contributor Badge Your exceptional post has been selected for our editorial column Staff Picks http://wolfr.am/StaffPicks and Your Profile is now distinguished by a Featured Contributor Badge and is displayed on the Featured Contributor Board. Thank you!
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:At end:
Posted 9 months ago
 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 9 months ago
 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!
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.