Page 1 of 10 1234 ... LastLast
Results 1 to 40 of 417

Thread: Contest 6 - Sudoku solver - Discussion

Hybrid View

  1. #1

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

    Contest 6 - Sudoku solver - Discussion

    This thread is to post any questions you have about the 6th contest


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

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

    Re: Contest 6 - Sudoku solver - Discussion

    Where can we find any patterns to test our progies against?
    Know of any good ones??

    no soap...radio -mendhak

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

  3. #3

    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

    Your program?

    Or www.websudoku.com


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

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

    Re: Contest 6 - Sudoku solver - Discussion

    Have you tried their evil level?
    Too bad I don'thave VBnet at home.
    Still, did you try my submission?


    -Lou
    no soap...radio -mendhak

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

  5. #5

    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

    I've tried it, my attempt at creating a solver is limited to solving some of the hard ones, so I would have to work on it more

    By submission you mean the creator/solver in the Games section?


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

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

    Re: Contest 6 - Sudoku solver - Discussion

    No.
    By submission, I meant the pattern I posted, ie...:



    Good for a speed test for all!

    no soap...radio -mendhak

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

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

    Re: Contest 6 - Sudoku solver - Discussion

    Quote Originally Posted by Something Else
    No.
    By submission, I meant the pattern I posted, ie...:



    Good for a speed test for all!

    I finished my Sudoku solver, and it works PERFECTLY, it solved ALL the puzles I gave it too...

    698217543
    412358679
    357649218
    749865321
    263174895
    581932467
    934521786
    876493152
    125786934

    Time taken: 134.911 seconds (On a P4, 1400 MHz)

    Where did you get that puzle by the way ?

    I tested my solver with puzles from here: http://www.websudoku.com/?select=1&level=4 at Evil level, and I never had one greater than 1 second to solve...

    When i pluged in your puzle I thought there is something wrong with my solver

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

    Re: Contest 6 - Sudoku solver - Discussion

    HAHA The funiest thing !!!

    I forgot to load a puzzle, the puzzle was empty, and I clicked on "Solve" button, it solved to this:

    123456789
    456789123
    789123456
    214365897
    365897214
    897214365
    531642978
    642978531
    978531642

    Time Taken: 1.62140719001996E-02 (0.0162 Seconds)

  9. #9
    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 CVMichael
    Where did you get that puzle by the way ?

    I tested my solver with puzles from here: http://www.websudoku.com/?select=1&level=4 at Evil level, and I never had one greater than 1 second to solve...

    When i pluged in your puzle I thought there is something wrong with my solver
    I made it.

    -Lou
    no soap...radio -mendhak

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

  10. #10

    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

    I'll give it a shot tomorrow Thanks for the suggestion


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

  11. #11
    I'm about to be a PowerPoster! mendhak's Avatar
    Join Date
    Feb 2002
    Location
    Ulaan Baator GooGoo: Frog
    Posts
    38,173

    Re: Contest 6 - Sudoku solver - Discussion

    Do you want us to place the timer code within our own code, or will you do that yourself?

  12. #12

    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 mendhak
    Do you want us to place the timer code within our own code, or will you do that yourself?
    Would be nice if you could include it... I know that it's VB6 but I remember you had a VB.Net version, I'll look for it. I don't have a C# one though, just thought of that


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

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

    Re: Contest 6 - Sudoku solver - Discussion

    Quote Originally Posted by manavo11
    The class located here will be used to time the entries.
    I suppose place that in our own code.

  14. #14
    type Woss is new Grumpy; wossname's Avatar
    Join Date
    Aug 2002
    Location
    #!/bin/bash
    Posts
    5,682

    Re: Contest 6 - Sudoku solver - Discussion

    Oh dear, this seems to be vague doesn't it.

    We should only have to submit a class nothing more. A class that implements an interface that is given to everyone.

    Then all the judges would have to do to test each entry is to add all the classes to one large project and then call each one in turn, that would be 100% fair then.

    The interface should have 2 methods:

    VB Code:
    1. Sub Solve(filePath as string)
    2. Sub DisplayResults()

    And thats it. All the timing code would be put into the Judge's program and not the contestants code.
    I don't live here any more.

  15. #15

    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 wossname
    We should only have to submit a class nothing more. A class that implements an interface that is given to everyone.
    Since I can't make for all of them, just make it like the prime numbers contest, a project...


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

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

    Re: Contest 6 - Sudoku solver - Discussion

    I want in !

    How do I enter the contest ?

    Or do I just post the code and that's it ?

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

    Re: Contest 6 - Sudoku solver - Discussion

    That's a good idea. Give us interfaces for each language (I don't know whether C# can implement VB.NET interfaces or vice versa) and we submit the class. However I think the timing code should maybe be placed in the class as otherwise you time calling the method as well. What do you think?

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

    Re: Contest 6 - Sudoku solver - Discussion

    You can't ask for everything; I rather code this simple thing 100% myself Especially because that way I can have the data in the format I want and I don't need to use CPU time to convert to some certain format.


    What we time when we use an interface:
    - raw data to the format programmer wants to
    - preprocessing of the data (optimizations etc.)
    - the actual algorithm
    - after processing: converting to the required format by the interface

    The very very bad thing about this is that it costs a lot of time to do the format changes; the algorithm can be superfast, yet the conversions might take time.


    Without an interface, we just would time the actual algorithm. A file loader could do the loading of data and preprocessing (ie. prepare used arrays and variables) directly to the format programmer wants. These almost always take the same amount of time no matter what kind of puzzle we have, so there is no point benchmarking these and letting them effect the results.

    I hated it in Prime Numbers contest that displaying of data was included in the benchmark... I never saw any point optimizing listbox item adding.
    Last edited by Merri; Jul 26th, 2005 at 04:45 AM.

  19. #19
    type Woss is new Grumpy; wossname's Avatar
    Join Date
    Aug 2002
    Location
    #!/bin/bash
    Posts
    5,682

    Re: Contest 6 - Sudoku solver - Discussion

    Format conversions? Its loading a file and extracting a few numbers. What hard about that?
    I don't live here any more.

  20. #20
    type Woss is new Grumpy; wossname's Avatar
    Join Date
    Aug 2002
    Location
    #!/bin/bash
    Posts
    5,682

    Re: Contest 6 - Sudoku solver - Discussion

    Load()
    'StartTimer
    Solve()
    'StopTimer
    Display()
    I don't live here any more.

  21. #21
    Fanatic Member
    Join Date
    Sep 2000
    Posts
    770

    Re: Contest 6 - Sudoku solver - Discussion

    You know what's funny?? My brother wrote one a few months ago. It works too!

  22. #22
    Fanatic Member x-ice's Avatar
    Join Date
    Mar 2004
    Location
    UK
    Posts
    671

    Re: Contest 6 - Sudoku solver - Discussion

    I cant even solve this puzzles on paper, nevermind programming a computer to do it, so i think i wont enter.

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

    Re: Contest 6 - Sudoku solver - Discussion

    Quote Originally Posted by x-ice
    I cant even solve this puzzles on paper, nevermind programming a computer to do it, so i think i wont enter.
    That's one thing I love about programming... you program what you want it to do, and it does it for you...

    If the computer took 135 seconds, then probably it will take DAYS for a person to do...
    Even the simplest one takes quite a long time.

    I did not solve any puzzle on paper. On paper it's even more difficult...
    I did solve a few puzzels on http://www.websudoku.com at easy level, but for every number i put in i clicked on "How am I doing?" button... without that button it would take a loooonnnggg time to do it...

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

    Re: Contest 6 - Sudoku solver - Discussion

    Did anyone else finish the Sudoku solver ?

    Kuz I finished, and it's working, but I'm wondering why no one posted in the submissions forum ?

    Did anyone decide how the interface will be ?

    I agree with wossname that we should submit a class...
    These are the methods I suggest to be public in the class:
    Code:
    Function SolveSudoku(Puzzle As String) As Boolean
    
    the puzzle should be a string like:
    ...8.....
    ..9....68
    .8.6.75.3
    ....2...4
    6.4...8.1
    5...3....
    8.52.3.9.
    46....2..
    .....1...
    
    And returns True if it was able to solve it
    
    Function ToString() As String
    
    That returns the solved puzzle as string like:
    356814972
    749352168
    182697543
    938126754
    624975831
    571438629
    815263497
    463789215
    297541386
    What do you think ?

    This way it is easy to plug the class in the tester application (for whoever does the testing)

  25. #25
    I'm about to be a PowerPoster! mendhak's Avatar
    Join Date
    Feb 2002
    Location
    Ulaan Baator GooGoo: Frog
    Posts
    38,173

    Re: Contest 6 - Sudoku solver - Discussion

    Are you guys taking care of the difficult sudoku problems as well? I'm sure you're aware that the higher levels involve some guessing and backtracking, how are you taking care of that? (Also, are you taking care of that?)

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

    Re: Contest 6 - Sudoku solver - Discussion

    For anyone who doesn't know it yet, you can find some sample tests HERE
    and their corresponding solutions HERE

    BTW,
    CVMichael has posted his times in THIS THREAD

    {Good Job, BTW!}


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

    Re: Contest 6 - Sudoku solver - Discussion

    Quote Originally Posted by mendhak
    Are you guys taking care of the difficult sudoku problems as well? I'm sure you're aware that the higher levels involve some guessing and backtracking, how are you taking care of that? (Also, are you taking care of that?)
    My program does not do ANY guessing at all...
    And that does not make any sence to me.... your saying I should pick the numbers randomly, and see if they are valid ? that takes an eternety to finish solving (IF it solves at all)

    My program is a recursive function (and some small functions), together is 158 lines (only the solver part, no loading and saving...)

  28. #28
    I'm about to be a PowerPoster! mendhak's Avatar
    Join Date
    Feb 2002
    Location
    Ulaan Baator GooGoo: Frog
    Posts
    38,173

    Re: Contest 6 - Sudoku solver - Discussion

    Quote Originally Posted by CVMichael
    My program does not do ANY guessing at all...
    And that does not make any sence to me.... your saying I should pick the numbers randomly, and see if they are valid ? that takes an eternety to finish solving (IF it solves at all)

    My program is a recursive function (and some small functions), together is 158 lines (only the solver part, no loading and saving...)
    That's interesting how you got it solved then, because I believe that the toughest sudoku puzzles cannot be solved simply by logic, but involve guessing and backtracking...

    Or maybe you should hope that I've got my facts wrong.

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

    Re: Contest 6 - Sudoku solver - Discussion

    What he does IS guessing. He described in the other topic that he tries a number and then sees if it is valid.

    Guessing is also known as brute force.

  30. #30
    Super Moderator
    Join Date
    Dec 2003
    Posts
    4,787

    Re: Contest 6 - Sudoku solver - Discussion

    http://www.vbforums.com/showthread.p...27#post2102227

    test your apps, thanks to NotLkh, our local maths expert.

    Pino

  31. #31
    I'm about to be a PowerPoster! mendhak's Avatar
    Join Date
    Feb 2002
    Location
    Ulaan Baator GooGoo: Frog
    Posts
    38,173

    Re: Contest 6 - Sudoku solver - Discussion

    I guess his definition of guessing is different.

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

    Re: Contest 6 - Sudoku solver - Discussion

    Quote Originally Posted by mendhak
    I guess his definition of guessing is different.
    I guess so...

    But the numbers I try are not random, I make a list of available numbers (that are not used horizontally and vertically, then I try those numbers...

  33. #33
    I'm about to be a PowerPoster! mendhak's Avatar
    Join Date
    Feb 2002
    Location
    Ulaan Baator GooGoo: Frog
    Posts
    38,173

    Re: Contest 6 - Sudoku solver - Discussion

    Guys, please try this sudoku puzzle as well:

    Code:
    ..9..5...
    47...2...
    .836.4.1.
    .15....8.
    ...3.7...
    .2....74.
    .4.5.187.
    ...7...52
    ...2..1..

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

    Re: Contest 6 - Sudoku solver - Discussion

    Quote Originally Posted by mendhak
    Guys, please try this sudoku puzzle as well:

    Code:
    ..9..5...
    47...2...
    .836.4.1.
    .15....8.
    ...3.7...
    .2....74.
    .4.5.187.
    ...7...52
    ...2..1..
    269175438
    471832965
    583694217
    715426389
    894317526
    326958741
    942561873
    138749652
    657283194

    Solved in 0.0339 seconds... (In the IDE), in 675 iterations...

  35. #35
    I'm about to be a PowerPoster! mendhak's Avatar
    Join Date
    Feb 2002
    Location
    Ulaan Baator GooGoo: Frog
    Posts
    38,173

    Re: Contest 6 - Sudoku solver - Discussion

    Quote Originally Posted by CVMichael
    269175438
    471832965
    583694217
    715426389
    894317526
    326958741
    942561873
    138749652
    657283194

    Solved in 0.0339 seconds... (In the IDE), in 675 iterations...
    I'm impressed.

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

    Re: Contest 6 - Sudoku solver - Discussion

    I'm a bit confused about what the judges expect me to submit. Is it just the solver class/module or is it a full application that loops through sudokus, solves them, times it and displays the result and time used? Should I write the solution back to the original sudoku files or just display it on the screen? Should I write the timing results to a log file or to a listbox on the form?

    I'm confused

    Please clarify.

  37. #37

    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 kaffenils
    I'm a bit confused about what the judges expect me to submit. Is it just the solver class/module or is it a full application that loops through sudokus, solves them, times it and displays the result and time used? Should I write the solution back to the original sudoku files or just display it on the screen? Should I write the timing results to a log file or to a listbox on the form?

    I'm confused

    Please clarify.
    Create a project (not just a class) that solves sudokus. In there it would be nice for us if you included the timing code as well, if you want. And it's probalby for the best for you to have a loading sub to read files like we show in the description thread of the contest.


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

  38. #38
    Hyperactive Member
    Join Date
    Jul 2005
    Posts
    297

    Re: Contest 6 - Sudoku solver - Discussion

    Hmm, I've already got one on planetsourcecode. No stealing lol. Actually the brute force method I added was converted from someone elses C code, but the rules based solver is my own work.
    for this grid mentioned above:

    ..9..5...
    47...2...
    .836.4.1.
    .15....8.
    ...3.7...
    .2....74.
    .4.5.187.
    ...7...52
    ...2..1..

    rules solver does it in about 700ms (I've not done an average of a few runs).
    brute forced in 7 ms (athlon fx55 though...)
    The rules based solver is definately NOT optimised for speed. I'd have to start from scratch to optimise it.

    Rules based solving tries to solve more like a human. You start will all squares being able to be any number 1-9, then eliminate possibilities based on rules, such as "if a number is known for sure in a square, then eliminate it as a possibility from all squares in its row, column and block...". You then churn through the rules repeatedly until it is (hopefully) solved.
    Brute force will make guesses and check if the grid is valid, if it is invalid then it will go back to a saved state and guess again. There is a sudoku programmers forum with lots of discussion on rules based solving.

    timing code:
    Code:
    Dim starttime, endtime As Date
    Dim elapsedtime As TimeSpan
    starttime = Now
    ----Call solving sub----
    endtime = Now
    elapsedtime = endtime.Subtract(starttime)
    Dim millisecs As Long = elapsedtime.Milliseconds
    Last edited by jo0ls; Jul 31st, 2005 at 04:05 PM.

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

    Re: Contest 6 - Sudoku solver - Discussion

    Actually, for me it's the other way around, the rules solver is the fastest, under a millisecond, and the brute force one takes the longest up to 6-7 seconds...

  40. #40
    Frenzied Member ntg's Avatar
    Join Date
    Sep 2004
    Posts
    1,449

    Re: Contest 6 - Sudoku solver - Discussion

    What's the timing class to be used for VB.Net?

    The problem:
    Code:
    ..9..5...
    47...2...
    .836.4.1.
    .15....8.
    ...3.7...
    .2....74.
    .4.5.187.
    ...7...52
    ...2..1..
    is solved pretty quickly. How are you guys doing on other problems like this one:
    Code:
    .........
    9.....1.7
    ...718...
    2........
    ..5.8...3
    ..6.49.18
    .18......
    .6..3..74
    ...9...3.
    "Feel the force...read the source..."
    Utilities: POPFileDebugViewProcess ExplorerWiresharkKeePassUltraVNCPic2Ascii
    .Net tools & open source: DotNetNukelog4NetCLRProfiler
    My open source projects: Thales SimulatorEFT CalculatorSystem Info ReporterVSS2SVNIBAN 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"

Page 1 of 10 1234 ... 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