Thread: Sudoku solver...

  1. #1
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677

    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  2. #2
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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 might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  3. #3
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  5. #5
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    takes mine 0.008s to figure out.

  6. #6
    Registered User
    Join Date
    Oct 2001
    Posts
    2,129
    running it on a supercomputer doesn't count

  7. #7
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    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. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  9. #9
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  10. #10
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by anon View Post
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  11. #11
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  12. #12
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  13. #13
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    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*
    Last edited by cyberfish; 12-16-2008 at 01:03 PM.

  14. #14
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  15. #15
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    Yeah I have lookup arrays for both popcount and bsr.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. sudoku - arrays
    By rocketman50 in forum C++ Programming
    Replies: 2
    Last Post: 03-21-2008, 09:20 AM
  2. Help for a sudoku Solver
    By axilleask in forum C Programming
    Replies: 3
    Last Post: 11-26-2007, 04:28 PM
  3. Sudoku Puzzle Solver?
    By Apocalypse in forum C Programming
    Replies: 7
    Last Post: 03-12-2006, 02:10 PM
  4. Newbie with a Sudoku Solver program
    By TylerBill in forum C Programming
    Replies: 13
    Last Post: 03-08-2006, 07:27 PM
  5. Sudoku - the new addiction
    By axon in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 11-07-2005, 11:39 PM