Contest 6 - Sudoku solver - Discussion

[dukuso]

is this the first and only sudoku programming contest or are others known ?
I found with google, that University of Hongkong is doing something...

[dukuso]

I'd hardly come to the idea to split a file with 7611 lines into
7611 files... no wonder it's getting slow.

[Merri]

Yup, 7611 files. It is insane, but I'd have to recode my program to be able to test a single batch file. And I guess the same applies to others. Things that are on the "features to be added" list.

My program has a slowdown in showing results, because it uses a listbox to sort the results. Not so fast thing to do. I guess that's what I fix next.

[eyeRmonkey]

BTW, merri, which tab control is that you are using on your program?

[Merri]

Custom user control.

[eyeRmonkey]

Did you make it?

Wanna hook me up?

[Merri]

You'll find it at PSC ;) Not made by me.

[eyeRmonkey]

Well could you at least give me some search terms? :)

[Merri]

Here it could be tabstrip merri. Sheesh! You ought to know I share EVERYTHING here! :D

[eyeRmonkey]

Why would it be tabstrip merri if you didn't make it? Whatever... I'll go search. ;)

[Merri]

Yeah, but I said to search here :D

(making your life hard today, but probably only because I'm not having easy time myself; or then I'm just evil)

[eyeRmonkey]

I'd say your just evil. ;)

I found a crap load of other cool stuff on PSC though. I have never had the time to browse for random stuff. Now I am gonna have 20 add-ins that I never use and 1000 more user controls that I never use. But who cares! They're cool! :D

[Merri]

Atleast my avatar doesn't look like evil? But you have to say: my future homepage design (http://merri.net/uusi/) is evil. I say, Evil.

Off the topic. Back to topic! You're really trying to make an exact copy of my solver, aren't you? ;)

[eyeRmonkey]

No, I was -- Ok well maybe.

Not really. I kinda just wanted a better tabstrip control for future use. But like I said, I can't get all your good ideas out of my head. :D I'll try not to copy it too bad. ;)

:)

PS - That site looks nice, but I can't read it. Is it about small fluffy creatures? Or is it a blog?

[Merri]

Just a homepage in general, no blog atm. Adding some other stuff there. I'll make some English content as well, I guess. Though you're right: small fluffy creature describes me well. I just miss the fluffy part. Except from my legs, but that's not really the point here.

PSC controls are nice, but most of them are pretty badly done. Atleast almost each time I look into source I cry in pain.

Good thing I don't have the time to code all my ideas, otherwise you'd have plenty to copy! :D

[eyeRmonkey]

:lol:

I think I will spend some timing looking around PSC for a grid control to do a project that I gave up on because I didn't feel like messing around with a flexgrid. I know, I know... I'm lazy. :D

You must be running out of out optimizations Merri, you havn't posted any times lately. Or maybe you are just "lurking". But we all know by now that you can't hold it in when you cut your times in half AGAIN.

[Merri]

Nah, there isn't much to optimize. I did try a few things, but they just lenghtened the processing time for most sudokus. There is a limit for everything blah blah blah. And I'm not that interested to start benchmarking single parts of code trying to see which things work the fastest and in which order the code should be :D

Though really, I've had some bad days now. Was depressed a few years ago and it is easy to get into that mood every once in a while...

[eyeRmonkey]

Yeah, I have been curious what order I should put my logic rules in too.

Sorry to hear about the depression. Were always here for you though buddy. :)

Winning the sudoku contest should boost your mood a little though. ;)

[Merri]

Like if I had a proper job :/ Nope, I have never got a real salary to my hands.

[dukuso]

http://www.icparc.ic.ac.uk/~hs/sudoku.pdf

[eyeRmonkey]

Don't make me read it mommy! I DON' WANNA!

J/K. I remember wiki mentioned constraint programming, I guess I should read and maybe I will shave some time of my results.

[Merri]

I added a new logic, Nishio to my program. No much gain: results went down by ~0.2 ms by avarage for a harder puzzle.

[dukuso]

I don't know, whether this could be useful for your
sudoku-specific,optimized versions - but here is,
what the author of that paper just wrote:

