Sudoku solvers: backtracking or logic?

While writing a sudoku solver - which would be more efficient, backtracking or logic?
Let's run experiment and find out.
Source code: drive.google.com/drive/folder...
Sudoku Universe on Steam: store.steampowered.com/app/73...
------------------------------
Dreamland by Jonas Schmidt / jonasschmidtof. .
Creative Commons - Attribution 3.0 Unported - CC BY 3.0
Free Download / Stream: bit.ly/-dreamland
Music promoted by Audio Library • Dreamland - Jonas Schm...
------------------------------

[@voxelfusion9894]

This is fascinating. I tried my hand at implementing a simple sudoku solver, and apart from simple elimination, didn't know these other strategies existed. I'll have to try implement them myself now.

[@GamesComputersPlay]

Same here - I might have intuitively used some of the very simple ones, but only when I started writing the solver I learned about how much more complex they can be. And it goes even deeper, I implemented easy, medium and couple of hard strategies. On sudoku sites there are more hard, very hard and diabolic strategies to learn about.

[@diogocaetanogarcia]

The more "esoteric" methods are important for humans that can't afford (or won't accept) backtracking.

[@rewrose2838]

😂 well, 3d medusa and x cycles seem quite ridiculous too (then again, I don't do sudokus)

[@diogocaetanogarcia]

@@rewrose2838 Yeah, they are quite hard to spot. When I find myself in a jam, I use backtracking, looking for places with 2 possible options that may highly influence the rest of the board.

[@uykusuzdev]

I love your videos, keep them providing.

[@nordern1]

How about, instead of mixing the backtracker with smarter solutions, you try to make the backtracker itself smarter. It can stop once it has found a single solution, so we could speed it up by picking a smarter path for it to traverse that might result in less backtracking or at least prefer paths that fail sooner. Currently, I think your backtracker just moves to the next free cell, left to right, top to bottom. Idea 1: Solve the cells with least remaining possible values first. This gives you "simple elimination" for free, and that on every step of the brute-forcing, leading to a possibly far quicker detection of impossible braches. Idea 2: Sort of an extension of Idea 2. Instead of searching the entire board for the next best move every time, search the other cells in the same houses first. Since you have just placed a number in the same house, chances are you have reduced their number of possible remaining moves. This incorporates the naked pairs, triples, quads into your bruteforcer. Idea 3: Maybe only proceed with a cell in your house if their remaining possible numbers are lower than the ones the current cell had. No need to get bogged down in the complex fields in your neighborhood if there are still simpler fields on the board. Idea 4: To speed up all these searches, build a proper graph with every cell and their neighbors beforehand, instead of the array you currently seem to have

[@GamesComputersPlay]

I like this ideas, I think it bois down to: down just go left to right, but from more populated houses to less populated. It sound like a good idea, but I am not 100% certain it is going to work. Aren't we just switching multipliers - thus having the same product?

[@nordern1]

@@GamesComputersPlay @Games Computers Play That would be another idea of traversal that might be worthwhile. But I don't think house population equals number of possibilities. A cell might only have one remaining possible number even if the all of its houses combined only have 8 populated fields. Not sure how that statistically averages out, though. I'm not sure on the math, I've never been great at that part, but I'm pretty sure it's not that simple, because every number placed reduces the possibilities for the other field. After all, by that logic, simple elimination would just move all the "1x" multipliers to the beginning, right? But it quartered the time your brute force algorithm needed I think if we pick the fields with the fewest possibilities first, we increase the speed with which we can eliminate large sections of the tree. I could try to implement that into your code. I need to brush up on my Python anyways :P I'll let you know if I find anything significant

[@nordern1]

@@GamesComputersPlay My last comment disappeared for some reason. Long story short, it worked better than I ever imaged, and I'm pretty sure it now beats out the actual solvers in most cases. Do you want to see the source?

[@andersama2215]

@@nordern1 ​ If you wanted to travel all possible branches from a starting board (getting all potential solutions if multiple are allowed) you'd be right, it'd take the same time. These are all optimizations that bank on reducing the number of boards you'll need to travel before you can safely assume the board is impossible. In turn this means the maximum number of branches you need to travel per board is significantly reduced (and in practice means you'll have reduced the number of branches you need to travel to find a solution), and it sounds like Norden's seen how big a difference it makes. If you consider that one swapped cell could reduce 9 choices to 2 and you've got x so many cells, that's how it stacks up quickly. What it's really doing is removing all the redundant work of backtracking boards that couldn't be right anyway. I can't remember where but if you want to see absurd sudoku solving results there's a simd based logic solver that is pure bit wizardry but I can't remember the link, it's definitely on github. That's I think the only thing I found that was faster than this type of method. (Edit: I remembered I left an issue for the repo on github, search tdoku) For context I've written several similar solvers. It's actually nice to see that adding different additional logical steps reduced time for you. When I was doing this type of thing I actually found that some algorithms cost more time than just the simple brute force methods, which was a bit disappointing, I was more after results like yours.

[@nordern1]

​@@andersama2215 Your comment confused me because you responded to me, not to them :P But yes. I've released an implementation myself. (edave64/ku on github) It probably helps that it's written in rust, not in python, but the method of traversal seems to vastly outweigh the choice of language My solver currently uses exactly the first strategy I described, always solve the cells with the least possibilities left first, and it's really fast. Worst case I've seen took 1 second. Average is in the tens of milliseconds, all with pure backtracking. If I replace "let next = board.most_certain();" in the algorithm with "let next = board.first_unsolved();" it suddenly becomes terribly slow again. As an example: "9..8...........5............2..1...3.1.....6....4...7.7.86.........3.1..4.....2.." With "most_certain" it takes roughly 100ms (According to the linux time command). With "first_unsolved", 36s. Even in debug mode "most_certain" finishes instantly, while I had to abort "first_unsolved".

[@jofx4051]

Applying some strategies reducing time so much to solve for the solvers, wew

[@ninjaburrito24]

How do some of these videos have such low view count!? Great content

[@IWkris]

Wonder if your testing puzzles just arent hard enough to use a medusa

[@GamesComputersPlay]

In the set I used I think there were 9 that medusa could help solve (out of 225 or so). But the point is, using strategies like medusa does not save time. It is relatively rare can help, so you better off backtracking after a few basic startegies. Is it possible that there exists sudoku that can solved lightning fast with medusa, but very slow without it? Possible. But it's probably very rare.

[@kama2106]

Awesome video but lacks reasoning and examples

[@GamesComputersPlay]

I would recommend my other video about sudoku with detailed explanation of how each strategy works. It has examples too :)

[@fernandobravo650]

Go away