Sudoku solver...

This is a discussion on Sudoku solver... within the C++ Programming forums, part of the General Programming Boards category; Originally Posted by cyberfish Yeah I have lookup arrays for both popcount and bsr. Not sure, but my guess would ...

  1. #16
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by cyberfish View Post
    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
    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. #17
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Last edited by matsp; 12-16-2008 at 02:35 PM.
    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.

  3. #18
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    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.
    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"

  4. #19
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,183
    we should try something like 25*25 sudoku... that should be more of a challenge for computers .

  5. #20
    Registered User
    Join Date
    Dec 2008
    Posts
    5
    Quote Originally Posted by cyberfish View Post
    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

  6. #21
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    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.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  7. #22
    Registered User
    Join Date
    Dec 2008
    Posts
    5
    I have never seen that before and I didnt even know it existed...that sounds masochistic.

  8. #23
    Registered User bobknows's Avatar
    Join Date
    Jan 2011
    Location
    SD
    Posts
    87
    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
    }

  9. #24
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,370
    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.

  10. #25
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,598
    Closed.

Page 2 of 2 FirstFirst 12
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, 10: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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21