>Dear Guenter,
>I'd be happy for you to redistribute the discussion.
>
>From a constraint programming point of view, I think
>the fastest solver would be based on a bounds
>consistent alldifferent and a depth-first search
>routine which selects the most constrained variable
>first. If the inverse constraint is coded effectively,
>then a channeling model (with another set of variables
>for the values in each alldifferent) could be even
>better. My hyper arc-consistent inverse constraint is
>too simple to make this competitive.
>My initial interest in the problem was not to solve
>the puzzles quickly, but to see how much can be done
>without resorting to search. There clearly is room for
>further improvements in the constraint reasoning
>concerning the interaction of the row/column and block
>constraints.
>
>Best regards
>
>Helmut

[Merri]

Could that be written in Finnish... er, I mean, English? ;) I have to admit, my problem is that I don't understand theoretical text very well. I understand the code much better than the text. In the other hand, reading code and understanding it from there is slow.

All the words that make no sense to me:
- constraint (dictionary translates this as "forced", which doesn't really help)
- alldifferent (understand the words as separate words, but can't figure out the meaning)
- depth-first (again, familiar words used in a completely bizarre way)
- inverse contraint (because I don't understand constraint)
- channeling model (familiar words...)
- hyper arc-consistent inverse contraint (familiar words...)

What I'm trying to say here... all this stuff could be explained in a way it can be understood by someone who doesn't know all the nice terms. It requires more words and probably even sentences, but it really would help if the language was understandable. Using these words limits the amount of people who can get into it. I place a bet most programmers here aren't able to follow the text smoothly.

[eyeRmonkey]

I couldn't understand it either Merri. I had the same problem with all the words you listed.

On a side note I FINALLY got my backtracker working and I am VERY VERY happy about it.

Now I can finally get around to doing all those optimizations I have been waiting on. I can also design a nice GUI for my program (my proggie still doesn't allow benchmarking and I need to add that so I can test out the speeds of things).

[Merri]

My solver now meets the contest requirements (finally). I have too much unrequired extra stuff, but I guess that isn't against the rules :D

[dukuso]

>Could that be written in Finnish... er, I mean, English?
>I have to admit, my problem is that I don't understand
>theoretical text very well. I understand the code much
>better than the text. In the other hand, reading code
>and understanding it from there is slow.
>
>All the words that make no sense to me:
>- constraint (dictionary translates this as "forced",
> which doesn't really help)

324 constraints in sudoku: exactly one symbol per cell, exacly one cell
per row and symbol,exactly one cell per symbol and column,
exactly one cell per block and symbol.
You'd probably call them "naked or hidden singles" - like if
these were easier to understand ;-)

>- alldifferent (understand the words as separate words, but can't
> figure out the meaning)

presumably because _all_ symbols in a row,column,block are _different_
Apparantly there are similar problems with other sorts
of constraints. So, if we are only interested in sudoku,
we can ignore that "alldifferent".
http://citeseer.ifi.unizh.ch/cache/papers/cs/27534/http:zSzzSzhomepages.cwi.nlzSz~wjvhzSzpaperszSzalldiff_praag.pdf/vanhoeve01alldifferent.pdf

>- depth-first (again, familiar words used in a completely bizarre way)

never heard about "depth-first-search" ?
http://en.wikipedia.org/wiki/Depth_first_search

>- inverse contraint (because I don't understand constraint)
>- channeling model (familiar words...)
>- hyper arc-consistent inverse contraint (familiar words...)

I don't know about these either. But presumably you could put
these as keywords into a search-engine and find something.
He is preparing another paper for a conference in Oct. in Spain
with timings etc.
Seems that the only really efficient method he tested was "shaving".

>What I'm trying to say here... all this stuff could be explained
>in a way it can be understood by someone who doesn't know all the
>nice terms. It requires more words and probably even sentences,
>but it really would help if the language was understandable.

this was probably done elsewhere. Usually a survey or an introductory
text is given in the references. This could be his first reference:
Apt,K.: Principles of constraint programming...
I don't know whether it's suitable for those who never heard about it.
I will ask him for a reference to an introduction into the
matter for beginners.

>Using these words limits the amount of people who can get into it.

yes. It's addressed to these experts from the workshop etc.

>I place a bet most programmers here aren't able to follow
>the text smoothly.

you still get an idea, that/how your work here relates to
real problems where much research is spent.
It's just a special case of constraint programming !
These constraint-programming programs can be used to
solve sudoku.
Whether they are faster than your sudoku-specific optimized
programs - that's another question.



BTW. the forum-page is awfully slow loading !

Guenter.

[titan7262]

ummm.. i have made a generator.. i have also made a SUDOKU checker.. the thing is.. i can't even start writing for a solver.. :(

[dukuso]

how can you generate them wothout solving ?

[titan7262]

i mean i generate sample puzzles.. like those posted.

[dukuso]

I mean, how do you verify that they have a unique solution ?

[manavo11]

1 week left :) Start wrapping them up slowly :)

[eyeRmonkey]

I mean, how do you verify that they have a unique solution ?
I somewhat doubt that he is. It's not too hard to make a program that throws 1-9 in a few cells, but making one that generates puzzles with unique soultions is a little more tough.

[dglienna]

I think that I've read that you can use the four corners of a grid, to substiitute 4 different ways to solve any puzzle. This ignores the center cell also.

[Merri]

I have some good news for you all. At some point of optimizing, my code has broken. So, there are some puzzles that fail to solve. You lot must be happy now, I don't know if I have the time to figure out the bug.

[dukuso]

ahh, why should we be happy ? Because that increases the chances of others
to win ? Some wise philosoph said: with sudoku not the solution counts,
but the path which you take. (or was it a newpaper journalist ? , well,
could have been Konfuzius too)

If it took you weeks to find a puzzle which wasn't solved, then
the judges won't probably have one for the contest.

[Merri]

No no, there are even basic ones that don't get solved. I didn't check for valid solutions for about a week (which was a bit silly of me, but I were a bit tired many of the times I coded), and now I've changed the code so much that it is very hard to find the error. I've tracked it as far as to the backtracker code itself, there seems to be no error in the logics. In worst case I have to rewrite the whole backtracker. Sounds nice, huh?

Every 1/50 puzzle seems to cause problems.

[dukuso]

just take your program from one week ago. Maybe the one you posted ?

[Merri]

Whew. Luckily I had made a solution counter, which had almost the exact same code I happened to have a few days ago. So, now I can try to apply the new optimizations again and see when the error comes in. The latest optimization I did was pretty effective...

Edit Darn. Still not wholly clear. Debug, debug... Finally! Another error found in the naked subset code.

[dukuso]

sounds as if your solver might suffer from complicatedness...
while you're there, could you measure how many % speedincrease these
"naked subsets" gave you ? Is it worth the trouble ?

[Merri]

When doing the 7611 minimal sudokus, it gave about 20% speed increase while retaining most sudokus valid. Note that it didn't take too long to fix the code, I just had to push time from something else (sorry Something Else for doing that). Though I need more time to analyze why the subset code doesn't work as it should.

[Something Else]

Heh, I understand, I also push time from myself every now and then. :)

I Just had a bout of optimizationitus myself. I created a total rewrite of my generators solver, and It looks really good, although I havn't written any backtracking into it yet. I've been trying to get it to solve all my submissions without any backtracking. It solves all but the final 15 of my last submissions. I wrote a procedure that I thought was a generic version of several other strategies. But it, for some reason, couldn't solve 1 extra submission. In actuality, it made it impossible, blanking out all possibles for 1 cell and 1 cell only!!! I debugged it, and it worked in tandom with all the other procedures. But, commenting out the ones I thought it replaced, I saw it was lacking something. So, I'll comment it out, since it doesn't do anything extra even if I keep it.

I'm just going to go back to my old code, put a counter in a couple of spots, and tweak my generator a hair.

:wave:
-Lou

[Brick1]

I'm done, finished, finito.
I have submitted my proggy and that's it. Am i the first?
Maybe I get some sleep again at night now, lovely.
Good luck to all of ya. ;)

[manavo11]

I'm done, finished, finito.
I have submitted my proggy and that's it. Am i the first?
Maybe I get some sleep again at night now, lovely.
Good luck to all of ya. ;)

