How might I speed up this sudoku solver?

Projects Personal Projects
1

Repository: Sudoku_Solver/sudoku.py at main · Jelly-Pudding/Sudoku_Solver · GitHub

I fed it an “evil” sudoku and it took like 16 seconds to get the solution. It really needs to be faster as I want to try it out on bigger sudoku boards.

If you look through the code, is there anything that could be done differently to make the script run faster? Also are there any other methods to make it faster - e.g. something that might support the backtracking function/prune the tree even more.

Thanks in advance

1 Like
2

While this is miles over my head, I am a pencil Sudoku throner so have a mindset, added to being able to read Python, I enjoyed the read of this code. Very nicely done.

I did give some thought when reading each segment of code, looking for opportunities to refactor, but saw none. That’s due to my own blindness perhaps, and/or naivete, more than anything. There is a significant amount of iteration; that might warrant further research/study.

Sixteen seconds, you say? Beats the 20 minutes or more I would have spent on it.

Disclaimer: My only approach to Sudoku is that a linear solution must be available. The only exception to nailing this down is finding the key when other visuals are coming up empty. A key means two elements are involved, or even three. Find the key, and move on. Soon enough the puzzle solves itself.

A solution finder needs to have this skill. Reach a point of impasse and locate the key (or better still, locate the key first to avoid the impasse). But that is all human thinking. One would never presume to criticize working solution code, especially given that I might never reach the level where I could write it. That is yet to be determined.

If we want to give our class added smarts we can teach it about excluded pairs (one of the possible keys), chained triples (another possible key) or elimination (can’t be an %x, or …)

It’s obvious the logic in your recursion is transcending even that human logic, so far be it for me to even think I’m adding insight to this reply. All I really know is I like Sudoku on the John. It’s my relaxed morning sojourn.

1 Like
3

Getting a block into a list, now we only really need to compare it to a set, assuming the value points are 1..9. A set with length less than a row, column, or block would fail.

This may be a way to limit iteration. You’ll sort it out quicker than me, so have at 'er.

Using my old Othello (Go, Minesweeper, &c.) thinking (writing in BASIC), Blocks 1 through 3 are row 1, columns 1, 4 and 7, and rows 4 and 7 match the same columns. That is the center element of each. All eight branches lead from there, for each block. I’m not convinced slicing is the way to go, but sure you will convince me.

(x - 1, y - 1), (x, y - 1), (x + 1, y - 1),
  (x - 1, y),     (x, y),     (x + 1, y),
(x - 1, y + 1), (x, y + 1), (x + 1, y + 1)

(x, y) is only ever, ((1, 4, 7), (1, 4, 7)).

sure you will convince me

Already done like dinner. I convinced myself. The slice points are right there, once all the syntax is in place.

1 Like
4

I did not know that for loops can really slow scripts down in python - and thanks for the suggestion and kindness :D.

I’m going to work on making it faster soon, but for now (weirdly enough) it’s good that it’s slow because I’m working on showing the backtracking process happening on a sudoku board (using pygame). It currently looks pretty neat lol with loads of numbers constantly changing to other values or resetting back to 0. But it would be less neat if it solved the board in the blink of an eye lol.

1 Like
5

You’re welcome.

Aside

Most of the published Sudoku puzzles we encounter are well crafted and designed by a human, not a machine.That is so far over my head one would never presume to know even a smidgen of the parameters those designers use. It is they who write in the above mentioned ‘keys’, by my way of thinking. A machine would need to be given this consideration as one of the criteria.

That, to me, would be the next level once you have perfected the solver. Expect it to be a challenge.

Another consideration is board layout. While I won’t turn any Sudoku aside, I love to see when they have the symmetry the inventor intended. Can’t say it makes any difference at the various difficulty levels. Just a personal favorite.

Back on topic, it would be interesting to see how the set comparison works out in your three linear arrays. The time difference is either there, or it’s not. Won’t know until you try.