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

corwin42

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?

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.
 
Upvote 0

thedesolatesoul

Expert
Licensed 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 :(
 
Upvote 0

JesseW

Active Member
Licensed 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 :)
 
Upvote 0

corwin42

Expert
Licensed 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:
 
Upvote 0

moster67

Expert
Licensed 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.......:D

Poor us.
 
Upvote 0

RandomCoder

Well-Known Member
Licensed User
The simplest solution shouldn't be too difficult. Read about backtracking...

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? :p

Just reading the Wiki for backtracking has given me a headache :BangHead:

Regards,
RandomCoder
 
Upvote 0

ertuncb

Member
Licensed 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)
 
Upvote 0

hackhack

Active Member
Licensed 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.......:D

Poor us.

Google Goggles can solve Soduko puzzles for free already, so it would have to be good ;)
 
Upvote 0

thedesolatesoul

Expert
Licensed 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 :(
 
Upvote 0
Top