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

  • Sudoku.zip
    5.8 KB · Views: 474

boten

Active Member
Licensed User
ok, thanks. I will submit 2 versions for competing closer to the deadline.

I think i got dumber myself - the "sophisticated" version is slower on tougher puzzles (which makes sense)
 
Last edited:
Upvote 0

boten

Active Member
Licensed User
Since many of the posters to this thread (myself included) witnessed worse times on the first run and better times on subsequent runs (as mentioned before, might be idle CPU, time to load the app into memory or whatever other reason), may I suggest that you ignore the time of the first run and average only the times from the 2nd run forward, thus eliminating the overhead of loading the app into memory, waking the CPU, etc...
 
Upvote 0

JesseW

Active Member
Licensed User
Yes, the main thing to remember is we are racing against each other, not the clock. As long as we are all measured by the same stick, the contest is fair. Having a quicker score on subsequent runs is just bragging rights. Which we all love ;D
 
Upvote 0

Brad

Active Member
Licensed User
Looks like some stiff competition! I have been so swamped I haven't had time to even play around with this... Good luck guys and gals! :)
 
Upvote 0

Rioven

Active Member
Licensed User
Can't go less anymore...

About 124ms per puzzle on my Motorola Atrix :(
 
Upvote 0

Rioven

Active Member
Licensed User
My solver tested!

Thanks Erel for testing my solver! :sign0162:
 
Upvote 0

thedesolatesoul

Expert
Licensed User
I hope Erel is going to put a list of all the entrants and their times.
I spent a few days on this, ofcourse nothing worked.
Then I can see if I made the worst solver or not (because quite frankly the algorithm was pure brute force and as bad as possible)...so I am basically aiming for last spot!!!
 
Upvote 0

boten

Active Member
Licensed User
That's it!
I had so much fun trying to "shave off" few microseconds from my solver, my eyes turned into a 9x9 grid:BangHead:

Just submitted my final crop to Erel, good luck to all who did it. :sign0098:
 
Upvote 0

Sergun73

Member
Licensed User
Getting ~100ms per puzzle on my Galaxy S1.
Can't get any faster than that - any attempt to optimize it leads to slower runs :eek:

Good luck to everyone!
 
Upvote 0

MM2forever

Active Member
Licensed User
Good luck at all the other competitors - I've given up... I cant do it in time although i will keep working on an at least working solution, disregarding the speed - just for my own interrest...
I basically know what the problem in my code is but i cant find a solution that quick...

My :sign0188: for all those who made a working solver :sign0098:


=================================================

Question: Will the source of fastest solver be posted here?
 
Upvote 0

ertuncb

Member
Licensed User
Your result is a good result for a pure backtracking solution.
Backtracking can be a very heavy operation. You should try to think of ways to "help" the backtracking operation (somehow make the puzzle easier for example).

Hi Erel,

Didn't have much time this week to optimize the code.
May be I will take a look to the code before I send you the last version.

What did you mean with "(somehow make the puzzle easier for example)" ?

Regards,
Bahri
 
Upvote 0

ertuncb

Member
Licensed User
The deadline is today at 23:59 PM...


The idea is to use less "brute force" and find ways to decrease the puzzle complexity.

Hi Erel,
I tried everything (find out lone rangers, twins, triplets etc. to decrease the number of possible candidates) to speed up the solver. But on every addition, the solver got slower.
Sent my last pure brute-force version to you, which solves the given puzzle set in 50 ms average.
I hope that you will get my code in time because of the time difference between your location and my country.
Regards,
 
Last edited:
Upvote 0

ertuncb

Member
Licensed User
Hi Erel,
Is it possible to get later the puzzle set you will use to test the solvers ?
 
Upvote 0
Top