Solving Sudoku puzzles with Graph Theory

Staff Picks
, , , , , , ,
1

SudokuBlog-heroimage.jpg
SudokuBlog-heroimage.jpg1010Ɨ719 221 KB

Open in Wolfram Cloud ā†—
10 Likes
2

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:

Errors1.png
Errors1.png721Ɨ219 9.33 KB

At end:

Errors2.png
Errors2.png712Ɨ111 5.2 KB

1 Like
3

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.

Open in Wolfram Cloud ā†—
1 Like
4

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.

1 Like
5

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!

2 Likes
6

news-congrads-kkluyshnik-02-04-19.jpg ā€“ you have earned Featured Contributor Badge 2015-11-02_10-07-11.png
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!

1 Like
7

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!

2 Likes
8

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}
};
1 Like
9

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:

Open in Wolfram Cloud ā†—
1 Like
10

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

Open in Wolfram Cloud ā†—
1 Like
11

Nice post, Iā€™m also interested in Graph Theory methods for solving magic squares and Latin squares.