Contest: Write the quickest Sudoku solver and win 500$

Erel

B4X founder
Staff member
Licensed User
Longtime 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: [email protected].
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: 699

ertuncb

Member
Licensed User
Longtime User
Hi Erel,

I made some changes on the program and sent a copy to you. It is a bit faster now. Because it is my first B4A program, the coding is not the best, but it runs.

It is interesting that i get "121ms (per puzzle)" on the first run on the device (Samsung SGS I9100), "51ms (per puzzle)" on the second run and "35ms (per puzzle)" on the third run.

I have compiled and reinstalled the program on the device several times. The first run is always slower, the additional runs getting faster.

Regards and thank you for the great IDE&Programming environment
 
Upvote 0

clewgsm

Member
Licensed User
Longtime User
Info request

Hi Erel,

can you please confirm that the last day to submit you the Sudoku solver code is September 30th ?

Kind regards,
clewgsm
 
Upvote 0

clewgsm

Member
Licensed User
Longtime User
Sudoku generator

Hi all,

I found the following online sudoku generator that can be very useful to all to generate additional test patterns for the contest:

Sudoku Generator, version 3

It's enough to press the "Clear" button and then the button corresponding to the wanted difficulty "Easy", "Normal", "Hard" or "Extreme".

Have fun!
 
Upvote 0

ertuncb

Member
Licensed User
Longtime User
@ertuncb, I'm taking the average result of the first run. Your project only included the first puzzle which is probably easier than the other as it gets solved really fast. Switching to the 7 test puzzles resulted with 575ms per puzzle.

:signOops: Forgot to reset data.txt to its original values after my testings.

Also on my SGS II I came near to your result. My fastest run was 512ms.

Its hard to optimize and get the program faster because of my limited Android programming and B4A programming knowledge. But thank you anyway. It was a good opportunity to learn the B4A IDE, the debugger and deal with the B4A language.

Regards,
 
Upvote 0

corwin42

Expert
Licensed User
Longtime User
It is interesting that i get "121ms (per puzzle)" on the first run on the device (Samsung SGS I9100), "51ms (per puzzle)" on the second run and "35ms (per puzzle)" on the third run.

I have compiled and reinstalled the program on the device several times. The first run is always slower, the additional runs getting faster.

I have seen the same effect on my device and I think there are two reasons for it.

1. If you install the app and run it immediately like the IDE does this the JIT compiler needs some time to compile in the background. So the first run is probably done without optimized JIT code.

2. Normally the CPU scales down its clock frequency when it has not much to do. It takes some time for the CPU to scale up again.

I have surrounded the puzzle solving with a for loop which solves the puzzles 100 times now. When i start it from the IDE the last executions are five times faster than the first ones.
 
Upvote 0

clewgsm

Member
Licensed User
Longtime User
I have seen the same effect on my device and I think there are two reasons for it.

1. If you install the app and run it immediately like the IDE does this the JIT compiler needs some time to compile in the background. So the first run is probably done without optimized JIT code.

2. Normally the CPU scales down its clock frequency when it has not much to do. It takes some time for the CPU to scale up again.

I have surrounded the puzzle solving with a for loop which solves the puzzles 100 times now. When i start it from the IDE the last executions are five times faster than the first ones.

I agree with you but I think that should be considered as the reference value that of the first run of the original Erel's code, so possibly without any optimization.
Furthermore the test should be run from the IDE with the target device awake and not in standby since the wake-up time depends from the current internal state and than can affects the final result.
 
Upvote 0

clewgsm

Member
Licensed User
Longtime User
Hi Erel,

would it be possible to keep updated the first post of this thread with the best results achieved for the contest up to now ? ;)
 
Upvote 0

ertuncb

Member
Licensed User
Longtime User
A new and faster version with some optimization. (but the code looks terrible now)

Got 129ms on the first run from the IDE with the original data.txt on Samsung Galaxy S II I9100.
 
Last edited:
Upvote 0

boten

Active Member
Licensed User
Longtime User
Got incosistent averages (same set of problems, those supplied) on my GalaxyS. They vary between 43 to 68 ms.
Need to figure it out and clean some of the tracing....
 
Upvote 0

boten

Active Member
Licensed User
Longtime User
Erel, for the interim results you post here, do u check with the sample u provided? On what machine? I get lower speed on my phone on 1st run. quitting the app and run it again - I get MUCH better results. (on my galaxys 2.2 froyo I get close to 60 ms)
 
Upvote 0

boten

Active Member
Licensed User
Longtime User
I have a dilemma about my solver. I have 2 versions which I tested against 2 sets of problems - the 1st set is the one you supplied and the second is a set of some "devilish", much tougher problems.

One version is dumber (uses less logic and more "brute force") and produce similar times for both sets. (say T0)

The second version is much more sophisticated (involves several techniques to solve, in increasing complexity) and resorts to "brute force" only when all else fail. For your supplied set it give much slower times then T0 but gives much faster times for the tougher set.

Can I submit 2 versions and have the better of the two results taken for the final set?
 
Upvote 0

clewgsm

Member
Licensed User
Longtime User
I have a dilemma about my solver. I have 2 versions which I tested against 2 sets of problems - the 1st set is the one you supplied and the second is a set of some "devilish", much tougher problems.

One version is dumber (uses less logic and more "brute force") and produce similar times for both sets. (say T0)

The second version is much more sophisticated (involves several techniques to solve, in increasing complexity) and resorts to "brute force" only when all else fail. For your supplied set it give much slower times then T0 but gives much faster times for the tougher set.

Can I submit 2 versions and have the better of the two results taken for the final set?

It would be useful if you could make available to all your "tougher" set so all can use same puzzle sets. ;)
 
Upvote 0
Top