You're the 2nd :) Good luck to you too :)

[dukuso]

not that it were so important for me, but just assume that
I wanted to submit something. I have a C-program which reads
sudokus from a file and solves them, So how much work is it
to meet the contest requirements ?
what's "C#" ? How to make it "callable", how to prompt, etc.

[titan7262]

hehe i have made a checker not a solver. hehe guess that doesn't count for the contest.. oh well i am trying to create a new theory for solving sudoku puzzles i just have to make something out of my theory.. will the codes be posted? I can't wait to see those codes.. :D

[Merri]

dukuso: C# is Microsoft's somewhat new language, which came with .NET when it appeared a few years ago. You can compile C# programs for free if you get the .NET framework.

For the requirements, there is another thread about it which should be rather straightforward.

titan7262: yes, the codes will be available.

[dukuso]

oh, I thought it were something like C++ or such, an extension of C.
I guess, I'm out then. Maybe I shouldn't have come here in the first place.?!

Hmm, shall I post my link to another paper as goodbye ?
I know, you're eager to read these papers...

[Merri]

C# is close to C++ in syntax, though it is more managed and it is easier to add GUI to it. I don't know much else about it. C# can be compiled to any environment that has a .NET compiler and framework available (Linux included).

[Something Else]

oh, I thought it were something like C++ or such, an extension of C.
I guess, I'm out then. Maybe I shouldn't have come here in the first place.?!

