Contest: Write the quickest Sudoku solver and win 500$

[Erel]

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:

   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.

 

[corwin42]

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]

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]

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]

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]

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$ )

 

[Erel]

I wonder why that contest Erel?

Life is a mystery...

 

[corwin42]

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:

 

[thedesolatesoul]

Life is a mystery...

We need to debug this life app/puzzle to solve the mystery!

 

[moster67]

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.

 

[Kamac]

I guess it's point is bring more people to the community, it's an investment into B4A, to get more purchases

 

[thedesolatesoul]

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]

If you like you can send me your project and I'll measure the results.

 

[corwin42]

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]

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?

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

Regards,
RandomCoder

 

[ertuncb]

On the emulator, with original data.txt:

LogCat connected to: emulator-5554
** Activity (main) Create, isFirst = true **
** Activity (main) Resume **
11074ms (per puzzle)

On Samsung Galaxy S II:

** Activity (main) Create, isFirst = true **
** Activity (main) Resume **
247ms (per puzzle)

 

[Erel]

247ms (per puzzle)

Nice result!
Tomorrow I will test the project you sent me...

 

[hackhack]

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.

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

 

[moster67]

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

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

 

[Erel]

I received several results. Corwin42 currently leads the contest with a very impressive result: 154ms per puzzle!

 

[thedesolatesoul]

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