Sudoku solver contest: We have a winner!!!

[Erel]

The Sudoku solver contest is now over. We have measured the solvers and you all did a great job!

:sign0188:

Two solutions were really amazing: 14ms and 18ms per puzzle.

The winner is: Markus Stipp (corwin42) :sign0188:

I will send you an email about the prize...

The other five best results are:

clewgsm - 18ms
derez - 51ms
boten - 66ms
Rui - 102ms
ertuncb - 113ms

I've tested the two best solvers many times and the results were consistent.
I've asked corwin42 to explain his solution which looks pretty complicated.
The fastest solver and the puzzles are attached.

 

[thedesolatesoul]

Congratulations to everyone that managed to create a working solver.

Thank you!
my result was around 3000 ms I think...good huh!

 

[corwin42]

Ok, now I have little time to say some words.

When I solved my first Sudoku puzzle a few years ago I got a little fan of this kind of puzzles. I tried to find many rules and ways to solve them and you can find many resources in the internet with tipps and tricks about it. After a short time the puzzles got quite boring because it was always the same procedure: Using rules to place numbers or eliminate allowed values until you have the final solution.

My solution works very similar like a human would solve the puzzle. In a loop there are 5 rules applied as long as up to five numbers could be found with this rules. If less than 5 values are found (or we have placed more than 69 values on the board) then the solver tries a backtracking because this is faster than applying comlicated rules.

There are two types of rules. One type tries to find numbers to place on the board and the other rules eliminate allowed values from a bitfield which stores the allowed values for each field on the board. In my solution there are 3 Rules that places numbers (The third one called only very rarely. It is only used to reach my personal goal to get solving times below 10ms on my LG P500 Optimus One. I guess the first two rules would have been enough to win the contest), and two rules which just eliminate allowed values.

The trick is to call the rules in the correct order and not every iteration of the loop. It took several days of (automated) testing to find the values when to call which rule and when to fall back to backtracking.

I will write a more detailed description in the next days. I think I will start a new thread for this and explain it step by step.

 

[gnostic]

browsing the code, i recall seeing it before here (Kevin's sudoku solver):
Sudoku solver update « Byte Author

 

[rtesluk]

Nothing on the screen running app Sudoku

Oct 3 2011
07:50 Hours

I downloaded the app and ran it on the emulator Level 8 and nothing appeared on the screen.

Somehow the 'log' function is not working for me.

So I replaced all of the log functions with the Msgbox function and I was able to see the end result.

I got 76 ms.

Congrats to the winner! :sign0098:

 

[Amalkotey]

My congratulations! :sign0098:

 

[Johan Schoeman]

Not my intention to take anything away from the winner (won by @corwin42 way back in Oct 2011) but it seems as if the attached project solves the same puzzles 3 to 4 times faster than that of the winning project. Project is based on the Dancing Links algorithm of Donald Knuth. It uses inline Java code - code is very short and can very easily be converted to B4A. Have not tried to add any optimization to the project - just adapted it slightly to fit B4A project. Competition puzzles have been hard coded in the project (so Sub Activity_Resume does not look the same) but points of time measurement (start/finish) are however the same.

CORRECTION EDIT: change this line
Log(Round((DateTime.Now - starttm) / 9 ) & "ms (per puzzle)")

to

Log(Round((DateTime.Now - starttm) / 7 ) & "ms (per puzzle)")

Still at least 2 to 3 times as fast when measured on the same device...

 

[KMatle]

Could you measure the time between Oct, 4th 2011 and now in ms?

 

[freedom2000]

Great Markus !

 

[corwin42]

Not my intention to take anything away from the winner (won by @corwin42 way back in Oct 2011) but it seems as if the attached project solves the same puzzles 3 to 4 times faster than that of the winning project. Project is based on the Dancing Links algorithm of Donald Knuth. It uses inline Java code - code is very short and can very easily be converted to B4A. Have not tried to add any optimization to the project - just adapted it slightly to fit B4A project. Competition puzzles have been hard coded in the project (so Sub Activity_Resume does not look the same) but points of time measurement (start/finish) are however the same.

CORRECTION EDIT: change this line
Log(Round((DateTime.Now - starttm) / 9 ) & "ms (per puzzle)")

to

Log(Round((DateTime.Now - starttm) / 7 ) & "ms (per puzzle)")

Still at least 2 to 3 times as fast when measured on the same device...

First I think the devices are so fast today that exact measurement is hard for such few puzzles. To get better measurings a few hundred puzzles would be better. On my Nexus 5 I most times get 2ms per puzzle with my program from the contest. Times varied from 2ms to 4ms on my short tests.

With your solution I get times between 3ms to 6ms and most times something between 4 and 5 ms per puzzle. So it seems that the solution I used is still faster in my opinion.

 

[Johan Schoeman]

Have also noticed some irregular timing with only a few puzzles - and your solution mostly wins. So have used 1465 hardest sudokus from here. Have changed the code in both our projects slightly not to compare answers with results in a file but added code to check if each puzzle adds to (45*9) - if not, the Sudoku can't be a valid solution (some puzzles might have more than one possible solution - have not checked the 1465 puzzles for uniqueness). Test the attached projects on your Nexus 5 and see what you get wrt timing. On a Samsumg S4 mini I get an average of 16ms/puzzle for your solution and 8ms/puzzle for the DLX algorithm.

Puzzle files (data_hard.txt) and additional library files (StringFunctions) are in the /files folder.

Markus, no competition here - just trying to see how fast a Sudoku solver can go. It is the same as when Roger Bannister ran the first sub 4 minute mile in 1954 (3:59.40). Other athletes did not stop trying to go faster and today we are sitting at 3:43.13. Same thing.

Have tried various options of DLX and this one seems to perform the best so far.

Rgds

Johan