Hmm, shall I post my link to another paper as goodbye ?
I know, you're eager to read these papers...
Why are you out of here?
We have a C and C++ area,
and if you know those, go ahead and code an entry with it!
Heck! We have assembly here! Code it in assembly!

:wave:
-Lou

[Merri]

Can I code one in FreeBASIC? :D

[dukuso]

Why are you out of here?
We have a C and C++ area,
and if you know those, go ahead and code an entry with it!
Heck! We have assembly here! Code it in assembly!

:wave:
-Lou


who is "we" ?
where is that area ?
Are you saying, there is(or will be) a sudoku-programming contest in C ?
Yes, I think I could do it in assembly, but why should I rewrite it,
when it already works in C ?

[dukuso]

Can I code one in FreeBASIC? :D

could you translate that teethy smiley into English ?
you're going to bite someone ?

[dukuso]

OK, I won't post the link to the announced paper.
Just a quote:

"A new strategy to select the next variable and the value to branch on
for Latin square problems was proposed in [4](2003) . This strategy clearly outperforms all the previous ones that have been tested.It consists of
selecting the variable with the minimum domain size and then select the value
which occurs the fewest times in the domains of the variables of the rows
and the columns of the selected variable.We have improved this strategy...."

[NotLKH]

who is "we" ?


"We" are you and me, everyone who particibates in VBForums.

where is that area ?

http://www.vbforums.com/forumdisplay.php?f=23


Are you saying, there is(or will be) a sudoku-programming contest in C ?

I'm sure if you asked TPTB {ie.. the Mod of the contest area}, he might accept your C entry, and compete it against every single one of the other C entries. Of course, I have no say in this matter. But if he DOES take it, You'll probably be the Best C entry for this contest to date!


Yes, I think I could do it in assembly, but why should I rewrite it,
when it already works in C ?

heh! Show Off!
:wave:
-Lou

[NotLKH]

Heres some more patterns.

I have no idea if they've become any harder. I added a counter to weight the pattern development with iteration counts on the several strategies in my generator. Let me know if I broke it.

-Thanks
-Lou

[Merri]

NotLKH: this is your fifth set this far, not fourth :) Unless I'm very badly mistaken...

Anyways, still relatively easy. 25 ms for 314 files = 0,08 ms per file. Compared to minimum set of 453 files: 103 ms; 0,22 ms per file. If you'd get rid of the all-too-easy ones, then your puzzles would start to compare.

