# Thread: Sudoku solver...

1. ## Sudoku solver...

In response to my posts here:
http://cboard.cprogramming.com/showthread.php?t=109951
where I "bragged" about my 3+s solver.

I'm not quite down to single millisecond solution, but I'm quite pleased with my 100x speed improvement for my particular test-case - currently solved in 31 ms on my rather ancient machine with rather slow memory.

Steps to improve it:
[list]
1. Use release mode rather than debug mode. This halfed the time.
2. Keep track of the count of candidates for each cell, instead of counting them. Not much gain, but made some of the logic simpler, so worth having anyways.
3. Do not use recursion unless there's a multiple candidates for this cell (so, if we are just following up on the consequence of a move that leaves us with single digit candidates in some other places, just continue filling those in). Since recursion also means copying the board and solution details, it's a good save. This got me to sub half a second for my benchmark casse
4. Check if there is a possible solution, and abort immediately if we have cells with no candidates [so the 1234 down the bottom right and 56789 across the bottom posted by anon is solved in "0" time].

Using a linked list for candidates was done to make the code simple - I can most likely gain quite a bit by having a more compact storage of candidates - e.g. a bitmap.

Some of the code is also "neat but not fast", e.g. I have accessor functions to get to CandidateList(x, y) that returns a reference to that candidate list. There may be better ways to do that.

But I still feel quite chuffed, it only took a few hours.

--
Mats

2. The other unsolvable type that has caused me trouble looks like this:

Code:
```......1..
.........
.........
.........
.......1.
.........
.1.......
.....1...
........2```
(Nowhere to put 1 in bottom-right block since the only spot is occupied by 2.)

How does yours handle this? (BTW, am I blind or the code is not there?)

