Yay finally :D ....Compiled here we go....now for the results :)
Note: Pentium Optimisations are for Pentiums Pro ,I - when VB6 was released.
Pentium 4 has completely different architecture so the optimisations won't improve on performance.
Printable View
Yay finally :D ....Compiled here we go....now for the results :)
Note: Pentium Optimisations are for Pentiums Pro ,I - when VB6 was released.
Pentium 4 has completely different architecture so the optimisations won't improve on performance.
Ah. :) I hope manavo releases the results soon. I just hope I don't get last place.
Hey, why didn't CVMicheal enter? Or did he not do VB6. I remember he was really into it earlier in the contest. Hmmmm.
OK then, results :)
VB 6 winner : Merri
VB.Net winner : ntg
Congrats :thumb:
Here are the results in the excel file :)
ntg wins by default, since he had the only .Net entry :)
Also, eyeRmonkey, I really don't understand what on earth happened, but your code solved all the sudokus in the IDE but not compiled! :ehh: I have no idea why, and I would really appreciate it if anyone else could test it! Thanks :)
congrats merri, and the rest.
And thx manavo! good job.
Yay! Now if I just had Excel... need to download OpenOffice.org to see the file. 71 MB, I'm waiting for you...
Code:Username VB Version Total Time (IDE) Total Time (Compiled)
Brick1 6 7.824347 0.38939
bpd 6 1.93226625 0.33901571
Merri 6 3.264567 0.170920885
kaffenils 6 41.600266 4.907671
Raedwulf 6 18.43646273 0.578268467
eyeRmonkey 6 20.194833 1.779405 (not all solved!)
ntg .Net 0.77159332 0.62759289
Ok, thanks :) Still downloading OO.org though, I seriously have a need for Excel support.
Seems like they've made the IDE support much speedier in .NET... in the other hand, there is no P-Code there. But for now, we are waiting to see each others codes :)
Thanks for reminding me :blush: Forgot to move them back :D
Moved back... Enjoy :)
http://www.vbforums.com/forumdisplay.php?f=68
In .NET there is no P-Code as Merri says. All the difference is a debugger is attached (the IDE) whereas compiled there isn't. Plus it is both IL.
I wsa going to enter this competition myself, just for kicks, but I guess I'm not smart enough :( I understand the concept but can't for the life of me solve one by hand. My solver got as far as solving rows and then once I added columns it went into an infinite loop, by which point I had a severe headache :D
So when's the next contest? :)
here are the correlation coefficents (*100) for the timings
of the 1011 individual instances.
I included mine as (duk).
Send your timings to sterten(at)aol.com if you want to be
included in that table and aren't already.
(or have other datasets from different versions)
just send or post a file with 1011 numbers for the timings.
don't shuffle the instances !
norming of the timings, multiplying by a positive constant,
adding a constant doesn't matter.
99 : very similar , linearly dependent
00 : completely independent
there could be some errors due to the ordering of the instances.
I can't believe that bpd,rae,eye should have got
timings so much different from mer,bri,kaf,duk !
mer bpd bri rae eye kaf duk
mer -- 06 22 09 07 29 42
bpd 06 -- 04 05 00 03 02
bri 22 04 -- 05 07 20 36
rae 09 05 05 -- 01 20 12
eye 07 00 07 01 -- 07 07
kaf 29 03 20 20 07 -- 40
duk 42 02 36 12 07 40 --
(see with fixed font)
manavo, what computer did you use for the timings ?
I can't read the sources. I think, I don't like VB6 ...
can anyone do 16*16 sudokus ?
I'd like to see timings for
http://magictour.free.fr/su16
(or other datasets)
-Guenter.
Congrats Merri :D....I should have done better but I did mine in two days :)
Yikes amazing.....comparing amount of code I did - it isn't bad 5.64k code vs 40k + :D
Do I get a prize for smallest implementation :) ;P
Good Job!
When does NTG get his custom status?
What does Merri get, since Merri already is in the Custom Title Realm?
Mod Powers? A forum? 2000 Rep Points?
:wave:
-Lou
I wish this contest had been open to other than a couple of Microsoft-only languages, or I would have entered it. (My time was 253 ms on a P2-400MHz, probably would have been under 50 ms on whatever the test machine was).
Here is a CSV file with all the results in microseconds, with my times added. This should be easy to look at or load into a spreadsheet. The last two columns, guess and place, are counters my program keeps track of. Guess is how many cells were filled in via a guess as opposed to logic. Place is the count of numbers placed into cells. 81 would be the best, more would indicate some numbers were placed incorrectly and back-tracking was needed.
Here is the correlation matrix again:
Four of the programs, Merri, Brick1, kaffenils, and xyzzy all have decent correlation with each other. While Raedwulf, bpd, and eyeRmonkey don't correlate with anything.Code:Brick1 Merri Raedwulf bpd eyeRmonkey kaffenils xyzzy
Brick1 100 23 6 4 7 21 28
Merri 23 100 9 4 8 30 37
Raedwulf 6 9 100 5 1 20 8
bpd 4 4 5 100 1 3 4
eyeRmonkey 7 8 1 1 100 8 8
kaffenils 21 30 20 3 8 100 24
xyzzy 28 37 8 4 8 24 100
Here is a table or normalized quantiles, which probably doesn't mean that much, but I'll explain it a bit.
First of all, the numbers in the table are normalized so that 1.00 means the average time that program took to complete a sudoku. e.g. for Merri 1.00 means 148 microseconds. Now look at the 50% row. This is the time under which the program could solve the fastest 50% of the problems. For example, Merri's is 0.77, so his program could solve half the problems in under 77% of his average time (114 us), and the other half took more than that. The 100% row is the time the slowest problem took, for example bpd's slowest problem took 81.66 times as long as his average time.Code:Brick1 Merri Raedwulf bpd eyeRmonkey kaffenils xyzzy
0% 0.01 0.22 0.12 0.58 0.03 0.02 0.72
33% 0.46 0.61 0.35 0.73 0.27 0.16 0.77
50% 0.68 0.77 0.54 0.79 0.40 0.30 0.86
67% 0.91 1.00 0.88 0.89 0.59 0.53 0.97
100% 42.29 6.47 36.22 81.66 15.33 34.68 3.89
This gives you an idea of how 'smart' the basic algorithm used was. You want the numbers to be close to 1, especially the 67% and 100% quantiles. In the 100% number is large, it means you do really bad on a few problems. If the 67% number is low, is means your average time is getting bumped up a lot by your slowest third.
We're back to that again? :D Who wants to find an interesting topic/idea? :DQuote:
Originally Posted by penagate
I used my laptop that isn't all that great :Quote:
Originally Posted by dukuso
Athlon 2600 (mobility)
192 MB RAM
Well, the idea is to get lots of people to enter... This being a forum with it's main language being Visual Basic we attract mostly programmers that use MS products. We had VB6, VB.Net and C# as the languages. VB.Net had one entry and even though C# was asked to be included, no one coded a solver. So if we had added Delphi or Java, how many people would have submitted an entry? ;)Quote:
Originally Posted by xyzzy
The grand prize is a custom title with HTML formatting to make it extra special (bold, color, stuff like that) :)Quote:
Originally Posted by Something Else
How about Linked Sudoku's?
For example, Given N msk patterns, solve both somewhat simultaineously.
However, the twist:
Not only do the msk patterns contain decimal points to indicate hidden numbers, and the values 1 thru 9 to indicate revealed values, but the characters A thru I, to indicate that, across the N msk patterns, any cells that have the same character indicates those cells have identical values. But you still don't know what they are.
VIA simultaneous solving, those Shared cells will each have their could be's removed, until at some point, their must be value will be revealed.
BTW, the revealed cells in the msk patterns will not be sufficient, on their own, to solve that msk pattern down to an individual solution. Only when the Shared cells have been solved will there be enough info to complete the solutions.
:wave:
-Lou
Is this for a next contest Lou? Cause if we got 7 entries with the simple sudoku solver, I really doubt people would enter (even though I like the idea) :)
Yes, it would be for a contest.
As you can see, at http://www.setbb.com/phpbb/viewtopic...&mforum=sudoku ,
The contest is beginning to be talked about on other boards.'
A new sudoku contest might attract more entrants, as it becomes more publicized.
Really!?! AH! Thats no good. I ran home and submitted the last backup of the program I had made bevause I had been in the middle of making some changes when I left. Mabye I submitted the wrong one or something. Thats really weird. I just downloaded the puzzles, but I don't have time to test the code right now.Quote:
Originally Posted by manavo11
Congrats Merri. I wish I had time to look at your code right now, but I am taking my girlfriend to the zoo. I'll check it out some time and kick myself in the face 100 times for not thinking of half the stuff you did. :)
I really hope there is another contest soon. But then again, school starts for me soon and I won't be posting here much, and I guess I won't be programming much either.
xyzzy concerning the normalized quantiles: what is the 0% line trying to tell us?
I noticed my value is the lowest there! hehe, is that good or bad news?
Some ideas for the next contest:
- Generate a single solution 9x9 sudoku with 16 numbers revealed. or prove mathematically this is impossible.
- Generate a single solution 9x9 sudoku where one revealed cell leads to a different unique solution for every given value from 1 to 9. or prove mathematically this is not possible.
- Generate a single solution YxY sudoku where Y is as large as possible.
- Rectangular sudokus YxZ with f.e. 9rowx18col where every number exists twice in every row and 3x6 block, but only once in a col. Also find other viariations.
- 3D-sudokus. imagine!
- Or just something very unsudoku-like
I think the good thing about the contest is that the subject area varies a lot. So, I'd like to see something different again, even if I continue in the world of sudoku myself. We have the other sudoku topic somewhere elsewhere, so maybe we should get back on track with that instead of using this topic?
OK, let's leave this topic for discussing stuff about the contest. If anyone has anything to suggest for a new contest you can post here : http://www.vbforums.com/showthread.php?t=306604 or read other ideas and support them so maybe it will be the next one :)
When I realized there's no way in hell I can beat anyone (epecially Merri), I even unsuscribled to this thread.Quote:
Originally Posted by eyeRmonkey
I stopped adding stuff/improving it about 15-20 days ago...
I just ran the contests msk files, in the IDE, I ran out of pacience waiting, and compiled it took 40.5 seconds for all the 1011 sudokus. Well, at least it solved them all... :rolleyes:
I guess you've now spent a while reading the codes other people posted? :)
For now, only your code :) But I will look at the others also...Quote:
Originally Posted by Merri
CVMichael's and NTG's timings would be interesting for the statistics too.
manavo, can you post ntg's timings ? they were missing
@Brick1: the 0-line is the time needed for the easiest sudoku relative to average.
How could you solve number 943 in 0.003 ms ?
@xxyzzy: thanks for the .csv file ! That makes it a lot easier.
and for the confirmation of the correlations.
Isn't it surprising that the programs need so different times
for special sudokus ? E.g. bpd's program is pretty fast but completely
unrelated to others ! So, how did he solve them ? Must be some weird
strange technique...
the 100%-line being close to 1 does not necessarily reflect 'smartness'
just means, that some further optimizations for some hard cases
seem possible/promising and yes, that xyzzy's and Merri's programs
look good also for 16*16 etc.
I've added a suggestion for the next contest http://www.vbforums.com/showthread.p...37#post2142237
YAY!
means that i had the fastest single time: 027_0273 in 0,003 ms.
Also 2nd, 3rd and 4th:
026_0536 0,020
024_0506 0,023
025_0737 0,028
where the 5th is a draw:
MER: 024_0059 0,032
BRI: 027_0273 0,032
How you can have two times for the same puzzle? Does your solver solve the same puzzle two times in a row? I get a time below 0,02 only if I try to solve the same puzzle two times in a row.Quote:
Originally Posted by Brick1
I also noticed that my output benchmark gives me worse timings, there seems to be about 0,015 ms slow down per sudoku. This is probably due to the outputting in the middle of the timing. My code performs better if it just does nothing but solves the sudokus it is given, all in row, because it allows CPU to do better predicting. This is also why Quick benchmark gives much better total time than doing any other benchmark :)
By outputting the results, I get a total time of 160 ms
By timing individual results, I get a total time of 118 ms
By just solving them, I get total time of 114 ms
ntg didn't include that feature in his entry and I didn't really want to add it myself...Quote:
Originally Posted by dukuso
sorry merri i swapped them, it should have been:
MER: 027_0273 0,032 (which I did in 0,002)
BRI: 024_0059 0,032 (which you did in 0,034)
so no games solved twice.
Hey manavo, I tested my code in IDE and EXE and it solved all of them. Which puzzle wasn't solved when you tested it?
@Merri: You code is insaneo. I can barely read it. Although, I am proud to say that about half way through the contest I had the idea of doing it in binary andusing Hex constants like you did. Then I realized that I barely had any idea how to do that and that I would have had to restructure my whole program. Congrats though!
You can see which, if any, failed in the log file, posted in your submission thread.
:wave:
As Lou posted the log file is in the thread you created with your entry...Quote:
Originally Posted by eyeRmonkey
I tried it on my desktop, same result :ehh: Download the code you have uploaded and test it instead of the code on your PC?
I have to wonder if it was some kind of error with the timer? 3 us is very fast, and the next fastest one was 20 us.Quote:
Originally Posted by dukuso
I'm sure you've noticed how the same sudoku turned upside down or rotated can end up taking much longer? Usually we have in a code something that goes "for Row 1 to 9 ; for column 1 to 9", etc. Maybe all there is to it, is that bpd started at row 9 and went to 1? ie. if bpd's program was fed the same samples upside down or transposed it might correlate with all the other fast programs?Quote:
Originally Posted by dukuso
What I'm thinking is that an algorithm that's fast for SOME sudokus is easy. e.g. just fill in the missing cells at random, sometimes you get it right on the first try! Designing one that is fast for all sudokus is harder. The smarter your algorithm, the larger fraction you can do quickly. The 100% quantile isn't the best, I think 95% would be better. But I'd classify the programs, using mean speed + 95% quantile like this:Quote:
Originally Posted by dukuso
slow speed + high quantile = naive algorithm and poor implementation
fast speed + high quantile = simple efficient algorithm and good implementation
slow speed + low quantile = smart but slow algorithm and/or poor implementation
fast speed + low quantile = smart and efficient algorithm and good implementation
xyzzy wrote:
>dukuso wrote:
>> E.g. bpd's program is pretty fast but completely
>> unrelated to others ! So, how did he solve them ? Must be some weird
>> strange technique...
>
>I'm sure you've noticed how the same sudoku turned upside down
>or rotated can end up taking much longer? Usually we have in a
yes !
>code something that goes "for Row 1 to 9 ; for column 1 to 9",
>etc. Maybe all there is to it, is that bpd started at row 9 and
>went to 1? ie. if bpd's program was fed the same samples upside
>down or transposed it might correlate with all the other fast programs?
I examined this and posted a summary to:
http://www.setbb.com/phpbb/viewtopic...um=sudoku#1426
>Quote:
>Originally Posted by dukuso
>the 100%-line being close to 1 does not necessarily reflect 'smartness'
>just means, that some further optimizations for some hard cases
>seem possible/promising and yes, that xyzzy's and Merri's programs
>look good also for 16*16 etc.
>
>
>What I'm thinking is that an algorithm that's fast for SOME
>sudokus is easy. e.g. just fill in the missing cells at random,
>sometimes you get it right on the first try! Designing one that
>is fast for all sudokus is harder. The smarter your algorithm,
>the larger fraction you can do quickly.
yes, but all the programs DID solve all the instances, so the
average time needed should be the better measure for "smartness"
>The 100% quantile isn't
>the best, I think 95% would be better. But I'd classify the
>programs, using mean speed + 95% quantile like this:
>
>slow speed + high quantile = naive algorithm and poor implementation
>fast speed + high quantile = simple efficient algorithm and good implementation
>slow speed + low quantile = smart but slow algorithm and/or poor implementation
>fast speed + low quantile = smart and efficient algorithm and good implementation
OK.
"smart" assumedly means "good worst-case behaviour" here.
This is, what usually is required in (theoretical) math, but in practice
the average-case behaviour is often more important.
-Guenter (dukuso)