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)
Well I'm mad. I finally got around to seeing why my program didn't solve all the puzzles and it looks like I just submitted the wrong copy of my code because I was submitting it in such a rush. Too bad I suppose. I still learned a lot in the process.
I really hope one of the mods hosts another contest soon. This was a lot of fun. :thumb:
I must say I'm glad you all enjoyed it. :)
It's a shame there were only a few entries in the end, but congratulations to those of you who managed to create a working solver, even if it wasn't the fastest. :thumb:
If it's any consolation, I never finished mine so all your project are better than mine :afrog:
I just need a new topic that more than 2 people take an interest in (actually, hopefully more than 7 :rolleyes: ) and we can have another one :)
BTW eyeR, what on earth was wrong with your code that it worked in the IDE and not compiled? :ehh:
Hi
I am trying to write a pure logic solver, I have got quite far. It is a pitty I didnt see this sooner or I could have entered my solution, which solves most medium level puzzles without guessing. Is there going to be a re-run? if not I will post my solution and hopefully get some help in finishing it! (translating the solving tactics into code is a bit of a nightmare)
The contest has ended. If you want, you can post your code in the contest entries when you finish so it can be with all the rest :) But it won't be as competition with the rest, just to be there.
I might start a contest thingy later on, I'm not sure if I'll have the time to keep it up. But one can always try :)
Start a contest? :ehh:
BTW Merri, don't you want your contest prize?
When i finish it i shall only post the algorithm not all the other stuff that was needed for the contest,it will take too much time otherwise. it will be interesting to see how they compare, i am doing something similar to merri but instead of using a string of bytes i am using arraycandidate(81,9) and arraysolution(81) and some nifty loops!
i presume bytes are faster to process or whatever but i would have thought to manipulate the byte strings to hold the data you want would take up more effort than manipulating arrays? dunno we shall see.
ps i am a vb noob
Well, good luck with it char1iecha1k :thumb:
Atm I don't see much value into it, I already have a custom title and I don't see a need to put colors into it etc.Quote:
Originally Posted by manavo11
Long arrays are faster, because processors are 32-bit. The processors are optimized for 32-bit values, thus 32-bit values are the fastest. From the sound of it, it looks like you're doing something completely different than what I did :)Quote:
Originally Posted by char1iecha1k
What are byte strings? If you mean string data type, I have to tell you: they're very slow in VB, because strings are very wise and easy to use. Thus a lot of extra code checking for various things -> slow.
Oh well, if you change your mind let me know :)Quote:
Originally Posted by Merri
Alternate Blue and White to match the sky in your new avatar :) :thumb:
Congrats to all contestents. Sole VB.Net entry? I'm depressed.
My timings are generated but are copied to the clipboard instead of being printed out to a file.
My Generator is VBNet.
Its got a solver.
I should have entered.
My solver wasn't designed for a speed competition, so its safe to say you'd still have won.
Boy, I really have an urge to attach some more msk files.
But I guess that'd be a waste of my attachment allotment.
Maybe in a month or so, when I get around to building Linked Sudokus.
:wave:
-Lou
Quote:
Originally Posted by dglienna
I notice a sharp drop in board activity, though.
So, who is still working on his/her program ?
Who did understand the other programs and was able to include
some ideas from them into his own program ?
This is a ridiculous post bump, but I just wanted to say (6.5 years later!) that I think about this contest often. It was a fun problem to solve right when I started getting into programming. And now I code for a living. Hope everyone in the VB6 forums community is doing well. If anyone wants to reconnect with me, I'm over at blanchardjeremy.com. <3
As ridiculous reply an additional half a year later!
- I also remember this contest every now and then. A shame there wasn't other as successful ones.
- I still don't code for a living.
- But I'm well, I've found my way to worklife after having huge difficulties most of the 00's.
- In programming I've switched to PHP/JavaScript, maybe finally C++ soon enough.
- I no longer do VB6 at all - a hard language to drop as it does have a lot of fun parts despite many huge limitations.
To this day I haven't solved a single sudoku by hand. I can write a program that does it, but doing it by hand just isn't something I'd be interested of.Quote:
Originally Posted by penagate