I make a "human difficulty rating" to my code after the contest is over, so then we can more clearly see which puzzles are hard and which are not. Computer speed isn't the only measure one should take into account. I already have an idea on how to make it.

[NotLKH]

I'd like to, hence My Ratings.
I just need feedback to determine what the ratings signifies in difficulty.

If you can list each ones speed, that'd help me determine whats what.

:wave:
-Lou

[manavo11]

The contest is for VB6, VB.Net and C#. I don't really know if it would be fair to compare a C entry with any of those...

[Merri]

It would be, dukuso already mentioned mine is faster :D Aren't we keeping it separate anyways or will all be in the same category and compared against eachother?

[manavo11]

The 3 categories I mentioned are going to be marked seperately. I meant that C doesn't fit in any of the 3 categories so I don't know if it would be fair to compare it with the entries of any of the 3 categories. Better now? :)

[NotLKH]

2 More days!

Here's the last that I'll post before the contest. Any feedback would be nice!

If you've wondered, the followin is what the numbers mean in the sol file name.

Given a filename like : 026_0674_0015-000019__Solved.sol

The first Set, 3 digits, indicates the number of exposed cells in the initial puzzle.
The second set, 4 digits, is the sequence index it was generated at.
The third set, 4 digits, is a binary composite:

A Zero means it only used naked and hidden singles
1 s: If it detected a number in a shared set of 3 cells at the intersection of a row/col and a 3x3 square that wasn't anywhere else in the row/col, but was in multiple other cells in the SQUARE, it was removed from the other multiple cells.
2: Same as 1, except the other way
4: Naked pairs were detected and processed
8: Hidden pairs were detected and processed
16: Naked and/or hidden trips were detected and processed
32: If I had it activated, it would mean naked/hidden Quads were detected and processed
64: This means, if after iterating thru all the first strategies until exhausted, and the puzzle still wasn't solved, then it went into the full iterate all posibles mode, until it found a solution. In my generator, it also counts all the solutions possible, and any that had more than 1 solution was considered a failure. None of these really should have more than 1 solution.

The 4th set, 6 digits, meant 2 possible things:

If the 3rd set < 64, then it is the count of how many times it looped adding sets of cells with only 1 possible into the solution matrix
if the third set was >= 64, then it indicates how many total possibles were available to all the unassigned cells, before it went into the 64 mode. Then I added 100.


This 4th number was what I used to filter on my generator as I tested removing revealed cells from an initiating set of succesful revealed cells.

Lets say, if I had a msk set of 26 cells that led to a solution, I would build and test 26 subsets, each of the the 26 combinations of 25 cells of this msk set, removing 1 of each 26 revealed cells. I would note which subset worked, and I would select the one with the largest 4th number as the new msk to test.

As I worked down, once I reached a set that had no good subsets, then that is the one that I'd output as a new msk entry.

Attached is my newest set, using the strategies as I've explained them, above.

:wave:
-Lou

[Merri]

Finally submitted the code. Did some final changes to actually meet the contest requirements... noticed the required output timings file format just when doing last time reading of the rules.

Happy benchmarking!

[eyeRmonkey]

I think I joined the contest a little too late. I am just now to the point of optimizing things (after finishing my backtracker). Each optimization I do breaks the whole solver for a while (until I can work out all the bugs), so I will be lucky to get 0 based arrays and 1-D arrays done by friday.

Can I turn it in at midnight on friday (my time zone)?

[Merri]

You're slow. You get eaten. That's the rule of the jungle.

You ought to be a monkey so code like one! Code like mad!


Easier said than done, but I'm done already so there shouldn't be much to complain about :D Oh, btw, I tried converting my solver to do 5 x 5 puzzle... it would be great, if all my optimization arrays worked in that mode, they take almost 100 MB unless I counted wrong... my computer just swaps when I start the project :D Don't know if it solves, this far I've had some typos... too many of them. Subscript out of range etc.

[manavo11]

I'll accept entries submitted till midnight Friday GMT. It's the easiest to keep track :)

[eyeRmonkey]

