Contest 6 - Sudoku solver - Discussion - Page 8-VBForums
Page 8 of 11 FirstFirst ... 567891011 LastLast
Results 281 to 320 of 417

Thread: Contest 6 - Sudoku solver - Discussion

  1. #281
    Member
    Join Date
    Aug 2005
    Posts
    50

    Re: Contest 6 - Sudoku solver - Discussion

    I mean, how do you verify that they have a unique solution ?

  2. #282

    Thread Starter
    Super Moderator manavo11's Avatar
    Join Date
    Nov 2002
    Location
    Other side of town from si_the_geek
    Posts
    7,171

    Re: Contest 6 - Sudoku solver - Discussion

    1 week left Start wrapping them up slowly


    Has someone helped you? Then you can Rate their helpful post.

  3. #283
    No place like 127.0.0.1 eyeRmonkey's Avatar
    Join Date
    Jul 2005
    Location
    Blissful Oblivion
    Posts
    2,306

    Re: Contest 6 - Sudoku solver - Discussion

    Quote Originally Posted by dukuso
    I mean, how do you verify that they have a unique solution ?
    I somewhat doubt that he is. It's not too hard to make a program that throws 1-9 in a few cells, but making one that generates puzzles with unique soultions is a little more tough.
    Visual Studio 2005 Professional Edition (.NET Framework 2.0)
    ~ VB .NET Links: Visual Basic 6 to .NET Function Equivalents (Thread) | Refactor! (White Paper) | Easy Control for Wizard Forms | Making A Proper UI For WinForms | Graphics & GDI+ Tutorial | Websites For Free Icons
    ~ QUOTE: Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the Universe trying to produce bigger and better idiots. So far, the Universe is winning. -Rich Cook

    ~ eyeRmonkey.com

  4. #284
    Banned dglienna's Avatar
    Join Date
    Jun 2004
    Location
    Center of it all
    Posts
    17,901

    Re: Contest 6 - Sudoku solver - Discussion

    I think that I've read that you can use the four corners of a grid, to substiitute 4 different ways to solve any puzzle. This ignores the center cell also.

  5. #285
    VB6, XHTML & CSS hobbyist Merri's Avatar
    Join Date
    Oct 2002
    Location
    Finland
    Posts
    6,654

    Re: Contest 6 - Sudoku solver - Discussion

    I have some good news for you all. At some point of optimizing, my code has broken. So, there are some puzzles that fail to solve. You lot must be happy now, I don't know if I have the time to figure out the bug.

  6. #286
    Member
    Join Date
    Aug 2005
    Posts
    50

    Re: Contest 6 - Sudoku solver - Discussion

    ahh, why should we be happy ? Because that increases the chances of others
    to win ? Some wise philosoph said: with sudoku not the solution counts,
    but the path which you take. (or was it a newpaper journalist ? , well,
    could have been Konfuzius too)

    If it took you weeks to find a puzzle which wasn't solved, then
    the judges won't probably have one for the contest.

  7. #287
    VB6, XHTML & CSS hobbyist Merri's Avatar
    Join Date
    Oct 2002
    Location
    Finland
    Posts
    6,654

    Re: Contest 6 - Sudoku solver - Discussion

    No no, there are even basic ones that don't get solved. I didn't check for valid solutions for about a week (which was a bit silly of me, but I were a bit tired many of the times I coded), and now I've changed the code so much that it is very hard to find the error. I've tracked it as far as to the backtracker code itself, there seems to be no error in the logics. In worst case I have to rewrite the whole backtracker. Sounds nice, huh?

    Every 1/50 puzzle seems to cause problems.

  8. #288
    Member
    Join Date
    Aug 2005
    Posts
    50

    Re: Contest 6 - Sudoku solver - Discussion

    just take your program from one week ago. Maybe the one you posted ?

  9. #289
    VB6, XHTML & CSS hobbyist Merri's Avatar
    Join Date
    Oct 2002
    Location
    Finland
    Posts
    6,654

    Re: Contest 6 - Sudoku solver - Discussion

    Whew. Luckily I had made a solution counter, which had almost the exact same code I happened to have a few days ago. So, now I can try to apply the new optimizations again and see when the error comes in. The latest optimization I did was pretty effective...

    Edit Darn. Still not wholly clear. Debug, debug... Finally! Another error found in the naked subset code.
    Last edited by Merri; Aug 20th, 2005 at 04:42 PM.

  10. #290
    Member
    Join Date
    Aug 2005
    Posts
    50

    Re: Contest 6 - Sudoku solver - Discussion

    sounds as if your solver might suffer from complicatedness...
    while you're there, could you measure how many % speedincrease these
    "naked subsets" gave you ? Is it worth the trouble ?

  11. #291
    VB6, XHTML & CSS hobbyist Merri's Avatar
    Join Date
    Oct 2002
    Location
    Finland
    Posts
    6,654

    Re: Contest 6 - Sudoku solver - Discussion

    When doing the 7611 minimal sudokus, it gave about 20% speed increase while retaining most sudokus valid. Note that it didn't take too long to fix the code, I just had to push time from something else (sorry Something Else for doing that). Though I need more time to analyze why the subset code doesn't work as it should.

  12. #292
    Lively Member Something Else's Avatar
    Join Date
    Nov 2003
    Location
    Where Humboldt Intersects Carlson
    Posts
    99

    Re: Contest 6 - Sudoku solver - Discussion

    Heh, I understand, I also push time from myself every now and then.

    I Just had a bout of optimizationitus myself. I created a total rewrite of my generators solver, and It looks really good, although I havn't written any backtracking into it yet. I've been trying to get it to solve all my submissions without any backtracking. It solves all but the final 15 of my last submissions. I wrote a procedure that I thought was a generic version of several other strategies. But it, for some reason, couldn't solve 1 extra submission. In actuality, it made it impossible, blanking out all possibles for 1 cell and 1 cell only!!! I debugged it, and it worked in tandom with all the other procedures. But, commenting out the ones I thought it replaced, I saw it was lacking something. So, I'll comment it out, since it doesn't do anything extra even if I keep it.

    I'm just going to go back to my old code, put a counter in a couple of spots, and tweak my generator a hair.


    -Lou
    no soap...radio -mendhak

    I understand...just a little...
    No comprende, it's a riddle
    - Wall of Voodoo-Mexican Radio

  13. #293
    New Member
    Join Date
    Aug 2005
    Posts
    11

    Re: Contest 6 - Sudoku solver - Discussion

    I'm done, finished, finito.
    I have submitted my proggy and that's it. Am i the first?
    Maybe I get some sleep again at night now, lovely.
    Good luck to all of ya.

  14. #294

    Thread Starter
    Super Moderator manavo11's Avatar
    Join Date
    Nov 2002
    Location
    Other side of town from si_the_geek
    Posts
    7,171

    Re: Contest 6 - Sudoku solver - Discussion

    Quote Originally Posted by Brick1
    I'm done, finished, finito.
    I have submitted my proggy and that's it. Am i the first?
    Maybe I get some sleep again at night now, lovely.
    Good luck to all of ya.
    You're the 2nd Good luck to you too


    Has someone helped you? Then you can Rate their helpful post.

  15. #295
    Member
    Join Date
    Aug 2005
    Posts
    50

    Re: Contest 6 - Sudoku solver - Discussion

    not that it were so important for me, but just assume that
    I wanted to submit something. I have a C-program which reads
    sudokus from a file and solves them, So how much work is it
    to meet the contest requirements ?
    what's "C#" ? How to make it "callable", how to prompt, etc.

  16. #296
    Addicted Member
    Join Date
    Jan 2004
    Location
    philippines
    Posts
    245

    Re: Contest 6 - Sudoku solver - Discussion

    hehe i have made a checker not a solver. hehe guess that doesn't count for the contest.. oh well i am trying to create a new theory for solving sudoku puzzles i just have to make something out of my theory.. will the codes be posted? I can't wait to see those codes..

  17. #297
    VB6, XHTML & CSS hobbyist Merri's Avatar
    Join Date
    Oct 2002
    Location
    Finland
    Posts
    6,654

    Re: Contest 6 - Sudoku solver - Discussion

    dukuso: C# is Microsoft's somewhat new language, which came with .NET when it appeared a few years ago. You can compile C# programs for free if you get the .NET framework.

    For the requirements, there is another thread about it which should be rather straightforward.

    titan7262: yes, the codes will be available.

  18. #298
    Member
    Join Date
    Aug 2005
    Posts
    50

    Re: Contest 6 - Sudoku solver - Discussion

    oh, I thought it were something like C++ or such, an extension of C.
    I guess, I'm out then. Maybe I shouldn't have come here in the first place.?!

    Hmm, shall I post my link to another paper as goodbye ?
    I know, you're eager to read these papers...

  19. #299
    VB6, XHTML & CSS hobbyist Merri's Avatar
    Join Date
    Oct 2002
    Location
    Finland
    Posts
    6,654

    Re: Contest 6 - Sudoku solver - Discussion

    C# is close to C++ in syntax, though it is more managed and it is easier to add GUI to it. I don't know much else about it. C# can be compiled to any environment that has a .NET compiler and framework available (Linux included).

  20. #300
    Lively Member Something Else's Avatar
    Join Date
    Nov 2003
    Location
    Where Humboldt Intersects Carlson
    Posts
    99

    Re: Contest 6 - Sudoku solver - Discussion

    Quote Originally Posted by dukuso
    oh, I thought it were something like C++ or such, an extension of C.
    I guess, I'm out then. Maybe I shouldn't have come here in the first place.?!

    Hmm, shall I post my link to another paper as goodbye ?
    I know, you're eager to read these papers...
    Why are you out of here?
    We have a C and C++ area,
    and if you know those, go ahead and code an entry with it!
    Heck! We have assembly here! Code it in assembly!


    -Lou
    no soap...radio -mendhak

    I understand...just a little...
    No comprende, it's a riddle
    - Wall of Voodoo-Mexican Radio

  21. #301
    VB6, XHTML & CSS hobbyist Merri's Avatar
    Join Date
    Oct 2002
    Location
    Finland
    Posts
    6,654

    Re: Contest 6 - Sudoku solver - Discussion

    Can I code one in FreeBASIC?

  22. #302
    Member
    Join Date
    Aug 2005
    Posts
    50

    Re: Contest 6 - Sudoku solver - Discussion

    Quote Originally Posted by Something Else
    Why are you out of here?
    We have a C and C++ area,
    and if you know those, go ahead and code an entry with it!
    Heck! We have assembly here! Code it in assembly!


    -Lou

    who is "we" ?
    where is that area ?
    Are you saying, there is(or will be) a sudoku-programming contest in C ?
    Yes, I think I could do it in assembly, but why should I rewrite it,
    when it already works in C ?

  23. #303
    Member
    Join Date
    Aug 2005
    Posts
    50

    Re: Contest 6 - Sudoku solver - Discussion

    Quote Originally Posted by Merri
    Can I code one in FreeBASIC?
    could you translate that teethy smiley into English ?
    you're going to bite someone ?

  24. #304
    Member
    Join Date
    Aug 2005
    Posts
    50

    Re: Contest 6 - Sudoku solver - Discussion

    OK, I won't post the link to the announced paper.
    Just a quote:

    "A new strategy to select the next variable and the value to branch on
    for Latin square problems was proposed in [4](2003) . This strategy clearly outperforms all the previous ones that have been tested.It consists of
    selecting the variable with the minimum domain size and then select the value
    which occurs the fewest times in the domains of the variables of the rows
    and the columns of the selected variable.We have improved this strategy...."

  25. #305
    pathfinder NotLKH's Avatar
    Join Date
    Apr 2001
    Posts
    2,397

    Re: Contest 6 - Sudoku solver - Discussion

    Quote Originally Posted by dukuso
    who is "we" ?
    "We" are you and me, everyone who particibates in VBForums.
    where is that area ?
    http://www.vbforums.com/forumdisplay.php?f=23

    Are you saying, there is(or will be) a sudoku-programming contest in C ?
    I'm sure if you asked TPTB {ie.. the Mod of the contest area}, he might accept your C entry, and compete it against every single one of the other C entries. Of course, I have no say in this matter. But if he DOES take it, You'll probably be the Best C entry for this contest to date!

    Yes, I think I could do it in assembly, but why should I rewrite it,
    when it already works in C ?
    heh! Show Off!

    -Lou

  26. #306
    pathfinder NotLKH's Avatar
    Join Date
    Apr 2001
    Posts
    2,397

    Re: Contest 6 - Sudoku solver - Discussion

    Heres some more patterns.

    I have no idea if they've become any harder. I added a counter to weight the pattern development with iteration counts on the several strategies in my generator. Let me know if I broke it.

    -Thanks
    -Lou
    Attached Files Attached Files

  27. #307
    VB6, XHTML & CSS hobbyist Merri's Avatar
    Join Date
    Oct 2002
    Location
    Finland
    Posts
    6,654

    Re: Contest 6 - Sudoku solver - Discussion

    NotLKH: this is your fifth set this far, not fourth Unless I'm very badly mistaken...

    Anyways, still relatively easy. 25 ms for 314 files = 0,08 ms per file. Compared to minimum set of 453 files: 103 ms; 0,22 ms per file. If you'd get rid of the all-too-easy ones, then your puzzles would start to compare.

    I make a "human difficulty rating" to my code after the contest is over, so then we can more clearly see which puzzles are hard and which are not. Computer speed isn't the only measure one should take into account. I already have an idea on how to make it.

  28. #308
    pathfinder NotLKH's Avatar
    Join Date
    Apr 2001
    Posts
    2,397

    Re: Contest 6 - Sudoku solver - Discussion

    I'd like to, hence My Ratings.
    I just need feedback to determine what the ratings signifies in difficulty.

    If you can list each ones speed, that'd help me determine whats what.


    -Lou

  29. #309

    Thread Starter
    Super Moderator manavo11's Avatar
    Join Date
    Nov 2002
    Location
    Other side of town from si_the_geek
    Posts
    7,171

    Re: Contest 6 - Sudoku solver - Discussion

    The contest is for VB6, VB.Net and C#. I don't really know if it would be fair to compare a C entry with any of those...


    Has someone helped you? Then you can Rate their helpful post.

  30. #310
    VB6, XHTML & CSS hobbyist Merri's Avatar
    Join Date
    Oct 2002
    Location
    Finland
    Posts
    6,654

    Re: Contest 6 - Sudoku solver - Discussion

    It would be, dukuso already mentioned mine is faster Aren't we keeping it separate anyways or will all be in the same category and compared against eachother?

  31. #311

    Thread Starter
    Super Moderator manavo11's Avatar
    Join Date
    Nov 2002
    Location
    Other side of town from si_the_geek
    Posts
    7,171

    Re: Contest 6 - Sudoku solver - Discussion

    The 3 categories I mentioned are going to be marked seperately. I meant that C doesn't fit in any of the 3 categories so I don't know if it would be fair to compare it with the entries of any of the 3 categories. Better now?


    Has someone helped you? Then you can Rate their helpful post.

  32. #312
    pathfinder NotLKH's Avatar
    Join Date
    Apr 2001
    Posts
    2,397

    Re: Contest 6 - Sudoku solver - Discussion

    2 More days!

    Here's the last that I'll post before the contest. Any feedback would be nice!

    If you've wondered, the followin is what the numbers mean in the sol file name.

    Given a filename like : 026_0674_0015-000019__Solved.sol

    The first Set, 3 digits, indicates the number of exposed cells in the initial puzzle.
    The second set, 4 digits, is the sequence index it was generated at.
    The third set, 4 digits, is a binary composite:
    1. A Zero means it only used naked and hidden singles
    2. 1 s: If it detected a number in a shared set of 3 cells at the intersection of a row/col and a 3x3 square that wasn't anywhere else in the row/col, but was in multiple other cells in the SQUARE, it was removed from the other multiple cells.
    3. 2: Same as 1, except the other way
    4. 4: Naked pairs were detected and processed
    5. 8: Hidden pairs were detected and processed
    6. 16: Naked and/or hidden trips were detected and processed
    7. 32: If I had it activated, it would mean naked/hidden Quads were detected and processed
    8. 64: This means, if after iterating thru all the first strategies until exhausted, and the puzzle still wasn't solved, then it went into the full iterate all posibles mode, until it found a solution. In my generator, it also counts all the solutions possible, and any that had more than 1 solution was considered a failure. None of these really should have more than 1 solution.

    The 4th set, 6 digits, meant 2 possible things:
    1. If the 3rd set < 64, then it is the count of how many times it looped adding sets of cells with only 1 possible into the solution matrix
    2. if the third set was >= 64, then it indicates how many total possibles were available to all the unassigned cells, before it went into the 64 mode. Then I added 100.


    This 4th number was what I used to filter on my generator as I tested removing revealed cells from an initiating set of succesful revealed cells.

    Lets say, if I had a msk set of 26 cells that led to a solution, I would build and test 26 subsets, each of the the 26 combinations of 25 cells of this msk set, removing 1 of each 26 revealed cells. I would note which subset worked, and I would select the one with the largest 4th number as the new msk to test.

    As I worked down, once I reached a set that had no good subsets, then that is the one that I'd output as a new msk entry.

    Attached is my newest set, using the strategies as I've explained them, above.


    -Lou
    Attached Files Attached Files

  33. #313
    VB6, XHTML & CSS hobbyist Merri's Avatar
    Join Date
    Oct 2002
    Location
    Finland
    Posts
    6,654

    Re: Contest 6 - Sudoku solver - Discussion

    Finally submitted the code. Did some final changes to actually meet the contest requirements... noticed the required output timings file format just when doing last time reading of the rules.

    Happy benchmarking!

  34. #314
    No place like 127.0.0.1 eyeRmonkey's Avatar
    Join Date
    Jul 2005
    Location
    Blissful Oblivion
    Posts
    2,306

    Re: Contest 6 - Sudoku solver - Discussion

    I think I joined the contest a little too late. I am just now to the point of optimizing things (after finishing my backtracker). Each optimization I do breaks the whole solver for a while (until I can work out all the bugs), so I will be lucky to get 0 based arrays and 1-D arrays done by friday.

    Can I turn it in at midnight on friday (my time zone)?
    Last edited by eyeRmonkey; Aug 25th, 2005 at 12:09 PM. Reason: spelling
    Visual Studio 2005 Professional Edition (.NET Framework 2.0)
    ~ VB .NET Links: Visual Basic 6 to .NET Function Equivalents (Thread) | Refactor! (White Paper) | Easy Control for Wizard Forms | Making A Proper UI For WinForms | Graphics & GDI+ Tutorial | Websites For Free Icons
    ~ QUOTE: Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the Universe trying to produce bigger and better idiots. So far, the Universe is winning. -Rich Cook

    ~ eyeRmonkey.com

  35. #315
    VB6, XHTML & CSS hobbyist Merri's Avatar
    Join Date
    Oct 2002
    Location
    Finland
    Posts
    6,654

    Re: Contest 6 - Sudoku solver - Discussion

    You're slow. You get eaten. That's the rule of the jungle.

    You ought to be a monkey so code like one! Code like mad!


    Easier said than done, but I'm done already so there shouldn't be much to complain about Oh, btw, I tried converting my solver to do 5 x 5 puzzle... it would be great, if all my optimization arrays worked in that mode, they take almost 100 MB unless I counted wrong... my computer just swaps when I start the project Don't know if it solves, this far I've had some typos... too many of them. Subscript out of range etc.

  36. #316

    Thread Starter
    Super Moderator manavo11's Avatar
    Join Date
    Nov 2002
    Location
    Other side of town from si_the_geek
    Posts
    7,171

    Re: Contest 6 - Sudoku solver - Discussion

    I'll accept entries submitted till midnight Friday GMT. It's the easiest to keep track


    Has someone helped you? Then you can Rate their helpful post.

  37. #317
    No place like 127.0.0.1 eyeRmonkey's Avatar
    Join Date
    Jul 2005
    Location
    Blissful Oblivion
    Posts
    2,306

    Re: Contest 6 - Sudoku solver - Discussion

    Well, I got the base 0 arrays working and got a slight speed increase and 1-D arrays are coming along nicely (although I am not far enough to get to the debugging part yet and I think they might turn out to be hell).

    I have at least 10 other optimizations to do and I know I won't have time for all of them. The only reason I am getting so much done today is because my girlfriend is busy for the first day in the last 2 weeks and we aren't hanging out today (well, we are, but not until later tonight).


    GMT sounds fair enough manavo.

    /me walks over to google to find a time convert

    EDIT: Crap! Thats 7AM friday for me. I won't even be up by then. I guess I can stay up all night thursday and be useless. Fun fun!
    Last edited by eyeRmonkey; Aug 24th, 2005 at 08:52 PM.
    Visual Studio 2005 Professional Edition (.NET Framework 2.0)
    ~ VB .NET Links: Visual Basic 6 to .NET Function Equivalents (Thread) | Refactor! (White Paper) | Easy Control for Wizard Forms | Making A Proper UI For WinForms | Graphics & GDI+ Tutorial | Websites For Free Icons
    ~ QUOTE: Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the Universe trying to produce bigger and better idiots. So far, the Universe is winning. -Rich Cook

    ~ eyeRmonkey.com

  38. #318
    VB6, XHTML & CSS hobbyist Merri's Avatar
    Join Date
    Oct 2002
    Location
    Finland
    Posts
    6,654

    Re: Contest 6 - Sudoku solver - Discussion

    You sure you counted to 23:59 of Friday and not 0:00 of Friday? Afaik you have 30 hours to go at the moment.

  39. #319

    Thread Starter
    Super Moderator manavo11's Avatar
    Join Date
    Nov 2002
    Location
    Other side of town from si_the_geek
    Posts
    7,171

    Re: Contest 6 - Sudoku solver - Discussion

    I mean the night from Friday to Saturday midnight...


    Has someone helped you? Then you can Rate their helpful post.

  40. #320
    Fanatic Member kaffenils's Avatar
    Join Date
    Apr 2004
    Location
    Norway
    Posts
    946

    Re: Contest 6 - Sudoku solver - Discussion

    Thats it. I have submitted my contribution. I don't stand a chance agains Merri's solver , but I'll be happy as long as I don't loose.

    The most important thing is to participate, not to win... I guess

Page 8 of 11 FirstFirst ... 567891011 LastLast

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Featured


Click Here to Expand Forum to Full Width

Survey posted by VBForums.