Contest: Write the quickest Sudoku solver and win 500\$

Erel

B4X founder
Staff member
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
Dim results As List
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("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: 629

corwin42

Expert
Longtime 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?

I think 1D arrays should be the fastest but I currently use 2D arrays because it's better to understand.

About local/global: I think if you create global arrays at Activity_Create and just use them it will be faster. The problem is that you don't know how many boards you need for the backtracking. Createing an array for every permutation at the beginning is not a good idea i think.

From first post:
Your application will be tested with a different set of puzzles.

I think Erel will use a set of puzzles. Perhaps even more than 7 as in the example because I get quite different results on my LG P500 when I call the example multiple times.

thedesolatesoul

Expert
Longtime User
I agree.
I am using a 2D array of lists. That may be a bad idea. I will have to change it later.
Some puzzles can be solved without backtracking (although I havent tried to solve the given puzzles without it), so I was wondering i may try and avoid backtracking but then that would not be a complete solution.
backtracking is quite hard to debug

JesseW

Active Member
Longtime User
I agree that 1d arrays are faster than 2d arrays, but... if the problem being solved is 2d, like the layout of a sudoku puzzle, then I would think using a 2d array would be faster than using a 1d array crippled with row and col transformation logic code, even if that code were very simple.

I also believe Int's are probably the fastest primitive data type for the microprocessor to deal with. I'm thinking Erel left us these clues in the sample code

Erel

B4X founder
Staff member
Longtime User
I recommend you to first optimize the algorithm and only then try to "squeeze" some more by choosing the best data type. The algorithm itself will have the most effect on performance.

Kamac

Active Member
Longtime User
I wonder why that contest Erel?

To bring some more users to B4A, or just for fun? (Which would be strange, because it's a loose of 500\$ )

Staff member
Longtime User

corwin42

Expert
Longtime User
I wonder why that contest Erel?

The next big feature in B4A will be a hidden sudoku solver which get compiled into every app and is activated with a strange touchscreen gesture. But because Erel is too lazy to write a fast resolver he let the community do the job for him. :sign0089:

moster67

Expert
Longtime User
I think Erel will publish the best and fastest one on the Android Market as a pay-application and once the revenues have covered the initial USD 500,00, all extra-revenues will make Erel a really rich man and he can decide to retire from the IDE-business.......

Poor us.

thedesolatesoul

Expert
Longtime User
Finally I have mine working and it is taking: 204417ms (per puzzle)
on the emulator with debugging and logs etc...:sign0080:
...only 1000 times worse than what I am aiming for!

Erel

B4X founder
Staff member
Longtime User
If you like you can send me your project and I'll measure the results.

corwin42

Expert
Longtime User
Is there somewhere a good sudoku generator available that can export text files? I need more input

Sent from my LG-P500 using Tapatalk

RandomCoder

Well-Known Member
Longtime User

When starting out with B4PPC I decided to write a Sudoku solver, just for the fun of it and as something to help me familiarise myself with B4PPC. It used bruteforce and took an age to complete on the device (although on the PC it was much more acceptable). I'm pretty certain that I could acheive the slowest time... is there a booby prize?

Regards,
RandomCoder

ertuncb

Member
Longtime User
On the emulator, with original data.txt:
B4X:
``````LogCat connected to: emulator-5554
** Activity (main) Create, isFirst = true **
** Activity (main) Resume **
11074ms (per puzzle)``````

On Samsung Galaxy S II:
B4X:
``````** Activity (main) Create, isFirst = true **
** Activity (main) Resume **
247ms (per puzzle)``````

Erel

B4X founder
Staff member
Longtime User
247ms (per puzzle)
Nice result!
Tomorrow I will test the project you sent me...

hackhack

Active Member
Longtime User
I think Erel will publish the best and fastest one on the Android Market as a pay-application and once the revenues have covered the initial USD 500,00, all extra-revenues will make Erel a really rich man and he can decide to retire from the IDE-business.......

Poor us.

moster67

Expert
Longtime User
Sure - my previous post was of course meant as a joke.

Erel

B4X founder
Staff member
Longtime User
I received several results. Corwin42 currently leads the contest with a very impressive result: 154ms per puzzle!

thedesolatesoul

Expert
Longtime User
I received several results. Corwin42 currently leads the contest with a very impressive result: 154ms per puzzle!
That is truly impressive. I wonder how many techniques he is using to bring the time down.
But then, that is only 200 times better than mine :sign0094: ...this is making me sad

Replies
2
Views
858
Android Tutorial How to write a sudoku solver
Replies
3
Views
13K
Replies
29
Views
11K