Contest: Write the quickest Sudoku solver and win 500$

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.
 

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 :(
 

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

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:
 

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.
 

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
 

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)
 

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

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 :(
 
Top