Group Abstract Group Abstract

Message Boards Message Boards

Solving Sudoku puzzles with Graph Theory

enter image description here
POSTED BY: Alejandra Ortiz Duran
10 Replies
Sort By:
Hans Milton
Hans Milton
Posted 2 years 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
POSTED BY: Alejandra Ortiz Duran

Thanks a lot for noticing that flaw! I have just corrected it, and hopefully, everything it's working correctly now!
POSTED BY: Alejandra Ortiz Duran
Brad Klee
Brad Klee
Posted 2 years 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 BY: Brad Klee
Hans Milton
Hans Milton
Posted 2 years 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 BY: Hans Milton

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 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 BY: EDITORIAL BOARD
Hans Milton
Hans Milton
Posted 2 years 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

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 BY: Alejandra Ortiz Duran
Hans Milton
Hans Milton
Posted 2 years ago
POSTED BY: Hans Milton
Hongyang Cao
Hongyang Cao
Posted 1 year ago

Nice post, I'm also interested in Graph Theory methods for solving magic squares and Latin squares.
POSTED BY: Hongyang Cao
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Tag limit exceeded
Note: Only the first five people you tag will receive an email notification; the other tagged names will appear as links to their profiles.
Reply Preview
Attachments
Remove
or Discard