Contest: Write the quickest Sudoku solver and win 500$

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:
B4X:
   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.
 

Attachments

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:
 

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!
 

JesseW

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:
I haven't even started coding yet, and my head hurts already :(
 

eps

Expert
Licensed User
First attempt:

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

I think I have to do some optimizations. :D
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...
 

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:

JesseW

Active 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...
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
 

eps

Expert
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
I know, this had already crossed my mind!!! I'll give it a go - made good inroads with the next App..
 
Top