Well, I got the base 0 arrays working and got a slight speed increase and 1-D arrays are coming along nicely (although I am not far enough to get to the debugging part yet and I think they might turn out to be hell).

I have at least 10 other optimizations to do and I know I won't have time for all of them. The only reason I am getting so much done today is because my girlfriend is busy for the first day in the last 2 weeks and we aren't hanging out today (well, we are, but not until later tonight).


GMT sounds fair enough manavo.

/me walks over to google to find a time convert

EDIT: Crap! Thats 7AM friday for me. I won't even be up by then. I guess I can stay up all night thursday and be useless. Fun fun!

[Merri]

You sure you counted to 23:59 of Friday and not 0:00 of Friday? Afaik you have 30 hours to go at the moment.

[manavo11]

I mean the night from Friday to Saturday midnight...

[kaffenils]

Thats it. I have submitted my contribution. I don't stand a chance agains Merri's solver ;) , but I'll be happy as long as I don't loose.

The most important thing is to participate, not to win... I guess :rolleyes:

[eyeRmonkey]

I mean the night from Friday to Saturday midnight...
Huh? :confused: :confused: :confused:

[manavo11]

The entries will be accepted if they are submitted until 23:59 Friday night... Now?

[Merri]

In plain Finnish that means "sinulla on alle 24 tuntia aikaa" which translated to English means "you have less than 24 hours to go". About 23:25 if I'm not mistaken.

[manavo11]

GMT at the moment it's 01:37 AM... if i'm not mistaken...

[eyeRmonkey]

Well according to the time converter I went to then Oregon (USA) is GMT - 7 so midnight GMT is 7AM the same day. Am I mistaken?

[manavo11]

I think it means that you have till 17:00 (5 PM) to submit...

When it's midnight GMT, you will be 7 hours behind, which means 5 PM...

[eyeRmonkey]

That saves me a lot of stress. Thanks manavo. :)

[NotLKH]

Just uploaded the 1011 patterns for the contest.
T - 16ish hours...

:)
-Lou

[NotLKH]

The file format should be:


Quote:
FileName001.msk: (SOLVED or FAILED) in 0,000000 seconds!



Later today, 8 hours or so, I'll tweak My code , generate some patterns that return more than 1 solution, {Hence, UNSOLVABLE Sudoku} and get those submitted, to allow testing on the SOLVED or FAILED requirement.


:wave:
-Lou

[Merri]

Err... my solver solves those as well, in case you mean just more than one solution. It just gives one of the possible answers. There is nowhere said in the rules that "sudokus with multiple solutions are equal to invalid sudoku, thus the solver function must return false when it meets such a sudoku". However, if you mean really unsolvable (board that can't be solved because there must be two or more of the same number in certain row/col/block) then it gives FAILED just fine.

[manavo11]

I agree with Merri... If there is more than one solution the app won't fail to solve it, it will only fail if it can't find any of the possible solutions...

[NotLKH]

Darn!

I hoped you wouldn't point that out.
:(

{In terms of a generator, I consider a multi solution sudoku as a failure, along with those that throw off conflicted cell values.}

Oh, well. That would take a bit more development time. Never mind.

:)
-Lou

[Merri]

It is very easy to do such sudokus just by hand. For example, there can be only one completely symmetrical group of numbers within a sudoku. Thus if you place numbers in symmetrical way in the board, you get an invalid sudoku. So if you just make enough symmetric placements that first seem to be valid, you easily make an invalid sudoku. A completely symmetric placement of any numbers require that the centermost cell is included... thus if you try to place all numbers according to the symmetry, then all numbers are pointing to the centermost cell... the problem is that only one number can be there and thus you'd get eight invalid placements to the centermost block.

[NotLKH]

True. Its easy to make an invalid base.

Now Hide all but "N" of them.
Now, Solve this msked arrangement.

Is the result necessarily the base you just created, or could it be a true sudoku?

[Raedwulf]

Last minute question... when you load the sudoku problem into my program it fills some lookup arrays other than the normal 'grid'...is this acceptable or must this be in the solver routine.
And since my code is implemented in a Module (not a class) can I have a Initialise subroutine?

[NotLKH]

I would say, if by "Lookup" grids they are not created by any analysis of the puzzle, but are constant from 1 puzzle to the next, like an intermapping between the 2x2 position of the 81 cells in relation to the 9 rows and 9 columns, then I'd think you would want to initialize them in the form_load event.

But if they ARE unique to each puzzle, if you do any analysis of the puzzle whatsoever to build these grids, then I'd have to say they need to be in your solver area.

Of course, thats only My opinion.

Ask Manavo!
:)

