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

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?)

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

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

takes mine 0.008s to figure out.

running it on a supercomputer doesn't count

Quote:

---

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)

Quote:

---

Use release mode rather than debug mode. This halfed the time.

---

Pretty much what I found also.

Quote:

---

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.

Quote:

---

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.

Quote:

---

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.

Quote:

---

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.

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.

Quote:

---

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

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

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.

Quote:

---

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*

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

Yeah I have lookup arrays for both popcount and bsr.

Quote:

---

Originally Posted by cyberfish

Yeah I have lookup arrays for both popcount and bsr.

---

Not sure, but my guess would be that having one array with both values at once would be beneficial, as you will often find that you need to get the count, and then the bsr value.

--
Mats

I have now implemented the "check if the sub-section can be solved" - however, it's now slower than before - probably due to naff implementation that takes too long to check each candidate. I have an idea of how to make it a bit better.

Edit: My idea didn't help much. I think it's time to get rid of linked lists and start using a bitmap [which in fact was my initial approach - I just had some other bugs, and didn't realize that the problems I had was completely unrelated to the storage of the candidates, but rather a logical problem in detecting the solution is finished.]

But the anon "unsolvable" is solved in "zero time" as my code is now immediately recognizing that there's no valid solution.

--
Mats

Quote:

---

I have now implemented the "check if the sub-section can be solved" - however, it's now slower than before - probably due to naff implementation that takes too long to check each candidate. I have an idea of how to make it a bit better.

---

I also just implemented this idea myself.
I found that it made it faster for the cases of checking whether there are numbers that cannot appear in any row or column.
However after then adding the check for numbers that cannot appear in any 3x3 grid, most of that performance gain went away again. At first I thought that the check was just slow enough that it outweighted the bennefit, however upon debugging a few boards, I found that the return statement was actually never being hit. So although I'm sure one can craft a board that will hit this case on the first call, on the majority of boards all that extra checking is for nothing.
Whereas the row and column checks seemed to be hit frequently - go figure!

So yeah, mine's down to 1.1ms now for the hardest board, and I've updated the source file I linked to earlier on my site.

we should try something like 25*25 sudoku... that should be more of a challenge for computers :).

Quote:

---

Originally Posted by cyberfish

we should try something like 25*25 sudoku... that should be more of a challenge for computers :).

---

heh...would they still have to equal 9? I can see that getting a little complicated :-p

I solved a 25x25 Sudoku. Took me days. 25 rows, 25 columns, 25 5x5 subgrids. Instead of numbers, you fill in the letters A-Y.

I have never seen that before and I didnt even know it existed...that sounds masochistic.

why not just solve it then test is it follows the rules. hmm.... but then you would need a break if it is impossible to solve, lets say after 100 loops? you will need 81 at max for sure but 100 is a rounder number, do it like this

Code:

---

for(int loops_run = 0; !solved && loops_run < 100; loops_run++)
{
    // the code implementing your solver
}

---

O_o

Please don't bump old threads without an extremely good reason.

I was expecting revelations...

Soma

And that wasn't a good reason.

Closed.