Page 10 of 11 FirstFirst ... 7891011 LastLast
Results 361 to 400 of 417

Thread: Contest 6 - Sudoku solver - Discussion

  1. #361
    Addicted Member
    Join Date
    Aug 2005
    Location
    York
    Posts
    197

    Re: Contest 6 - Sudoku solver - Discussion

    Yay finally ....Compiled here we go....now for the results
    Note: Pentium Optimisations are for Pentiums Pro ,I - when VB6 was released.
    Pentium 4 has completely different architecture so the optimisations won't improve on performance.
    Last edited by Raedwulf; Aug 27th, 2005 at 03:20 PM.

  2. #362
    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

    Ah. I hope manavo releases the results soon. I just hope I don't get last place.

    Hey, why didn't CVMicheal enter? Or did he not do VB6. I remember he was really into it earlier in the contest. Hmmmm.
    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

  3. #363

    Thread Starter
    Super Moderator manavo11's Avatar
    Join Date
    Nov 2002
    Location
    Around the corner from si_the_geek
    Posts
    7,171

    Re: Contest 6 - Sudoku solver - Discussion

    OK then, results

    VB 6 winner : Merri
    VB.Net winner : ntg

    Congrats


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

  4. #364

    Thread Starter
    Super Moderator manavo11's Avatar
    Join Date
    Nov 2002
    Location
    Around the corner from si_the_geek
    Posts
    7,171

    Re: Contest 6 - Sudoku solver - Discussion

    Here are the results in the excel file

    ntg wins by default, since he had the only .Net entry

    Also, eyeRmonkey, I really don't understand what on earth happened, but your code solved all the sudokus in the IDE but not compiled! I have no idea why, and I would really appreciate it if anyone else could test it! Thanks
    Attached Files Attached Files
    Last edited by manavo11; Aug 27th, 2005 at 06:02 PM.


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

  5. #365
    New Member
    Join Date
    Aug 2005
    Posts
    11

    Re: Contest 6 - Sudoku solver - Discussion

    congrats merri, and the rest.
    And thx manavo! good job.

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

    Re: Contest 6 - Sudoku solver - Discussion

    Yay! Now if I just had Excel... need to download OpenOffice.org to see the file. 71 MB, I'm waiting for you...

  7. #367

    Thread Starter
    Super Moderator manavo11's Avatar
    Join Date
    Nov 2002
    Location
    Around the corner from si_the_geek
    Posts
    7,171

    Re: Contest 6 - Sudoku solver - Discussion

    Code:
    Username	VB Version	Total Time (IDE)	Total Time (Compiled)
    
    Brick1	               6	7.824347	       0.38939
    bpd	               6	1.93226625	       0.33901571
    Merri	               6	3.264567	       0.170920885
    kaffenils	       6	41.600266	       4.907671
    Raedwulf	       6	18.43646273	       0.578268467
    eyeRmonkey	       6	20.194833	       1.779405 (not all solved!)
    
    ntg	               .Net     0.77159332	       0.62759289
    Last edited by manavo11; Aug 27th, 2005 at 06:11 PM. Reason: Fixed table (added tags)


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

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

    Re: Contest 6 - Sudoku solver - Discussion

    Ok, thanks Still downloading OO.org though, I seriously have a need for Excel support.

    Seems like they've made the IDE support much speedier in .NET... in the other hand, there is no P-Code there. But for now, we are waiting to see each others codes

  9. #369

    Thread Starter
    Super Moderator manavo11's Avatar
    Join Date
    Nov 2002
    Location
    Around the corner from si_the_geek
    Posts
    7,171

    Re: Contest 6 - Sudoku solver - Discussion

    Thanks for reminding me Forgot to move them back


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

  10. #370

    Thread Starter
    Super Moderator manavo11's Avatar
    Join Date
    Nov 2002
    Location
    Around the corner from si_the_geek
    Posts
    7,171

    Re: Contest 6 - Sudoku solver - Discussion



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

  11. #371
    I'm about to be a PowerPoster!
    Join Date
    Jan 2005
    Location
    Everywhere
    Posts
    13,647

    Re: Contest 6 - Sudoku solver - Discussion

    In .NET there is no P-Code as Merri says. All the difference is a debugger is attached (the IDE) whereas compiled there isn't. Plus it is both IL.

    I wsa going to enter this competition myself, just for kicks, but I guess I'm not smart enough I understand the concept but can't for the life of me solve one by hand. My solver got as far as solving rows and then once I added columns it went into an infinite loop, by which point I had a severe headache

    So when's the next contest?
    Last edited by penagate; Aug 28th, 2005 at 12:18 AM.

  12. #372
    Member
    Join Date
    Aug 2005
    Posts
    50

    Re: Contest 6 - Sudoku solver - Discussion

    here are the correlation coefficents (*100) for the timings
    of the 1011 individual instances.
    I included mine as (duk).
    Send your timings to sterten(at)aol.com if you want to be
    included in that table and aren't already.
    (or have other datasets from different versions)
    just send or post a file with 1011 numbers for the timings.
    don't shuffle the instances !
    norming of the timings, multiplying by a positive constant,
    adding a constant doesn't matter.

    99 : very similar , linearly dependent
    00 : completely independent


    there could be some errors due to the ordering of the instances.
    I can't believe that bpd,rae,eye should have got
    timings so much different from mer,bri,kaf,duk !



    mer bpd bri rae eye kaf duk
    mer -- 06 22 09 07 29 42
    bpd 06 -- 04 05 00 03 02
    bri 22 04 -- 05 07 20 36
    rae 09 05 05 -- 01 20 12
    eye 07 00 07 01 -- 07 07
    kaf 29 03 20 20 07 -- 40
    duk 42 02 36 12 07 40 --

    (see with fixed font)


    manavo, what computer did you use for the timings ?


    I can't read the sources. I think, I don't like VB6 ...



    can anyone do 16*16 sudokus ?
    I'd like to see timings for
    http://magictour.free.fr/su16
    (or other datasets)


    -Guenter.
    Last edited by dukuso; Aug 28th, 2005 at 12:22 AM.

  13. #373
    Addicted Member
    Join Date
    Aug 2005
    Location
    York
    Posts
    197

    Re: Contest 6 - Sudoku solver - Discussion

    Congrats Merri ....I should have done better but I did mine in two days
    Yikes amazing.....comparing amount of code I did - it isn't bad 5.64k code vs 40k +
    Do I get a prize for smallest implementation ;P
    Last edited by Raedwulf; Aug 28th, 2005 at 03:13 AM.

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

    Re: Contest 6 - Sudoku solver - Discussion

    Good Job!
    When does NTG get his custom status?
    What does Merri get, since Merri already is in the Custom Title Realm?
    Mod Powers? A forum? 2000 Rep Points?


    -Lou
    no soap...radio -mendhak

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

  15. #375
    New Member
    Join Date
    Aug 2005
    Posts
    2

    Re: Contest 6 - Sudoku solver - Discussion

    I wish this contest had been open to other than a couple of Microsoft-only languages, or I would have entered it. (My time was 253 ms on a P2-400MHz, probably would have been under 50 ms on whatever the test machine was).

    Here is a CSV file with all the results in microseconds, with my times added. This should be easy to look at or load into a spreadsheet. The last two columns, guess and place, are counters my program keeps track of. Guess is how many cells were filled in via a guess as opposed to logic. Place is the count of numbers placed into cells. 81 would be the best, more would indicate some numbers were placed incorrectly and back-tracking was needed.

    Here is the correlation matrix again:
    Code:
               Brick1 Merri Raedwulf bpd eyeRmonkey kaffenils xyzzy
    Brick1        100    23        6   4          7        21    28
    Merri          23   100        9   4          8        30    37
    Raedwulf        6     9      100   5          1        20     8
    bpd             4     4        5 100          1         3     4
    eyeRmonkey      7     8        1   1        100         8     8
    kaffenils      21    30       20   3          8       100    24
    xyzzy          28    37        8   4          8        24   100
    Four of the programs, Merri, Brick1, kaffenils, and xyzzy all have decent correlation with each other. While Raedwulf, bpd, and eyeRmonkey don't correlate with anything.

    Here is a table or normalized quantiles, which probably doesn't mean that much, but I'll explain it a bit.
    Code:
        Brick1 Merri Raedwulf   bpd eyeRmonkey kaffenils xyzzy
    0%    0.01  0.22     0.12  0.58       0.03      0.02  0.72
    33%   0.46  0.61     0.35  0.73       0.27      0.16  0.77
    50%   0.68  0.77     0.54  0.79       0.40      0.30  0.86
    67%   0.91  1.00     0.88  0.89       0.59      0.53  0.97
    100% 42.29  6.47    36.22 81.66      15.33     34.68  3.89
    First of all, the numbers in the table are normalized so that 1.00 means the average time that program took to complete a sudoku. e.g. for Merri 1.00 means 148 microseconds. Now look at the 50% row. This is the time under which the program could solve the fastest 50% of the problems. For example, Merri's is 0.77, so his program could solve half the problems in under 77% of his average time (114 us), and the other half took more than that. The 100% row is the time the slowest problem took, for example bpd's slowest problem took 81.66 times as long as his average time.

    This gives you an idea of how 'smart' the basic algorithm used was. You want the numbers to be close to 1, especially the 67% and 100% quantiles. In the 100% number is large, it means you do really bad on a few problems. If the 67% number is low, is means your average time is getting bumped up a lot by your slowest third.
    Attached Files Attached Files

  16. #376

    Thread Starter
    Super Moderator manavo11's Avatar
    Join Date
    Nov 2002
    Location
    Around the corner from si_the_geek
    Posts
    7,171

    Re: Contest 6 - Sudoku solver - Discussion

    Quote Originally Posted by penagate
    So when's the next contest?
    We're back to that again? Who wants to find an interesting topic/idea?


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

  17. #377

    Thread Starter
    Super Moderator manavo11's Avatar
    Join Date
    Nov 2002
    Location
    Around the corner from si_the_geek
    Posts
    7,171

    Re: Contest 6 - Sudoku solver - Discussion

    Quote Originally Posted by dukuso
    manavo, what computer did you use for the timings ?
    I used my laptop that isn't all that great :

    Athlon 2600 (mobility)
    192 MB RAM


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

  18. #378

    Thread Starter
    Super Moderator manavo11's Avatar
    Join Date
    Nov 2002
    Location
    Around the corner from si_the_geek
    Posts
    7,171

    Re: Contest 6 - Sudoku solver - Discussion

    Quote Originally Posted by xyzzy
    I wish this contest had been open to other than a couple of Microsoft-only languages, or I would have entered it.
    Well, the idea is to get lots of people to enter... This being a forum with it's main language being Visual Basic we attract mostly programmers that use MS products. We had VB6, VB.Net and C# as the languages. VB.Net had one entry and even though C# was asked to be included, no one coded a solver. So if we had added Delphi or Java, how many people would have submitted an entry?


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

  19. #379

    Thread Starter
    Super Moderator manavo11's Avatar
    Join Date
    Nov 2002
    Location
    Around the corner from si_the_geek
    Posts
    7,171

    Re: Contest 6 - Sudoku solver - Discussion

    Quote Originally Posted by Something Else
    Good Job!
    When does NTG get his custom status?
    What does Merri get, since Merri already is in the Custom Title Realm?
    Mod Powers? A forum? 2000 Rep Points?


    -Lou
    The grand prize is a custom title with HTML formatting to make it extra special (bold, color, stuff like that)


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

  20. #380
    pathfinder NotLKH's Avatar
    Join Date
    Apr 2001
    Posts
    2,397

    Re: Contest 6 - Sudoku solver - Discussion

    How about Linked Sudoku's?

    For example, Given N msk patterns, solve both somewhat simultaineously.
    However, the twist:

    Not only do the msk patterns contain decimal points to indicate hidden numbers, and the values 1 thru 9 to indicate revealed values, but the characters A thru I, to indicate that, across the N msk patterns, any cells that have the same character indicates those cells have identical values. But you still don't know what they are.

    VIA simultaneous solving, those Shared cells will each have their could be's removed, until at some point, their must be value will be revealed.

    BTW, the revealed cells in the msk patterns will not be sufficient, on their own, to solve that msk pattern down to an individual solution. Only when the Shared cells have been solved will there be enough info to complete the solutions.


    -Lou

  21. #381

    Thread Starter
    Super Moderator manavo11's Avatar
    Join Date
    Nov 2002
    Location
    Around the corner from si_the_geek
    Posts
    7,171

    Re: Contest 6 - Sudoku solver - Discussion

    Is this for a next contest Lou? Cause if we got 7 entries with the simple sudoku solver, I really doubt people would enter (even though I like the idea)


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

  22. #382
    pathfinder NotLKH's Avatar
    Join Date
    Apr 2001
    Posts
    2,397

    Re: Contest 6 - Sudoku solver - Discussion

    Yes, it would be for a contest.


    As you can see, at http://www.setbb.com/phpbb/viewtopic...&mforum=sudoku ,
    The contest is beginning to be talked about on other boards.'
    A new sudoku contest might attract more entrants, as it becomes more publicized.

  23. #383
    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 manavo11
    Here are the results in the excel file

    ntg wins by default, since he had the only .Net entry

    Also, eyeRmonkey, I really don't understand what on earth happened, but your code solved all the sudokus in the IDE but not compiled! I have no idea why, and I would really appreciate it if anyone else could test it! Thanks
    Really!?! AH! Thats no good. I ran home and submitted the last backup of the program I had made bevause I had been in the middle of making some changes when I left. Mabye I submitted the wrong one or something. Thats really weird. I just downloaded the puzzles, but I don't have time to test the code right now.

    Congrats Merri. I wish I had time to look at your code right now, but I am taking my girlfriend to the zoo. I'll check it out some time and kick myself in the face 100 times for not thinking of half the stuff you did.

    I really hope there is another contest soon. But then again, school starts for me soon and I won't be posting here much, and I guess I won't be programming much either.
    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

  24. #384
    New Member
    Join Date
    Aug 2005
    Posts
    11

    Re: Contest 6 - Sudoku solver - Discussion

    xyzzy concerning the normalized quantiles: what is the 0% line trying to tell us?
    I noticed my value is the lowest there! hehe, is that good or bad news?

    Some ideas for the next contest:
    - Generate a single solution 9x9 sudoku with 16 numbers revealed. or prove mathematically this is impossible.
    - Generate a single solution 9x9 sudoku where one revealed cell leads to a different unique solution for every given value from 1 to 9. or prove mathematically this is not possible.
    - Generate a single solution YxY sudoku where Y is as large as possible.
    - Rectangular sudokus YxZ with f.e. 9rowx18col where every number exists twice in every row and 3x6 block, but only once in a col. Also find other viariations.
    - 3D-sudokus. imagine!
    - Or just something very unsudoku-like

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

    Re: Contest 6 - Sudoku solver - Discussion

    I think the good thing about the contest is that the subject area varies a lot. So, I'd like to see something different again, even if I continue in the world of sudoku myself. We have the other sudoku topic somewhere elsewhere, so maybe we should get back on track with that instead of using this topic?

  26. #386

    Thread Starter
    Super Moderator manavo11's Avatar
    Join Date
    Nov 2002
    Location
    Around the corner from si_the_geek
    Posts
    7,171

    Re: Contest 6 - Sudoku solver - Discussion

    OK, let's leave this topic for discussing stuff about the contest. If anyone has anything to suggest for a new contest you can post here : http://www.vbforums.com/showthread.php?t=306604 or read other ideas and support them so maybe it will be the next one


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

  27. #387
    PowerPoster
    Join Date
    Feb 2002
    Location
    Canada, Toronto
    Posts
    5,802

    Re: Contest 6 - Sudoku solver - Discussion

    Quote Originally Posted by eyeRmonkey
    Hey, why didn't CVMicheal enter? Or did he not do VB6. I remember he was really into it earlier in the contest. Hmmmm.
    When I realized there's no way in hell I can beat anyone (epecially Merri), I even unsuscribled to this thread.
    I stopped adding stuff/improving it about 15-20 days ago...

    I just ran the contests msk files, in the IDE, I ran out of pacience waiting, and compiled it took 40.5 seconds for all the 1011 sudokus. Well, at least it solved them all...

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

    Re: Contest 6 - Sudoku solver - Discussion

    I guess you've now spent a while reading the codes other people posted?

  29. #389
    PowerPoster
    Join Date
    Feb 2002
    Location
    Canada, Toronto
    Posts
    5,802

    Re: Contest 6 - Sudoku solver - Discussion

    Quote Originally Posted by Merri
    I guess you've now spent a while reading the codes other people posted?
    For now, only your code But I will look at the others also...

  30. #390
    Member
    Join Date
    Aug 2005
    Posts
    50

    Re: Contest 6 - Sudoku solver - Discussion

    CVMichael's and NTG's timings would be interesting for the statistics too.
    manavo, can you post ntg's timings ? they were missing
    @Brick1: the 0-line is the time needed for the easiest sudoku relative to average.
    How could you solve number 943 in 0.003 ms ?
    @xxyzzy: thanks for the .csv file ! That makes it a lot easier.
    and for the confirmation of the correlations.
    Isn't it surprising that the programs need so different times
    for special sudokus ? E.g. bpd's program is pretty fast but completely
    unrelated to others ! So, how did he solve them ? Must be some weird
    strange technique...
    the 100%-line being close to 1 does not necessarily reflect 'smartness'
    just means, that some further optimizations for some hard cases
    seem possible/promising and yes, that xyzzy's and Merri's programs
    look good also for 16*16 etc.

  31. #391
    Addicted Member
    Join Date
    Aug 2005
    Location
    York
    Posts
    197

    Re: Contest 6 - Sudoku solver - Discussion

    I've added a suggestion for the next contest http://www.vbforums.com/showthread.p...37#post2142237

  32. #392
    New Member
    Join Date
    Aug 2005
    Posts
    11

    Re: Contest 6 - Sudoku solver - Discussion

    YAY!
    means that i had the fastest single time: 027_0273 in 0,003 ms.
    Also 2nd, 3rd and 4th:
    026_0536 0,020
    024_0506 0,023
    025_0737 0,028
    where the 5th is a draw:
    MER: 024_0059 0,032
    BRI: 027_0273 0,032

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

    Re: Contest 6 - Sudoku solver - Discussion

    Quote Originally Posted by Brick1
    means that i had the fastest single time: 027_0273 in 0,003 ms.
    ...
    BRI: 027_0273 0,032
    How you can have two times for the same puzzle? Does your solver solve the same puzzle two times in a row? I get a time below 0,02 only if I try to solve the same puzzle two times in a row.

    I also noticed that my output benchmark gives me worse timings, there seems to be about 0,015 ms slow down per sudoku. This is probably due to the outputting in the middle of the timing. My code performs better if it just does nothing but solves the sudokus it is given, all in row, because it allows CPU to do better predicting. This is also why Quick benchmark gives much better total time than doing any other benchmark

    By outputting the results, I get a total time of 160 ms
    By timing individual results, I get a total time of 118 ms
    By just solving them, I get total time of 114 ms
    Last edited by Merri; Aug 29th, 2005 at 08:27 AM.

  34. #394

    Thread Starter
    Super Moderator manavo11's Avatar
    Join Date
    Nov 2002
    Location
    Around the corner from si_the_geek
    Posts
    7,171

    Re: Contest 6 - Sudoku solver - Discussion

    Quote Originally Posted by dukuso
    manavo, can you post ntg's timings ? they were missing
    ntg didn't include that feature in his entry and I didn't really want to add it myself...


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

  35. #395
    New Member
    Join Date
    Aug 2005
    Posts
    11

    Re: Contest 6 - Sudoku solver - Discussion

    sorry merri i swapped them, it should have been:

    MER: 027_0273 0,032 (which I did in 0,002)
    BRI: 024_0059 0,032 (which you did in 0,034)

    so no games solved twice.

  36. #396
    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

    Hey manavo, I tested my code in IDE and EXE and it solved all of them. Which puzzle wasn't solved when you tested it?

    @Merri: You code is insaneo. I can barely read it. Although, I am proud to say that about half way through the contest I had the idea of doing it in binary andusing Hex constants like you did. Then I realized that I barely had any idea how to do that and that I would have had to restructure my whole program. Congrats though!
    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

  37. #397

  38. #398

    Thread Starter
    Super Moderator manavo11's Avatar
    Join Date
    Nov 2002
    Location
    Around the corner from si_the_geek
    Posts
    7,171

    Re: Contest 6 - Sudoku solver - Discussion

    Quote Originally Posted by eyeRmonkey
    Hey manavo, I tested my code in IDE and EXE and it solved all of them. Which puzzle wasn't solved when you tested it?
    As Lou posted the log file is in the thread you created with your entry...

    I tried it on my desktop, same result Download the code you have uploaded and test it instead of the code on your PC?


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

  39. #399
    New Member
    Join Date
    Aug 2005
    Posts
    2

    Re: Contest 6 - Sudoku solver - Discussion

    Quote Originally Posted by dukuso
    @Brick1: the 0-line is the time needed for the easiest sudoku relative to average.
    How could you solve number 943 in 0.003 ms ?
    I have to wonder if it was some kind of error with the timer? 3 us is very fast, and the next fastest one was 20 us.
    Quote Originally Posted by dukuso
    @xxyzzy: thanks for the .csv file ! That makes it a lot easier.
    and for the confirmation of the correlations.
    Isn't it surprising that the programs need so different times
    for special sudokus ? E.g. bpd's program is pretty fast but completely
    unrelated to others ! So, how did he solve them ? Must be some weird
    strange technique...
    I'm sure you've noticed how the same sudoku turned upside down or rotated can end up taking much longer? Usually we have in a code something that goes "for Row 1 to 9 ; for column 1 to 9", etc. Maybe all there is to it, is that bpd started at row 9 and went to 1? ie. if bpd's program was fed the same samples upside down or transposed it might correlate with all the other fast programs?

    Quote Originally Posted by dukuso
    the 100%-line being close to 1 does not necessarily reflect 'smartness'
    just means, that some further optimizations for some hard cases
    seem possible/promising and yes, that xyzzy's and Merri's programs
    look good also for 16*16 etc.
    What I'm thinking is that an algorithm that's fast for SOME sudokus is easy. e.g. just fill in the missing cells at random, sometimes you get it right on the first try! Designing one that is fast for all sudokus is harder. The smarter your algorithm, the larger fraction you can do quickly. The 100% quantile isn't the best, I think 95% would be better. But I'd classify the programs, using mean speed + 95% quantile like this:

    slow speed + high quantile = naive algorithm and poor implementation
    fast speed + high quantile = simple efficient algorithm and good implementation
    slow speed + low quantile = smart but slow algorithm and/or poor implementation
    fast speed + low quantile = smart and efficient algorithm and good implementation

  40. #400
    Member
    Join Date
    Aug 2005
    Posts
    50

    Re: Contest 6 - Sudoku solver - Discussion

    xyzzy wrote:

    >dukuso wrote:
    >> E.g. bpd's program is pretty fast but completely
    >> unrelated to others ! So, how did he solve them ? Must be some weird
    >> strange technique...
    >
    >I'm sure you've noticed how the same sudoku turned upside down
    >or rotated can end up taking much longer? Usually we have in a

    yes !

    >code something that goes "for Row 1 to 9 ; for column 1 to 9",
    >etc. Maybe all there is to it, is that bpd started at row 9 and
    >went to 1? ie. if bpd's program was fed the same samples upside
    >down or transposed it might correlate with all the other fast programs?

    I examined this and posted a summary to:
    http://www.setbb.com/phpbb/viewtopic...um=sudoku#1426

    >Quote:
    >Originally Posted by dukuso
    >the 100%-line being close to 1 does not necessarily reflect 'smartness'
    >just means, that some further optimizations for some hard cases
    >seem possible/promising and yes, that xyzzy's and Merri's programs
    >look good also for 16*16 etc.
    >
    >
    >What I'm thinking is that an algorithm that's fast for SOME
    >sudokus is easy. e.g. just fill in the missing cells at random,
    >sometimes you get it right on the first try! Designing one that
    >is fast for all sudokus is harder. The smarter your algorithm,
    >the larger fraction you can do quickly.

    yes, but all the programs DID solve all the instances, so the
    average time needed should be the better measure for "smartness"

    >The 100% quantile isn't
    >the best, I think 95% would be better. But I'd classify the
    >programs, using mean speed + 95% quantile like this:
    >
    >slow speed + high quantile = naive algorithm and poor implementation
    >fast speed + high quantile = simple efficient algorithm and good implementation
    >slow speed + low quantile = smart but slow algorithm and/or poor implementation
    >fast speed + low quantile = smart and efficient algorithm and good implementation

    OK.
    "smart" assumedly means "good worst-case behaviour" here.
    This is, what usually is required in (theoretical) math, but in practice
    the average-case behaviour is often more important.

    -Guenter (dukuso)

Page 10 of 11 FirstFirst ... 7891011 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
  •  



Click Here to Expand Forum to Full Width