This thread is to post any questions you have about the 6th contest :)
Printable View
This thread is to post any questions you have about the 6th contest :)
Where can we find any patterns to test our progies against?
Know of any good ones??
:wave:
Your program? ;)
Or www.websudoku.com :)
Have you tried their evil level?
Too bad I don'thave VBnet at home.
Still, did you try my submission?
:wave:
-Lou
I've tried it, my attempt at creating a solver is limited to solving some of the hard ones, so I would have to work on it more :)
By submission you mean the creator/solver in the Games section?
No.
By submission, I meant the pattern I posted, ie...:
http://www.vbforums.com/attachment.p...id=38856&stc=1
Good for a speed test for all!
:wave:
I'll give it a shot tomorrow :) Thanks for the suggestion :thumb:
Do you want us to place the timer code within our own code, or will you do that yourself?
I suppose place that in our own code.Quote:
Originally Posted by manavo11
Oh dear, this seems to be vague doesn't it.
We should only have to submit a class nothing more. A class that implements an interface that is given to everyone.
Then all the judges would have to do to test each entry is to add all the classes to one large project and then call each one in turn, that would be 100% fair then.
The interface should have 2 methods:
VB Code:
And thats it. All the timing code would be put into the Judge's program and not the contestants code.
That's a good idea. Give us interfaces for each language (I don't know whether C# can implement VB.NET interfaces or vice versa) and we submit the class. However I think the timing code should maybe be placed in the class as otherwise you time calling the method as well. What do you think?
You can't ask for everything; I rather code this simple thing 100% myself ;) Especially because that way I can have the data in the format I want and I don't need to use CPU time to convert to some certain format.
What we time when we use an interface:
- raw data to the format programmer wants to
- preprocessing of the data (optimizations etc.)
- the actual algorithm
- after processing: converting to the required format by the interface
The very very bad thing about this is that it costs a lot of time to do the format changes; the algorithm can be superfast, yet the conversions might take time.
Without an interface, we just would time the actual algorithm. A file loader could do the loading of data and preprocessing (ie. prepare used arrays and variables) directly to the format programmer wants. These almost always take the same amount of time no matter what kind of puzzle we have, so there is no point benchmarking these and letting them effect the results.
I hated it in Prime Numbers contest that displaying of data was included in the benchmark... I never saw any point optimizing listbox item adding.
Format conversions? Its loading a file and extracting a few numbers. What hard about that?
Load()
'StartTimer
Solve()
'StopTimer
Display()
Would be nice if you could include it... I know that it's VB6 but I remember you had a VB.Net version, I'll look for it. I don't have a C# one though, just thought of that :(Quote:
Originally Posted by mendhak
Since I can't make for all of them, just make it like the prime numbers contest, a project...Quote:
Originally Posted by wossname
I want in ! :D
How do I enter the contest ?
Or do I just post the code and that's it ?
You know what's funny?? My brother wrote one a few months ago. It works too!
I finished my Sudoku solver, and it works PERFECTLY, it solved ALL the puzles I gave it too...Quote:
Originally Posted by Something Else
698217543
412358679
357649218
749865321
263174895
581932467
934521786
876493152
125786934
Time taken: 134.911 seconds (On a P4, 1400 MHz)
Where did you get that puzle by the way ?
I tested my solver with puzles from here: http://www.websudoku.com/?select=1&level=4 at Evil level, and I never had one greater than 1 second to solve...
When i pluged in your puzle I thought there is something wrong with my solver :D
HAHA :D :D :D :D The funiest thing !!!
I forgot to load a puzzle, the puzzle was empty, and I clicked on "Solve" button, it solved to this:
123456789
456789123
789123456
214365897
365897214
897214365
531642978
642978531
978531642
Time Taken: 1.62140719001996E-02 (0.0162 Seconds)
I made it.Quote:
Originally Posted by CVMichael
:wave:
-Lou
I cant even solve this puzzles on paper, nevermind programming a computer to do it, so i think i wont enter.
That's one thing I love about programming... you program what you want it to do, and it does it for you...Quote:
Originally Posted by x-ice
If the computer took 135 seconds, then probably it will take DAYS for a person to do...
Even the simplest one takes quite a long time.
I did not solve any puzzle on paper. On paper it's even more difficult...
I did solve a few puzzels on http://www.websudoku.com at easy level, but for every number i put in i clicked on "How am I doing?" button... without that button it would take a loooonnnggg time to do it...
Did anyone else finish the Sudoku solver ?
Kuz I finished, and it's working, but I'm wondering why no one posted in the submissions forum ?
Did anyone decide how the interface will be ?
I agree with wossname that we should submit a class...
These are the methods I suggest to be public in the class:
What do you think ?Code:Function SolveSudoku(Puzzle As String) As Boolean
the puzzle should be a string like:
...8.....
..9....68
.8.6.75.3
....2...4
6.4...8.1
5...3....
8.52.3.9.
46....2..
.....1...
And returns True if it was able to solve it
Function ToString() As String
That returns the solved puzzle as string like:
356814972
749352168
182697543
938126754
624975831
571438629
815263497
463789215
297541386
This way it is easy to plug the class in the tester application (for whoever does the testing)
Are you guys taking care of the difficult sudoku problems as well? I'm sure you're aware that the higher levels involve some guessing and backtracking, how are you taking care of that? (Also, are you taking care of that?)
For anyone who doesn't know it yet, you can find some sample tests HERE
and their corresponding solutions HERE
BTW,
CVMichael has posted his times in THIS THREAD
{Good Job, BTW!}
:wave:
My program does not do ANY guessing at all...Quote:
Originally Posted by mendhak
And that does not make any sence to me.... your saying I should pick the numbers randomly, and see if they are valid ? that takes an eternety to finish solving (IF it solves at all)
My program is a recursive function (and some small functions), together is 158 lines (only the solver part, no loading and saving...)
http://www.vbforums.com/showthread.p...27#post2102227
test your apps, thanks to NotLkh, our local maths expert.
Pino
That's interesting how you got it solved then, because I believe that the toughest sudoku puzzles cannot be solved simply by logic, but involve guessing and backtracking...Quote:
Originally Posted by CVMichael
Or maybe you should hope that I've got my facts wrong.
What he does IS guessing. He described in the other topic that he tries a number and then sees if it is valid.
Guessing is also known as brute force.
I guess his definition of guessing is different. :p
Guys, please try this sudoku puzzle as well:
Code:..9..5...
47...2...
.836.4.1.
.15....8.
...3.7...
.2....74.
.4.5.187.
...7...52
...2..1..
I guess so... :)Quote:
Originally Posted by mendhak
But the numbers I try are not random, I make a list of available numbers (that are not used horizontally and vertically, then I try those numbers...
269175438Quote:
Originally Posted by mendhak
471832965
583694217
715426389
894317526
326958741
942561873
138749652
657283194
Solved in 0.0339 seconds... (In the IDE), in 675 iterations...
I'm a bit confused about what the judges expect me to submit. Is it just the solver class/module or is it a full application that loops through sudokus, solves them, times it and displays the result and time used? Should I write the solution back to the original sudoku files or just display it on the screen? Should I write the timing results to a log file or to a listbox on the form?
I'm confused :confused:
Please clarify.
At this moment, you just make a program with a function that solves the sudoku. You can load a file before that (so it can be counted out of the timing). Everything else is voluntary; I've done benchmarking and all kinds of other things to my program. A few guys are trying to push the class idea, but I think it is more confusing.
I'm impressed.Quote:
Originally Posted by CVMichael
Create a project (not just a class) that solves sudokus. In there it would be nice for us if you included the timing code as well, if you want. And it's probalby for the best for you to have a loading sub to read files like we show in the description thread of the contest.Quote:
Originally Posted by kaffenils
Hmm, I've already got one on planetsourcecode. No stealing lol. Actually the brute force method I added was converted from someone elses C code, but the rules based solver is my own work.
for this grid mentioned above:
..9..5...
47...2...
.836.4.1.
.15....8.
...3.7...
.2....74.
.4.5.187.
...7...52
...2..1..
rules solver does it in about 700ms (I've not done an average of a few runs).
brute forced in 7 ms (athlon fx55 though...)
The rules based solver is definately NOT optimised for speed. I'd have to start from scratch to optimise it.
Rules based solving tries to solve more like a human. You start will all squares being able to be any number 1-9, then eliminate possibilities based on rules, such as "if a number is known for sure in a square, then eliminate it as a possibility from all squares in its row, column and block...". You then churn through the rules repeatedly until it is (hopefully) solved.
Brute force will make guesses and check if the grid is valid, if it is invalid then it will go back to a saved state and guess again. There is a sudoku programmers forum with lots of discussion on rules based solving.
timing code:
Code:Dim starttime, endtime As Date
Dim elapsedtime As TimeSpan
starttime = Now
----Call solving sub----
endtime = Now
elapsedtime = endtime.Subtract(starttime)
Dim millisecs As Long = elapsedtime.Milliseconds
Actually, for me it's the other way around, the rules solver is the fastest, under a millisecond, and the brute force one takes the longest up to 6-7 seconds...
What's the timing class to be used for VB.Net?
The problem:
is solved pretty quickly. How are you guys doing on other problems like this one:Code:..9..5...
47...2...
.836.4.1.
.15....8.
...3.7...
.2....74.
.4.5.187.
...7...52
...2..1..
Code:.........
9.....1.7
...718...
2........
..5.8...3
..6.49.18
.18......
.6..3..74
...9...3.
Solved it in 0,21 ms. Reposting this one in this topic:
Humm... my code seems to have distorded a bit, it used to take "only" 200 ms on this one, now it takes about 400 ms. Have to check it after I've slept. This code is so slow for me due to one reason: it effectively acts as the "worst case scenario" for the backtracking code I use to solve the ones the pure logic code can't handle.Code:wallyb.txt:
..2.9.1.7
.386.....
4........
.....5...
..9.1.3..
...4.....
........4
.....792.
8.6.3.7..
Edit Duh, silly of me! Should remember NOT to run benchmarking in power saving mode :D Now gives me 190 ms.
What's the problem with that one ?Quote:
Originally Posted by ntg
871394652
943526187
652718349
284153796
195687423
736249518
318472965
569831274
427965831
It solved in 0.000467 Seconds
That's interesting...quite a result. My initial result for that is 155,6ms so achieving time under 1ms seems very good. I'm not on my primary PC right now and I got that result with a P4 1.7 Ghz. Out of curiosity, what's the configuration you used to get the result (processor, VB6/VB.Net, Debug/Release, IDE/Commandline)?Quote:
Originally Posted by CVMichael
I understand that the total time it takes to solve a number of sodukus will be the actual winning factor since I guess that most people's algorithms will solve all sodukus. I'm just wondering here...but if the benchmarking box is hyperthreaded wouldn't a threading solution perform better than a single-threaded one for lots of sodukus?
I still don't see the timing class to be used for VB.Net solutions.
It solved it using LOGIC only... maybe your missing some rules in your program...Quote:
Originally Posted by ntg
My configuration: P4, 1.4 GHz, VB6, Compiled with ALL optimizations, And by all optimizations, I mean this:
Well, I'm not up to building msk files like Merris last one yet, although given a day or two {where My car doesn't break down, go into shop, or I'm sitting around waiting for the phone to ring telling me that its fixed, while I'm busy trying to shuttle back and forth between work & home to care for my bedridden mom} I could incorporate that. Propably next weekend.
But I tweaked my generator a little bit more. Theoretically, if you know the proper strategies, you can, so far, solve any of mine without any brute force.
So, attached are a few more patterns for you to play with. Please inform me if I've screwed up and made invalid patterns.
:wave:
-Lou
This : http://www.mentalis.org/soft/class.qpx?id=8Quote:
Originally Posted by ntg
Yeah, you're right. A small adjustment brought it down to 10ms...although I don't think I'll see anything close to 1ms. I'm using VB.Net and a class-based solution (no plain arrays or structures) so that's going to incur some performance penalty.Quote:
Originally Posted by CVMichael
I've fooled around a bit and I think that the benchmarking box could make a difference after all. For the patterns posted by Pino, threading isn't worth the trouble because the respective solutions are calculated very fast on a single thread. The patterns posted by NotLKH are a different story - a hastily written threading solution is 15% faster than a single threaded one using the same algorithm (with hyperthreading processor - if you force the process affinity for one CPU only, the performance gain drops below 2%).
Thanks manavo11. Fun contest, too. :thumb:Quote:
Originally Posted by manavo11
I'm not sure, but I think Pino's are NotLKH's first round of patterns, and what you are referring to as NotLKH's are his second round of patterns.Quote:
Originally Posted by ntg
If so, it sounds like NotLKH is evolving along pretty good?
:wave:
-Lou
0,023187 ms: 023_0837_XXXX__SOD_MASKED.msk
(or 0,000023 seconds)
Some of NotLKH's sudokus are too easy :D In the other hand it is good to test the easy ones too, that is one of the things that make the difference when the final tests are done.
Hardest for my solver in NotLKH's newest set:
147,824374 ms: 023_0807_XXXX__SOD_MASKED.msk
(or 0,147823 seconds)
Total time to solve all 532 sudokus: 1,695153 seconds
Is "," the same as a decimal point?Quote:
Originally Posted by Merri
If so, can I see the code you use for timing to .000023 seconds {23 thousandths of a millisecond, oops, forgot the furthur 187 points of accuracy beyond thousandths of a thousandth}, merri?
:wave:
-Lou
It is the same which has been linked to in the first post: sTime.cls
I also use this code to display the results, so I don't get the weird +E or -E business:
VB Code:
3 of my hardest 9*9:
....1.78.5....9..........4..26.........6....3.74.8.........3..2.8..4..1.6..5.....
.2..........6....3.74.8.........3..2.8..4..1.6..5.........1.78.5....9..........4.
6...4...3.1.....7...5...8.....5.2...3...9...2...1.3.....8...9...7.....5.2...3...4
NotLKH's second 532 puzzles list now solved within 900 ms. Optimization is such a cool thing.
0.091 sec. with 2.6GHz for that 532-set.
But it's in C, I don't know about VB, is it much slower than C ?
Another suggestion : transform the puzzles randomly by one of the
9!*6^8*2 equivalence transformations, since many solvers heavily depend
on the order of rows,columns in which the puzzle is processed.
The nature of the language is different, but I don't believe there is much diffence in this task: VB6 compiler is a hacked C compiler. My "poor" result is due to the fact the harder ones require backtracking, as I haven't yet bothered to code a good logical solver. Some easier ones are solved lightning fast thanks to the optimized basic logic.
then I don't understand why you wrote earlier that you can't easily adaptQuote:
Originally Posted by Merri
it for larger sudokus like 16*16 etc. ?
My solver is just an exact-cover solver, so I needn't bother about
all these "sudoku-rules".
Because it is highly optimized already: I use fixed size arrays and precalculated values. Also, VB is slow with multidimensional arrays, so I use one dimensional array. If the contest required different sized sudokus, then I'd code it flexible. But that'd require changing quite many values and doing some light extra math and so on.