Contest: Write the quickest Sudoku solver and win 500$

Discussion in 'Android Questions' started by Erel, Sep 6, 2011.

  1. Erel

    Erel Administrator Staff Member Licensed User

    The challenge is to write the fastest Sudoku solver.
    A prize of 500$ will be given to the author of the quickest solver (which should also solve correctly...).

    This contest is open for both licensed users and users who are using the trial version.
    To make it a fair contest, no libraries are allowed.

    The due date is October 1st. You should export your project and sent it to me: erel@basic4ppc.com.
    The prize will be paid with PayPal.

    We will run the tests. Note that you can send your projects multiple times and also before the date. I will post the current best result in the forum (without the code).

    The project attached should be used as a skeleton for your application.
    You can modify the code as needed but Sub Activity_Resume must be kept exactly as it is:
    Code:
    Dim puzzles As List
       puzzles = 
    File.ReadList(File.DirAssets, "data.txt")
       
    Dim results As List
       results = 
    File.ReadList(File.DirAssets, "answer.txt")
       
    Dim t As Long
       t = 
    DateTime.Now
       
    For i = 0 To puzzles.Size - 1
          
    Dim ans As String
          ans = SolveSudoku(puzzles.Get(i)) 
    'This is your part...
          If ans <> results.Get(i) Then
             
    Log("Wrong answer!!!")
             
    Log("Expected: " & results.Get(i))
             
    Log("Result: " & ans)
          
    End If
       
    Next
       
    Log(Round((DateTime.Now - t) / puzzles.Size ) & "ms (per puzzle)")
    Cheating is not allowed!
    The project includes two sample files. Data.txt holds the puzzles and answer.txt holds the answers. The example project shows how you can read the puzzle and what is the expected result.
    Puzzles have a single solution.
    Your application will be tested with a different set of puzzles.
    Feel free to post any question.

    Tip: Disable the debugger when you measure the performance of your solver.

    Boten currently leads the contest with an impressive result of 86ms per puzzle!
    Note that these results are not final. The real tests will be done with a different and larger set of puzzles.
     

    Attached Files:

  2. hackhack

    hackhack Active Member Licensed User

    Right, I'm confused already, so I'll just applaud the winner from the sidelines :)
     
  3. thedesolatesoul

    thedesolatesoul Expert Licensed User

    Wont the time be dependent on the device you test it on?
    ...so basically 270 ms doesnt mean anything to me (for now) :)

    EDIT: If the Threading library was allowed, I would kick off a thread for each permutation...now THAT should be fast :)
     
  4. hackhack

    hackhack Active Member Licensed User

    Perhaps they'll test it on the emulator (on Erels machine :)
     
  5. Erel

    Erel Administrator Staff Member Licensed User

    The emulator speed depends on the host computer. The test will be done by me on the same device. Probably the Galaxy Tab.
    Once you optimized your solution you can submit me your project and I will test it.
     
  6. Erel

    Erel Administrator Staff Member Licensed User

    Creating more threads than the number of processors available will not help in this case. It will only make your program slower. This is a CPU bound problem.
     
  7. thedesolatesoul

    thedesolatesoul Expert Licensed User

    That is true. I'm always thinking in hardware design terms!
     
  8. Brad

    Brad Active Member Licensed User

    Since I've never have played this game I had to look it up..This is either going to be a lot of fun or I'll end up with a very sore head from :BangHead:
     
  9. Erel

    Erel Administrator Staff Member Licensed User

    The simplest solution shouldn't be too difficult. Read about backtracking...
     
  10. hackhack

    hackhack Active Member Licensed User

    Which is why i said it would be on your machine ;)

    Is your app faster than Googles? :)
     
    Last edited: Sep 6, 2011
  11. Kevin

    Kevin Well-Known Member Licensed User

    Being mathematically challenged (which sometimes makes my programming adventures a series of trial and error, and is a big reason why I don't "do" layouts in code), I too shall pass on this one.

    I tried one of these puzzles quite a while ago and it just made my head hurt. :D

    Good luck to those who enter!
     
  12. JesseW

    JesseW Active Member Licensed User

    I haven't even started coding yet, and my head hurts already :(
     
  13. corwin42

    corwin42 Expert Licensed User

    First attempt:

    Code:
    12653ms (per puzzle)
    on an LG P500 Optimus One overclocked with 729MHz

    I think I have to do some optimizations. :D
     
  14. eps

    eps Well-Known Member Licensed User

    The gauntlet has been thrown down!! Very tempted to have a go at this. Although I was planning on releasing my 2nd App before the end of this month...
     
  15. thedesolatesoul

    thedesolatesoul Expert Licensed User

    Question:
    Which is faster: 2D Arrays, 1D Arrays, Lists?

    Another question:
    Is it faster to create local arrays that keep getting destroyed or declare global arrays?

    EDIT: Also another question...(sorry about the questions)...
    You know that different algorithms can solve different puzzles at different speeds. Lets say a brute-force algorithm may solve 2 different puzzles in different times.
    So are you going to throw in 10 puzzles and average the time?
     
    Last edited: Sep 7, 2011
  16. JesseW

    JesseW Active Member Licensed User

    You know if you release your 2nd app instead, it'll never generate $500 in the time frame it takes you to win this contest! Gotta go with the money, dude! :D
     
    Peter Simpson likes this.
  17. eps

    eps Well-Known Member Licensed User

    I know, this had already crossed my mind!!! I'll give it a go - made good inroads with the next App..
     
  18. Kamac

    Kamac Active Member Licensed User

    I think i'll pass by...
    ...I'm just too weak i guess.


    Or no :confused:

    Gotta take a look.
     
  19. thedesolatesoul

    thedesolatesoul Expert Licensed User

    On the emulator: 35017ms (per puzzle)
    ...and i get all the answers wrong ;)

    EDIT: downto 7274ms (per puzzle)
    ofcourse with wrong answers again!

    This is hard!
     
    Last edited: Sep 9, 2011
  20. corwin42

    corwin42 Expert Licensed User

    I just sent Erel my first solution.

    Let's see what result he get on his Galaxy Tab...
     
Loading...
  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice