Yay finally ....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.
Last edited by Raedwulf; Aug 27th, 2005 at 03:20 PM.
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! I have no idea why, and I would really appreciate it if anyone else could test it! Thanks
Last edited by manavo11; Aug 27th, 2005 at 06:02 PM.
Has someone helped you? Then you can Rate their helpful post.
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
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
So when's the next contest?
Last edited by penagate; Aug 28th, 2005 at 12:18 AM.
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 !
Congrats Merri ....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 +
Do I get a prize for smallest implementation ;P
Last edited by Raedwulf; Aug 28th, 2005 at 03:13 AM.
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?
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.
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.
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.
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.
I wish this contest had been open to other than a couple of Microsoft-only languages, or I would have entered it.
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?
Has someone helped you? Then you can Rate their helpful post.
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?
-Lou
The grand prize is a custom title with HTML formatting to make it extra special (bold, color, stuff like that)
Has someone helped you? Then you can Rate their helpful post.
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.
-Lou
Last edited by NotLKH; Aug 28th, 2005 at 09:00 AM.
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)
Has someone helped you? Then you can Rate their helpful post.
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.
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! I have no idea why, and I would really appreciate it if anyone else could test it! Thanks
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.
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
Has someone helped you? Then you can Rate their helpful post.
Hey, why didn't CVMicheal enter? Or did he not do VB6. I remember he was really into it earlier in the contest. Hmmmm.
When I realized there's no way in hell I can beat anyone (epecially Merri), I even unsuscribled to this thread.
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...
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.
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
means that i had the fastest single time: 027_0273 in 0,003 ms.
...
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.
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
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!
@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 ?
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.
Originally Posted by dukuso
@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...
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?
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. 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
>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?
>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.