-Lou

[Raedwulf]

Thanks.
Yet another question....after you have completed solving one problem...where do you put the 'cleanup - clearing arrays etc.' code in the same subroutine as the solver or can you put it elsewhere so it isn't timed?

[NotLKH]

I would think that, any arrays that "Need" to be cleaned up would be redimmed at the start of each solving, in your solver, hence they would be timed.

If the arrays are static, ie.. again an intermapping between 2D coordinates and 1D, then they never have to be cleaned up. But any arrays that are used for temperary values, obviously if any preexisting values interferes with the next puzzle processing, would have to be cleaned up, and IMHO, that should be part of the timing.

Of Course, it could also be argued that, if all you are doing is zeroing existing arrays, without truly adding any information into them, then they should also be outside of the timeing.

So, I officially have no idea.

:wave:

-Lou

[Raedwulf]

Yeah , Im just zeroing my arrays....hope that's ok.

[eyeRmonkey]

Of Course, it could also be argued that, if all you are doing is zeroing existing arrays, without truly adding any information into them, then they should also be outside of the timeing.

I have a sub call PrepareSudoku that sets all my relevant modular level arrays to 0 (or whatever their default value is) that is not based on the contents of the current puzzle in any way. I don't time this. I don't think Merri does either.

Manavo, can you clear this up (again? :D)? :)

[Raedwulf]

Thanks!

[Raedwulf]

Posted :D it ...hope it does well :D

[eyeRmonkey]

3 hours to go exactly. I guess I don't have time for any more optimizations, so I guess I will re-read the rules and scan the code a couple times (and remove things that are there for testing purposes only) then submit.

[Merri]

Hehe, I left my code in a pretty unclean state. Ten minutes to go and the deadline is here... I weren't able to comment all the code as well as I wanted to, there just were too many things I tested. I've a lot of undone code as well... just the way it is. No time to do everything I want.

At the moment MegaTokyo translation is getting close to my heart again, so I've been working with it for the last three days. I need to work a few more so I don't need to think about it too much in three months or so. Needs about a week more work and I'm there. Then I can spend time with other things as well.

[eyeRmonkey]

I submitted mine about 10 minutes too late and I really hope manavo accepts it. I am pretty sure he will. I left home and what I did took extra long then I rushed back to submit it in time.

[Raedwulf]

Hehe yeah I don't think 10minutes late is too bad :D.
When do the results come out?

[dglienna]

He'd have to give you a 10 second penalty for being late. Should have said your clock was wrong :)
Maybe you could argue "Monkey Time" ?

[Raedwulf]

10 second penalty YIKES!....might as well give up :D

[manavo11]

Now I feel bad :( I didn't answer all your questions before the end :(

However, NotLKH's unofficial answers are correct, so I hope you listened to him :)

eyeR, 10 minutes isn't a problem, don't worry ;)

[Raedwulf]

When are the results gonna come out?

[manavo11]

I have just downloaded all the entries. Not many :( I'll probably start marking now :)

Good luck everyone :)

[Raedwulf]

Thanks :D

[manavo11]

Question for all contestants :

Do you want the marking to be in the IDE or compiled?

The answers I need are from :

Brick1 : Compiled
bpd : IDE
Merri : Compiled
kaffenils : Compiled
Raedwulf : Compiled
eyeRmonkey : Compiled

Thanks :)

[Merri]

Compiled. With all advanced optimizations turned on in each. Saves you a lot of time :D

[Raedwulf]

Compiled :D.. Same as Merri 'all advanced optimizations turned on'

