Contest: Write the quickest Sudoku solver and win 500$

E

ertuncb

Member
Licensed 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
 
C

clewgsm

Member
Licensed 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
 
C

clewgsm

Member
Licensed 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!
 
E

ertuncb

Member
Licensed User
Erel said:
@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.
Click to expand...
: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,
 
corwin42

corwin42

Expert
Licensed User
ertuncb said:
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.
Click to expand...
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.
 
C

clewgsm

Member
Licensed User
corwin42 said:
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.
Click to expand...
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.
 
C

clewgsm

Member
Licensed 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 ? ;)
 
E

ertuncb

Member
Licensed 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:
boten

boten

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

boten

Active Member
Licensed 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)
 
boten

boten

Active Member
Licensed 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?
 
C

clewgsm

Member
Licensed User
boten said:
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?
Click to expand...
It would be useful if you could make available to all your "tougher" set so all can use same puzzle sets. ;)
 
You must log in or register to reply here.
Top