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:

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

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:

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.

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!