[manavo11]

OK, since majority rules, if 1 more person picks compiled I'll release the compiled results :)

[Raedwulf]

Tension rising :D
Tick tock Tick tock.....
Im growing impatient :P
1 hour after the announcement 3/6 votes
3 hours after the announcement 3/6 votes
....Last vote please :D

[manavo11]

I'm sure that the majority will pick compiled, but just incase, I'll wait for the other 3 members to reply :)

[Brick1]

Ok manavo, just read it.
To be honest, i dont care IDE or compiled. No difference if it's for everyone the same.
But agree for compiled, to get things going.

[eyeRmonkey]

Wow, not too many entries. I feel special now.

I vote for compiled with all advanced optimizations if possible. Also if you are on a Pentium, do that optimization too. :)

[Raedwulf]

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.

[eyeRmonkey]

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.

[manavo11]

OK then, results :)

VB 6 winner : Merri
VB.Net winner : ntg

Congrats :thumb:

[manavo11]

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 :)

[Brick1]

congrats merri, and the rest.
And thx manavo! good job.

[Merri]

Yay! Now if I just had Excel... need to download OpenOffice.org to see the file. 71 MB, I'm waiting for you...

[manavo11]

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

[Merri]

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 :)

[manavo11]

Thanks for reminding me :blush: Forgot to move them back :D

[manavo11]

Moved back... Enjoy :)

http://www.vbforums.com/forumdisplay.php?f=68

[penagate]

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? :)

[dukuso]

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.

[Raedwulf]

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

[Something Else]

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

[xyzzy]

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:

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

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.

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

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.

[manavo11]

So when's the next contest? :)

We're back to that again? :D Who wants to find an interesting topic/idea? :D

[manavo11]

manavo, what computer did you use for the timings ?

I used my laptop that isn't all that great :

Athlon 2600 (mobility)
192 MB RAM

[manavo11]

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? ;)

[manavo11]

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

The grand prize is a custom title with HTML formatting to make it extra special (bold, color, stuff like that) :)

[NotLKH]

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

[manavo11]

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) :)

[NotLKH]

Yes, it would be for a contest.


As you can see, at http://www.setbb.com/phpbb/viewtopic.php?p=1339&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.

[eyeRmonkey]

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 :)
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.

[Brick1]

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

[Merri]

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?

[manavo11]

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 :)

[CVMichael]

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... :rolleyes:

[Merri]

I guess you've now spent a while reading the codes other people posted? :)

[CVMichael]

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...

[dukuso]

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.

[Raedwulf]

I've added a suggestion for the next contest http://www.vbforums.com/showthread.php?p=2142237#post2142237

[Brick1]

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

[Merri]

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

[manavo11]

manavo, can you post ntg's timings ? they were missing

ntg didn't include that feature in his entry and I didn't really want to add it myself...

[Brick1]

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.

[eyeRmonkey]

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!

[NotLKH]

You can see which, if any, failed in the log file, posted in your submission thread.

:wave:

[manavo11]

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?

As Lou posted the log file is in the thread you created with your entry...

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?

[xyzzy]

@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.

@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?


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]

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.php?p=1426&mforum=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)

[eyeRmonkey]

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:

[si_the_geek]

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:

[manavo11]

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:

[char1iecha1k]

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)

[manavo11]

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.

[Merri]

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 :)

[manavo11]

Start a contest? :ehh:

BTW Merri, don't you want your contest prize?

[char1iecha1k]

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

[manavo11]

Well, good luck with it char1iecha1k :thumb:

[Merri]

BTW Merri, don't you want your contest prize?

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.

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?

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 :)

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.

[manavo11]

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.

Oh well, if you change your mind let me know :)

[dglienna]

Alternate Blue and White to match the sky in your new avatar :) :thumb:

[ntg]

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.

[NotLKH]

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

[dukuso]

I don't think so. Entered code will be available after the contest ends. It will be a learning experience for everyone, and things can continue after it ends. The thread was started before the contest was even brought up.


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 ?

[eyeRmonkey]

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 (http://blanchardjeremy.com). <3