3. I haven't posted the code, because it's quite "messy" (it's in several files, intermixed with a large chunk of GUI code using MFC - you can also "play it yourself" - the original intention with the solver was to generate a board, to THEN solve manually).

I will give your unsolvable board a try - I think my code handles it - but I don't know for sure.

--
Mats

4. My solver figured out that it was unsolvable, but it took 17 seconds to figure that out. I guess that I need to check that "there are no missing candidates" in a 3 x 3 square either...

More code - but may make it faster by eliminating another lot of useless possibilities.

--
Mats

5. takes mine 0.008s to figure out.

6. running it on a supercomputer doesn't count

7. processor : 1
vendor_id : GenuineIntel
cpu family : 6
model : 15
model name : Intel(R) Core(TM)2 CPU 6300 @ 1.86GHz
stepping : 6
cpu MHz : 2400.000
cache size : 2048 KB
physical id : 0
siblings : 2
core id : 1
cpu cores : 2
fpu : yes
fpu_exception : yes
cpuid level : 10
wp : yes
flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx lm constant_tsc arch_perfmon pebs bts rep_good pni monitor ds_cpl vmx est tm2 ssse3 cx16 xtpr lahf_lm
bogomips : 6300.01
clflush size : 64
cache_alignment : 64
address sizes : 36 bits physical, 48 bits virtual
power management:
6300 bogomips! =D

(should be 3.3ghz, not detected correctly for some reason)

8. Use release mode rather than debug mode. This halfed the time.
Pretty much what I found also.

Keep track of the count of candidates for each cell, instead of counting them. Not much gain, but made some of the logic simpler, so worth having anyways.
Actually that's not something I did, and I'm not sure it would help in my case.

Do not use recursion unless there's a multiple candidates for this cell (so, if we are just following up on the consequence of a move that leaves us with single digit candidates in some other places, just continue filling those in). Since recursion also means copying the board and solution details, it's a good save. This got me to sub half a second for my benchmark casse
Check if there is a possible solution, and abort immediately if we have cells with no candidates [so the 1234 down the bottom right and 56789 across the bottom posted by anon is solved in "0" time].
I don't copy the board on recursion, I only copy the array of possible moves, which is just 162 bytes. So I'm quite happy leaving mine performing the check for needing to backtrack upon the next call. I consider it essential to abort as soon as you detect that there are no possible moves for a cell though.

Using a linked list for candidates was done to make the code simple - I can most likely gain quite a bit by having a more compact storage of candidates - e.g. a bitmap.
Yeah I used the bitflags approach, as did the other guy who got a fast solver in that last thread.

Some of the code is also "neat but not fast", e.g. I have accessor functions to get to CandidateList(x, y) that returns a reference to that candidate list. There may be better ways to do that.
Yup, at some point it's speed over convenience. Bitflags work fine for me, as it feels like I've got the best of both.

I uploaded my solver to my site a few days ago. You can find it at the bottom of the page here.

9. The example puzzle probably causes trouble if you always fill the cells in the same order (since the conflict would only appear when you get close to the end). I think somebody had code that determines the most suitable order in which to fill the cells, in which case they might start solving at the lower-right corner and discover the conflict early on.

10. Originally Posted by anon
The example puzzle probably causes trouble if you always fill the cells in the same order (since the conflict would only appear when you get close to the end). I think somebody had code that determines the most suitable order in which to fill the cells, in which case they might start solving at the lower-right corner and discover the conflict early on.
Well, I actually tried to extend the "detect if there is no solution" to detect that it's not worth trying. I got it down to 6 something seconds, but my logic is still flawed - and I know why, I just haven't implemented the code yet [I need to refactor the function a bit, to avoid having 4 levels of nested loops with a couple of nested if-statements, and it's not complete yet, so at 1.30AM I decided to give up on that].

--
Mats

11. iMalc: The point about detecting if it's possible to solve or not wasn't so much to avoid that ONE recursion level, but rather that my code didn't detect cases where it was not possible to solve because some cells had no candidates. So it would happily go round filling in the rest of the cells until it had NO cells left to set and some cells where not filled in. Then go back to the previous branch and try some other combination. Of course, since there are MANY wrong paths, it would take quite some time (around a 1.5 seconds in my benchmark case) to find the actual solution.

Having a count helps when you have a linked list. If you have a bitmap, it would also help a little bit in selecting the next candidate(set), but not as much as in a linked list, I don't think.

I've just started on the refactoring of the "detect if we're in an impossible scenario" function, so that it detect cases where one number within a 3 x 3 square is not possible to set, and don't try any further if it's not possible to get all digits in a square - again, this will help the overall solution time by not going down a path that will end up a dead-end.

--
Mats

12. Thanks for clearing up my one recursion level assumption.

The idea of detecting when there are no possibile places for a certain digit in a row, column or 3x3, could be worth trying in my implementation.
I first thought it would be redundant as everything is marked off in advance, as it goes, but the solver can easily mark off the possibility that there is a six at all in a particular row for example, and so long as none of the cells in that row then only have one solution, it is allowed to continue.
I will add this to my solver also, tonight.

13. Having a count helps when you have a linked list. If you have a bitmap, it would also help a little bit in selecting the next candidate(set), but not as much as in a linked list, I don't think.
Really? The bimap is just 9-bits, so an array lookup (precomputed bsr) will do (that's what I am doing in my program).

I think "detecting impossible scenario" is well worth it. With incrementally updated candidate lists, it's just checking 81 pointers (in the case of linked list), or 81 bitmaps against 0.

If looping is not wanted, perhaps it can be checked every time the candidate lists are changed (if a candidate list reaches 0, it's a dead end).

I'm not sure which approach is faster, but I am guessing they are both faster than not checking at all.

*edit* I do it at the same time as searching for the square with fewest possible candidates, so there is hardly any performance penalty. */edit*

14. Yes, a 512 entry bitmap-to-number-of-candidates would be much easier and probably faster. We don't need that much memory for the solver, so it will probably hang around in the L1 cache all the time.

--
Mats

15. Yeah I have lookup arrays for both popcount and bsr.

Popular pages Recent additions