# Solving Sudoku puzzles with Graph Theory

**URL:** <https://community.wolfram.com/t/solving-sudoku-puzzles-with-graph-theory/22607>\
**Category:** Staff Picks\
**Tags:** game-development, fun-and-play, discrete-mathematics, graphics-and-visualization, graphs-and-networks, computer-based-maths, staff-pick, wolfram-repositories\
**Created:** [August 4, 2023, 11:54pm UTC](https://community.wolfram.com/t/solving-sudoku-puzzles-with-graph-theory/22607 "2023-08-04T23:54:58Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![aleordu](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/aleordu/32/449_2.png) [@aleordu](https://community.wolfram.com/u/aleordu)\
**Post date:** [August 4, 2023, 11:54pm UTC](https://community.wolfram.com/t/solving-sudoku-puzzles-with-graph-theory/22607/1 "2023-08-04T23:54:58Z")

</div>

![SudokuBlog-heroimage.jpg](https://global.discourse-cdn.com/wolfram/original/2X/f/fe710629fec7b28384a520ccea1ab6171e90e745.jpeg)

[Open in Wolfram Cloud ↗](https://www.wolframcloud.com/obj/b9ea0b6a-1200-4c69-bd69-1e27edaa0a1b)

---

<div class="post-metadata">

**Author:** ![hansmilton](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/hansmilton/32/8656_2.png) [@hansmilton](https://community.wolfram.com/u/hansmilton)\
**Post date:** [August 5, 2023, 2:59pm UTC](https://community.wolfram.com/t/solving-sudoku-puzzles-with-graph-theory/22607/2 "2023-08-05T14:59:57Z")

</div>

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](https://global.discourse-cdn.com/wolfram/original/2X/d/d81ee6a4afd167158ec5a1a5713bd50b5e40bb37.png)

At end:

 ![Errors2.png](https://global.discourse-cdn.com/wolfram/original/2X/0/00e10ec501dd986da8c9674e0824d164a077ad31.png)

---

<div class="post-metadata">

**Author:** ![aleordu](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/aleordu/32/449_2.png) [@aleordu](https://community.wolfram.com/u/aleordu)\
**Post date:** [August 5, 2023, 3:27pm UTC](https://community.wolfram.com/t/solving-sudoku-puzzles-with-graph-theory/22607/3 "2023-08-05T15:27:42Z")

</div>

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 ↗](https://www.wolframcloud.com/obj/90cd8860-74c5-4a8f-890d-157707e18309)

---

<div class="post-metadata">

**Author:** ![hansmilton](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/hansmilton/32/8656_2.png) [@hansmilton](https://community.wolfram.com/u/hansmilton)\
**Post date:** [August 5, 2023, 4:46pm UTC](https://community.wolfram.com/t/solving-sudoku-puzzles-with-graph-theory/22607/4 "2023-08-05T16:46:08Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![aleordu](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/aleordu/32/449_2.png) [@aleordu](https://community.wolfram.com/u/aleordu)\
**Post date:** [August 5, 2023, 10:07pm UTC](https://community.wolfram.com/t/solving-sudoku-puzzles-with-graph-theory/22607/5 "2023-08-05T22:07:40Z")

</div>

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!

---

<div class="post-metadata">

**Author:** ![wolframcommunity](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/wolframcommunity/32/8335_2.png) [@wolframcommunity](https://community.wolfram.com/u/wolframcommunity)\
**Post date:** [August 6, 2023, 5:58am UTC](https://community.wolfram.com/t/solving-sudoku-puzzles-with-graph-theory/22607/6 "2023-08-06T05:58:19Z")

</div>

![news-congrads-kkluyshnik-02-04-19.jpg](https://global.discourse-cdn.com/wolfram/original/3X/6/a/6a310c2d0904616faf4e6e148260c9f29ab9f4eb.jpeg) – you have earned _ **Featured Contributor Badge** _ ![2015-11-02_10-07-11.png](https://global.discourse-cdn.com/wolfram/original/3X/5/0/50e59c9ead62f729e7130d3ea1482555a75602b6.png)  
Your exceptional post has been selected for our editorial column _ **Staff Picks** _ [http://wolfr.am/StaffPicks](http://wolfr.am/StaffPicks) and [Your Profile](http://community.wolfram.com/web/aleordu) is now distinguished by a _ **Featured Contributor Badge** _ and is displayed on the [Featured Contributor Board](https://community.wolfram.com/people). Thank you!

---

<div class="post-metadata">

**Author:** ![hansmilton](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/hansmilton/32/8656_2.png) [@hansmilton](https://community.wolfram.com/u/hansmilton)\
**Post date:** [August 6, 2023, 8:20am UTC](https://community.wolfram.com/t/solving-sudoku-puzzles-with-graph-theory/22607/7 "2023-08-06T08:20:11Z")

</div>

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!

---

<div class="post-metadata">

**Author:** ![hansmilton](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/hansmilton/32/8656_2.png) [@hansmilton](https://community.wolfram.com/u/hansmilton)\
**Post date:** [August 6, 2023, 12:27pm UTC](https://community.wolfram.com/t/solving-sudoku-puzzles-with-graph-theory/22607/8 "2023-08-06T12:27:12Z")

</div>

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}
};

```

---

<div class="post-metadata">

**Author:** ![bradklee](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/bradklee/32/16606_2.png) [@bradklee](https://community.wolfram.com/u/bradklee)\
**Post date:** [August 6, 2023, 5:50pm UTC](https://community.wolfram.com/t/solving-sudoku-puzzles-with-graph-theory/22607/9 "2023-08-06T17:50:29Z")

</div>

This is a nice follow-up to [your previous post](https://wolfram.discourse.group/t/22575/1) , 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](https://resources.wolframcloud.com/FunctionRepository/resources/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 ↗](https://www.wolframcloud.com/obj/c81558de-3fd0-4bb2-844e-2c88942d0c4c)

---

<div class="post-metadata">

**Author:** ![aleordu](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/aleordu/32/449_2.png) [@aleordu](https://community.wolfram.com/u/aleordu)\
**Post date:** [August 7, 2023, 12:13am UTC](https://community.wolfram.com/t/solving-sudoku-puzzles-with-graph-theory/22607/10 "2023-08-07T00:13:56Z")

</div>

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

[Open in Wolfram Cloud ↗](https://www.wolframcloud.com/obj/db8c5f15-8c59-4d2d-8d8c-8976e8198ebc)

---

<div class="post-metadata">

**Author:** ![chyanog](https://avatars.discourse-cdn.com/v4/letter/c/90ced4/32.png) [@chyanog](https://community.wolfram.com/u/chyanog)\
**Post date:** [June 11, 2024, 3:35pm UTC](https://community.wolfram.com/t/solving-sudoku-puzzles-with-graph-theory/22607/11 "2024-06-11T15:35:11Z")

</div>

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