Contest 6 - Sudoku solver - Discussion - Page 4-VBForums
Page 4 of 11 FirstFirst 1234567 ... LastLast
Results 121 to 160 of 417

Thread: Contest 6 - Sudoku solver - Discussion

  1. #121
    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

    Merri,

    I have to say, you motivate me to give up because I know you are going to win (well, at least beat me). Not really, but your "VB speed guru" title fits you well. I have been reading your posts in "Code It Better" and its crazy how fast your program is. Mine solves 10 in the time yours solves 300.

    I decided I will just get it to solve all the puzzels and I will be happy. I will keep speed in mind as I code it, but not worry too much about it. Then when I am done I will play around with things to see what is fastest.
    Last edited by eyeRmonkey; Aug 9th, 2005 at 07:06 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

  2. #122

    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

    Keep trying At the end, it will be more fun to look at Merri's code and see what he did differently if you have tried it yourself


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

  3. #123
    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 totally agree. This is all a great learning experience for me anyway because I have only been into VB6 for a little over a month.
    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. #124

    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

    Then I'll just keep on encouraging you The more people participate the better


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

  5. #125
    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'm working on it. At the moment it can only solve the most basic ones, but I am working on adding a couple other logic rules to it.

    I'm kinda worried about adding back-tracking, because I think it will slow down my program a ton, but it sounds like it is necessary for the harder ones.
    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

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

    Re: Contest 6 - Sudoku solver - Discussion

    There is going to be a personal history lesson. If you're not up to it, skip the following paragraph. For the others... enjoy the fun.

    Yeah, it is always better to first make it work and then start optimizing it. Of course the level of optimization I started with was pretty high, I have much more previous experience I've been using VB since late 1997 and a basic language since ~1990 (when I were about six years old). Though I've "only" been getting into speed optimization for about two years now, ever since bothering another guru and trying to match up with him in speed... I lost as he had done a code a couple of years before which he has proven to be the fastest possible in VB6, but I got very close when I tried all kinds of approaches. I also found out "The Secret to Speed".

    Anyways... it is pretty hard as I know my code still isn't the fastest out there (mostly due to my "poor" backtracker) yet my code seems to be much faster than other participants. I still think there are probably some people who just lurk behind the scenes and will submit a superb code. My approach might also lose if tested under the IDE, because targetting speed for IDE is much different from targetting speed for a compiled EXE.

    My code will be fully commented for everyone's viewing pleasure And also, I don't know how much it is worth to win the contest anyways... it didn't really destroy my life to take part in the Prime Numbers contest last year and only lose due to the slow speed of listbox adding which I didn't optimize at all (the only trick I did was to hide the listbox when adding items). Of course I'm angry about the silliness of it as I can't understand why we should optimize a listbox adding in a prime numbers contest. Atleast this time I'll lose due to bad code.


    This is getting long... maybe I should write more?

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

    Re: Contest 6 - Sudoku solver - Discussion

    Okay... I have just made something I'm pretty happy with. Due to that I won't be saying my times anymore, mostly to make it harder for the possible lurkers to see where I am going. I also might be just bluffing...


    Edit
    Here are the hardest three puzzles I've found this far:

    Code:
    67....3..
    .4.....8.
    ....1....
    ...8..1.5
    .2.4.....
    ......6..
    ...7...2.
    5...6....
    1........
    Code:
    .86......
    ....5..1.
    ...4...3.
    5..3...4.
    .7....2..
    ...1.....
    .....86.7
    3........
    ......8..
    Code:
    3...8....
    ...7....5
    1........
    ......36.
    ..2..4...
    .7.......
    ....6.13.
    .452.....
    ......8..
    These are pain for me. They take almost 500 times longer to solve than the easiest I have.
    Last edited by Merri; Aug 10th, 2005 at 12:00 PM.

  8. #128
    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

    Thanks, I had been wondering what the hardest ones are (not that I'm close to being able to solve them). I'm guessing they take a lot of backtracking if yours takes a lot of time.

    From what I have read (and the code I have made) it seems to me that optimized code tends to be very hard to read. I hope your comments are really good.

    I'm up for hearing a continuation of that long post.
    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

  9. #129
    Frenzied Member ntg's Avatar
    Join Date
    Sep 2004
    Posts
    1,448

    Re: Contest 6 - Sudoku solver - Discussion

    OK, for all the lurkers out there:

    NotLKH1, 69 files, ~30ms
    NotLKH2, 532 files, ~270ms
    NotLKH3, 123 files, ~80ms
    Hardest, 337 files, ~745ms

    Using VB.Net, P4@3,2Ghz. I still can't get the fastest solution below 0,2 ms no matter what I do. There are still improvements that can be made though.
    "Feel the force...read the source..."
    Utilities: POPFile DebugView Process Explorer Wireshark KeePass UltraVNC Pic2Ascii
    .Net tools & open source: DotNetNuke log4Net CLRProfiler
    My open source projects: Thales Simulator EFT Calculator System Info Reporter VSS2SVN IBAN Functions
    Customer quote: "If the server has a RAID array, why should we bother with backups?"
    Programmer quote: "I never comment my code. Something that is hard to write should be impossible to comprehend."
    Ignorant quote: "I have no respect for universities, as they teach not practicle stuff, and charge money for"

  10. #130
    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

    By the way are we going to be given puzzels with non-unique solutions? I know our solver has to be able to solve all puzzles to have a shot at winning, so does that include non-unique ones/ones that need to be brute-forced?
    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

  11. #131

    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

    No... I thought that was established that those aren't true sudokus or something Anyway, it doesn't seem fair to have those since it's kind of a matter of luck then, right?


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

  12. #132
    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

    True, it would be more like luck.

    Sorry, you might have established it earlier, I probably missed it. Thanks for clearing it up.
    Last edited by eyeRmonkey; Aug 10th, 2005 at 07:29 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

  13. #133

    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 don't think I did explicitely mention it but when Lou said they aren't true sudokus I assumed it's obvious that we won't test them (in other words I'm lazy)


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

  14. #134
    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 manavo11
    I don't think I did explicitely mention it but when Lou said they aren't true sudokus I assumed it's obvious that we won't test them (in other words I'm lazy)

    Got a link?



    -Lou
    no soap...radio -mendhak

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

  15. #135

    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

    No?

    Maybe it wasn't you? I remember someone saying that And there are 3 threads going on (Games section, Contest Section and Chit Chat)... In one of them someone said that


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

  16. #136

    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

    Close, someone was asking you but wikipedia answered

    http://www.vbforums.com/showpost.php...2&postcount=89


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

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

    Re: Contest 6 - Sudoku solver - Discussion

    I've been concerned that I might be making multi-solution puzzles.

    I thought you were saying I said they weren't true sudoku's, "they" meaning my submissions.


    Thanks for the clarification!


    -Lou
    no soap...radio -mendhak

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

  18. #138

    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

    Oh no no no! Your submissions are just fine as the testers have proven Sorry for the mixup


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

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

    Re: Contest 6 - Sudoku solver - Discussion

    Quote Originally Posted by Merri
    yet my code seems to be much faster than other participants.
    I haven't had time to code much lately since I am on holiday, but these are my temporary results. I still have some good ideas on how to optimize even further, so my guess is that the "long" running sudokus will be much much faster. Keep in mind that the results are from a P3 700 Mhz. You still beat me on the hardest sudokus.

    My results (in milliseconds):
    Code:
    Total time: 1751,659219
    wossname.txt solved. Time used 3,042565
    wallyb.txt solved. Time used 148,997708
    veryeasy.txt solved. Time used 0,163429
    tomker.txt solved. Time used 290,79478
    supertough1.txt solved. Time used 303,626299
    sudoku3.txt solved. Time used 2,412876
    sudoku2.txt solved. Time used 0,58974
    sudoku1.txt solved. Time used 0,148902
    dukuso3.txt solved. Time used 303,340508
    dukuso2.txt solved. Time used 215,274567
    dukuso1.txt solved. Time used 291,233662
    0068_0003_023.msk solved. Time used 0,52381
    0067_0000_023.msk solved. Time used 0,34781
    0066_0000_023.msk solved. Time used 0,324064
    0065_0001_023.msk solved. Time used 0,481625
    0064_0001_023.msk solved. Time used 0,486654
    0063_0003_023.msk solved. Time used 0,630527
    0062_0003_023.msk solved. Time used 0,482743
    0061_0000_023.msk solved. Time used 0,334121
    0060_0001_023.msk solved. Time used 0,442235
    0059_0001_023.msk solved. Time used 0,438045
    0058_0000_023.msk solved. Time used 0,285511
    0057_0003_023.msk solved. Time used 0,412064
    0056_0003_023.msk solved. Time used 0,509562
    0055_0000_023.msk solved. Time used 0,308698
    0054_0003_023.msk solved. Time used 0,492241
    0053_0001_023.msk solved. Time used 0,415695
    0052_0003_023.msk solved. Time used 0,449219
    0051_0001_023.msk solved. Time used 0,488889
    0050_0003_023.msk solved. Time used 0,441676
    0049_0001_023.msk solved. Time used 3,240635
    0048_0001_023.msk solved. Time used 0,423238
    0047_0003_023.msk solved. Time used 0,617676
    0046_0003_023.msk solved. Time used 0,400889
    0045_0000_023.msk solved. Time used 0,275175
    0044_0001_023.msk solved. Time used 0,496432
    0043_0000_023.msk solved. Time used 0,297244
    0042_0003_023.msk solved. Time used 0,805968
    0041_0000_023.msk solved. Time used 0,267073
    0040_0003_023.msk solved. Time used 0,585549
    0039_0003_023.msk solved. Time used 122,883774
    0038_0001_023.msk solved. Time used 0,485816
    0037_0003_023.msk solved. Time used 0,450616
    0036_0001_023.msk solved. Time used 0,427987
    0035_0003_023.msk solved. Time used 0,376305
    0034_0001_023.msk solved. Time used 0,622146
    0033_0003_023.msk solved. Time used 0,587505
    0032_0003_023.msk solved. Time used 0,398375
    0031_0003_023.msk solved. Time used 0,393625
    0030_0003_023.msk solved. Time used 2,606756
    0029_0003_023.msk solved. Time used 0,625219
    0028_0000_023.msk solved. Time used 0,295848
    0027_0001_023.msk solved. Time used 0,488051
    0026_0001_023.msk solved. Time used 0,381613
    0025_0003_023.msk solved. Time used 5,461588
    0024_0001_023.msk solved. Time used 0,584432
    0023_0003_023.msk solved. Time used 0,545321
    0022_0003_023.msk solved. Time used 1,501867
    0021_0000_023.msk solved. Time used 0,298362
    0020_0001_023.msk solved. Time used 0,389156
    0019_0001_023.msk solved. Time used 0,412902
    0018_0001_023.msk solved. Time used 0,415137
    0017_0003_023.msk solved. Time used 20,805717
    0016_0003_023.msk solved. Time used 2,196369
    0015_0003_023.msk solved. Time used 0,657905
    0014_0001_023.msk solved. Time used 0,587505
    0013_0003_023.msk solved. Time used 0,437206
    0012_0001_023.msk solved. Time used 0,472406
    0011_0001_023.msk solved. Time used 0,452013
    0010_0003_023.msk solved. Time used 0,500902
    0009_0001_023.msk solved. Time used 0,500064
    0008_0003_023.msk solved. Time used 0,591695
    0007_0001_023.msk solved. Time used 0,390832
    0006_0003_023.msk solved. Time used 0,489448
    0005_0003_022.msk solved. Time used 0,641702
    0004_0001_022.msk solved. Time used 4,991975
    0003_0003_022.msk solved. Time used 0,561803
    0002_0003_022.msk solved. Time used 0,402844
    0001_0001_022.msk solved. Time used 0,499225
    0000_0001_022.txt solved. Time used 0,517105
    Results from Merri's solver:
    Code:
    Benchmarking...
    0,067048 ms:	0000_0001_022.txt
    3,535645 ms:	0001_0001_022.msk
    0,091632 ms:	0002_0003_022.msk
    0,949003 ms:	0003_0003_022.msk
    2,662350 ms:	0004_0001_022.msk
    1,850235 ms:	0005_0003_022.msk
    0,160356 ms:	0006_0003_023.msk
    0,081854 ms:	0007_0001_023.msk
    2,838350 ms:	0008_0003_023.msk
    0,076546 ms:	0009_0001_023.msk
    0,084927 ms:	0010_0003_023.msk
    0,202819 ms:	0011_0001_023.msk
    0,140241 ms:	0012_0001_023.msk
    0,278806 ms:	0013_0003_023.msk
    19,585171 ms:	0014_0001_023.msk
    0,092190 ms:	0015_0003_023.msk
    50,603918 ms:	0016_0003_023.msk
    7,015417 ms:	0017_0003_023.msk
    0,114260 ms:	0018_0001_023.msk
    0,106438 ms:	0019_0001_023.msk
    1,356318 ms:	0020_0001_023.msk
    0,065092 ms:	0021_0000_023.msk
    6,493004 ms:	0022_0003_023.msk
    0,800102 ms:	0023_0003_023.msk
    2,845334 ms:	0024_0001_023.msk
    2,192178 ms:	0025_0003_023.msk
    0,071517 ms:	0026_0001_023.msk
    0,132140 ms:	0027_0001_023.msk
    0,063695 ms:	0028_0000_023.msk
    5,990706 ms:	0029_0003_023.msk
    12,262452 ms:	0030_0003_023.msk
    0,159797 ms:	0031_0003_023.msk
    0,112305 ms:	0032_0003_023.msk
    0,270984 ms:	0033_0003_023.msk
    0,076546 ms:	0034_0001_023.msk
    0,150019 ms:	0035_0003_023.msk
    4,640813 ms:	0036_0001_023.msk
    0,070121 ms:	0037_0003_023.msk
    0,205892 ms:	0038_0001_023.msk
    12,765589 ms:	0039_0003_023.msk
    0,129346 ms:	0040_0003_023.msk
    0,065092 ms:	0041_0000_023.msk
    0,238578 ms:	0042_0003_023.msk
    0,063695 ms:	0043_0000_023.msk
    0,124597 ms:	0044_0001_023.msk
    0,063416 ms:	0045_0000_023.msk
    4,159467 ms:	0046_0003_023.msk
    0,208406 ms:	0047_0003_023.msk
    0,163429 ms:	0048_0001_023.msk
    5,038070 ms:	0049_0001_023.msk
    0,151137 ms:	0050_0003_023.msk
    0,070679 ms:	0051_0001_023.msk
    0,936152 ms:	0052_0003_023.msk
    0,113981 ms:	0053_0001_023.msk
    0,144990 ms:	0054_0003_023.msk
    0,065371 ms:	0055_0000_023.msk
    2,688051 ms:	0056_0003_023.msk
    0,122641 ms:	0057_0003_023.msk
    0,068724 ms:	0058_0000_023.msk
    0,073473 ms:	0059_0001_023.msk
    0,104203 ms:	0060_0001_023.msk
    0,067606 ms:	0061_0000_023.msk
    0,118171 ms:	0062_0003_023.msk
    0,218464 ms:	0063_0003_023.msk
    2,054451 ms:	0064_0001_023.msk
    0,212038 ms:	0065_0001_023.msk
    0,066489 ms:	0066_0000_023.msk
    0,081016 ms:	0067_0000_023.msk
    0,222933 ms:	0068_0003_023.msk
    353,006318 ms:	dukuso1.txt
    104,280013 ms:	dukuso2.txt
    38,606583 ms:	dukuso3.txt
    0,069841 ms:	sudoku1.txt
    0,169575 ms:	sudoku2.txt
    5,610210 ms:	sudoku3.txt
    42,242799 ms:	supertough1.txt
    348,630901 ms:	tomker.txt
    0,077943 ms:	veryeasy.txt
    64,338065 ms:	wallyb.txt
    5,631163 ms:	wossname.txt
    Total time for 80 files: 1121,759888 milliseconds

  20. #140
    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 was wondering who will be doing the marking of the entries? I need to know if the person who scores them will have windows XP so I know if I can use the rtlcomparememory API in my program.
    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

  21. #141
    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

    /rant on
    GRRRRRRR! Ruff!

    Ok, Merri, so you talked me into (without knowing it) making my puzzle 1-D. I spent like 5 hours figuring out how to change everything to 1-D and after I was done... I found out that it takes 3 times as long to solve a puzzle now.

    I think it has something to do with the way I eliminate possiblities from each group. I thought I had the most efficient forumla I could think of, but maybe VB does math too slow or something.

    SHMA!!

    Maybe its also because the solver isnt done and all the logic rules aren't in place. If all the rules were there maybe I would find a 1-D array to be faster, but I doubt it. 3 times as slow for a very simple puzzle.

    /rant off
    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

  22. #142
    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

    Woooot. Sorry for triple posting. But I finally got my solver to do something other than solve this:
    .695.78.1
    5.2.83.4.
    31.694...
    .37.65.8.
    284731.96
    956.483.7
    8.14569.3
    793.1.46.
    6.53.91..

    Which I had to make by taking a solution and removing a few parts. The crappy thing is that it takes 4 - 5 ms per puzzle where as other peoples solve in under 1 ms. I'll be happy if I can get it to solve everything though. YAY!
    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

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

    Re: Contest 6 - Sudoku solver - Discussion

    When you change a puzzle to 1D, you have to make sure you don't keep doing too much calculations. For example:

    VB Code:
    1. For Y = 0 To 8
    2.     For X = 0 To 8
    3.         Board(Y * 9 + X) = Y
    4.     Next X
    5. Next Y

    Is remarkably slower when compared to:
    VB Code:
    1. YX = 0
    2. For Y = 0 To 8
    3.     For X = 0 To 8
    4.         Board(YX + X) = Y
    5.     Next X
    6.     YX = YX + 9
    7. Next Y

    This only one of the hundreds of tricks to speed up code As you can see, the code gets longer and consumes more memory when it is faster, but it is basically doing the same thing. You just try to calculate less yet doing the same thing you were doing before.


    Edit Also, zero based arrays are much faster in VB6 than other bases.
    Last edited by Merri; Aug 12th, 2005 at 12:29 AM.

  24. #144
    Member
    Join Date
    Aug 2005
    Posts
    50

    Re: Contest 6 - Sudoku solver - Discussion

    how about board[(y<<4)+x]=y ?
    that's how I would avoid multiplication by 9 in C

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

    Re: Contest 6 - Sudoku solver - Discussion

    There is no bitshifting operator in VB6. Though I'd still use a temporary variable to hold the result of Y<<4 if I were optimizing C for speed

  26. #146
    Member
    Join Date
    Aug 2005
    Posts
    50

    Re: Contest 6 - Sudoku solver - Discussion

    I just tried to estimate how much time I lose due to 2-dim arrays : about 3%.

  27. #147
    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 Merri
    When you change a puzzle to 1D, you have to make sure you don't keep doing too much calculations. For example:

    VB Code:
    1. For Y = 0 To 8
    2.     For X = 0 To 8
    3.         Board(Y * 9 + X) = Y
    4.     Next X
    5. Next Y

    Is remarkably slower when compared to:
    VB Code:
    1. YX = 0
    2. For Y = 0 To 8
    3.     For X = 0 To 8
    4.         Board(YX + X) = Y
    5.     Next X
    6.     YX = YX + 9
    7. Next Y

    This only one of the hundreds of tricks to speed up code As you can see, the code gets longer and consumes more memory when it is faster, but it is basically doing the same thing. You just try to calculate less yet doing the same thing you were doing before.
    No I had been doing something like this:
    VB Code:
    1. For i = 1 to 81
    2.    ' Do stuff
    3. Next i
    4.  
    5. And then when I needed to get the row and column I would use integer division and a few other calculations. Doing it this way made groups really hard. The way you mentioned is a lot easier. I will try that later. Thanks. :)

    Quote Originally Posted by Merri
    Edit Also, zero based arrays are much faster in VB6 than other bases.
    NOW YOU TELL ME!!! I had been using Option Base 1 to make things make sense in my head. More work to do now I guess.
    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

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

    Re: Contest 6 - Sudoku solver - Discussion

    Quote Originally Posted by eyeRmonkey
    And then when I needed to get the row and column I would use integer division and a few other calculations. Doing it this way made groups really hard. The way you mentioned is a lot easier. I will try that later. Thanks.
    You could also create a 2dimensional map array, ie.. Dim CELL_TO_ROW_COL( 80, 1) as integer,

    and, when you need to use the col and row coordinate for cell N, you just reference CELL_TO_ROW_COL( 80, 0) & CELL_TO_ROW_COL( 80, 1).

    I've been revamping my version up to not use columns or rows whatsoever.
    Just intermappings between:

    1. the 81 cells and the 27 groups
    2. the 9 3x3 Groups with the 18 row and column groups.


    Whats your opinion on this theoretical setup?


    -Lou

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

    Re: Contest 6 - Sudoku solver - Discussion

    Hehe, I tell a lot it seems Zero based arrays are easier for the computer and they start to make more sense once you get the idea. Oh well, I give you a tip for more optimization: make arrays that hold all the stuff you need to calculate over and over again (X and Y positions, square index...).

  30. #150
    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 NotLKH
    You could also create a 2dimensional map array, ie.. Dim CELL_TO_ROW_COL( 80, 1) as integer,

    and, when you need to use the col and row coordinate for cell N, you just reference CELL_TO_ROW_COL( 80, 0) & CELL_TO_ROW_COL( 80, 1).

    I've been revamping my version up to not use columns or rows whatsoever.
    Just intermappings between:

    1. the 81 cells and the 27 groups
    2. the 9 3x3 Groups with the 18 row and column groups.


    Whats your opinion on this theoretical setup?


    -Lou
    Not quite sure what you mean. Do you keep track of everything twice of what? Do you have 81 cells 2 times?
    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

  31. #151
    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 Merri
    ... I give you a tip for more optimization: make arrays that hold all the stuff you need to calculate over and over again (X and Y positions, square index...).
    I thought of this back when I was still planning on not entering the contest and was going over it in my head. I don't know why I never applied it.

    Any more tips? *nudge nudge*

    EDIT: I have been using a UDT to hold the Row and Col (X and Y). Is that slower than a normal variable because of the fact that using a dot is always slower than not? Or does that dot thing not apply?
    Last edited by eyeRmonkey; Aug 12th, 2005 at 11:08 AM.
    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

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

    Re: Contest 6 - Sudoku solver - Discussion

    Do you think the requirements should be tweaked a bit?
    It seems that many of you can handle processing directories of submissions en masse.

    For the contest, it would seem like it'd be easier to judge if the progie, upon clicking "Start", that it should query for a source directory, whereby all the .msk files reside that need to be solved.

    As each one is solved, the solution you've generated would be outputted to a directory parrallel to the source directory, generated by you, and recognizably named after your username. Also, once solved, a timing file is created, with the time you've detected it took to solve a submission.

    An option control would also be resident on your form, to toggle between "Silent" mode, and "Visual" mode {ie.. just outputing to screen your solutions, as you solve them.}

    Thus, as the judges run each entrant, all they have to do is build a compiler to return the results of ALL the entrants, plus it would also compare the entrants solutions against the "official" .sol file.

    This way, you could place any optimizations into the form_load event that you want, that don't need to ever be regenerated when you do mass processing.

    -Lou

  33. #153
    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 like that idea, but it is probably up to manavo for the final decision.

    I was also wondering if we could get a final say-so as to wether the judges will be testing compiled code or in the IDE? It would just make me feel more confident in what I am testing. If they do it compiled I would assume most optimizations would be on? Of course that could cause some programs to crash, but if they did crash, then they probably wouldn't have won anyway? Can give word on this subject manavo?
    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

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

    Re: Contest 6 - Sudoku solver - Discussion

    NotLKH: I don't like the idea as such, I want some freedom to the design. So cleaned up:

    - there must be an option to pick a folder with the sudokus
    - the folder files must be easy to benchmark
    - the timing results must be outputted so that they're viewable by the user
    - the solutions should be outputted into a user configurable directory if the user wants

    I don't want to create a separate "silent" mode. I have added some visual candy so that it is easier for a human to check if the results are valid... though these are just nice extra. But the above mentioned changes/requirements should be enough?


    Also, I do optimizations when a file is loaded the first time. My module is 100% independent from the actual program.

  35. #155
    pathfinder NotLKH's Avatar
    Join Date
    Apr 2001
    Posts
    2,397

    Re: Contest 6 - Sudoku solver - Discussion

    Well, I don't disagree with what you've suggested,
    however, the timings should also not only be viewable, but also outted to a data file.

    That way the judges won't have to manually tabulate the results, especially if they use the number of puzzles I can potentially provide.

    The "Silent" mode is just a streamlining, so that the judges don't have to put up with screen outputs & updates.

    And, your suggestion to be able to "Pick" a folder, well, again, all well and good. But Pasting the path is what I'd prefer, or even Drag and Drop, if I was forced to run/judge the entrents.

    What you're making is a good distributable app to a generic user, and it sounds great. I was thinking about what would make it a better program for the intents of this contest, and that would be quick access to the source directory with as few human required input events as possible, and standard outputting of the data that needs to be judged, standard such that a judge could programically analyze the results, without having to do much of anything by eye and hand.


    -Lou

  36. #156
    Frenzied Member ntg's Avatar
    Join Date
    Sep 2004
    Posts
    1,448

    Re: Contest 6 - Sudoku solver - Discussion

    Hey lurkers:
    NotLKH1, 69 files, ~26ms
    NotLKH2, 532 files, ~233ms
    NotLKH3, 123 files, ~68ms
    Hardest, 337 files, ~648ms

    I've been reading what you guys are discussing about optimizing array access, precalculating things and stuff like that. Personally, I won't do any more relevant optimizations because it's going to take the fun out of it, plus the code is already beginning to look like primo gusto macaroni to me. The sole code optimizations I did was to minimize method calls and substitute my original class design in favor of an array approach (although anyone who would read the class implementation would understand it in about 5 seconds - instead the current implementation would take considerably more time to comprehend and I really hate that). I think that major speed gains can be realized by improving the algorithmic approach to the solution of this instead of focusing on pure code optimization. Merri and dukuso in particular who already have very fast implementations for simple puzzles would drive everybody to the ground with a good backtracking algo.
    "Feel the force...read the source..."
    Utilities: POPFile DebugView Process Explorer Wireshark KeePass UltraVNC Pic2Ascii
    .Net tools & open source: DotNetNuke log4Net CLRProfiler
    My open source projects: Thales Simulator EFT Calculator System Info Reporter VSS2SVN IBAN Functions
    Customer quote: "If the server has a RAID array, why should we bother with backups?"
    Programmer quote: "I never comment my code. Something that is hard to write should be impossible to comprehend."
    Ignorant quote: "I have no respect for universities, as they teach not practicle stuff, and charge money for"

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

    Re: Contest 6 - Sudoku solver - Discussion

    Before, pretty much all I did was a combination of algorithm and code optimization as much as I could with the backtracker code I had. Since then I have coded a whole new backtracker with code optimization only. I don't dare say more... Or well, I say one timing: NotLKH1 in ~5.1 ms.
    Last edited by Merri; Aug 12th, 2005 at 12:37 PM.

  38. #158
    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 Merri
    Before, pretty much all I did was a combination of algorithm and code optimization as much as I could with the backtracker code I had. Since then I have coded a whole new backtracker with code optimization only. I don't dare say more... Or well, I say one timing: NotLKH1 in ~5.1 ms.
    *stabs Merri in the hear and ran widly around holding a disk with his code on it over my head*
    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

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

    Re: Contest 6 - Sudoku solver - Discussion

    *sniff* Now my hear is broken :/ Good thing I can always do a recode!

    Edit Oh... and make it ~4.7 ms... this is getting scary.
    Last edited by Merri; Aug 12th, 2005 at 01:25 PM.

  40. #160
    Member
    Join Date
    Aug 2005
    Posts
    50

    Re: Contest 6 - Sudoku solver - Discussion

    put all sudokus in one file, one row per sudoku

Page 4 of 11 FirstFirst 1234567 ... 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.