-
Jul 25th, 2005, 04:58 PM
#1
-
Jul 25th, 2005, 09:18 PM
#2
Lively Member
Re: Contest 6 - Sudoku solver - Discussion
Where can we find any patterns to test our progies against?
Know of any good ones??
-
Jul 25th, 2005, 09:21 PM
#3
-
Jul 25th, 2005, 09:37 PM
#4
Lively Member
Re: Contest 6 - Sudoku solver - Discussion
Have you tried their evil level?
Too bad I don'thave VBnet at home.
Still, did you try my submission?
-Lou
-
Jul 25th, 2005, 09:40 PM
#5
-
Jul 25th, 2005, 09:48 PM
#6
-
Jul 27th, 2005, 11:22 PM
#7
Re: Contest 6 - Sudoku solver - Discussion
Originally Posted by Something Else
No.
By submission, I meant the pattern I posted, ie...:
Good for a speed test for all!
I finished my Sudoku solver, and it works PERFECTLY, it solved ALL the puzles I gave it too...
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
-
Jul 28th, 2005, 12:02 AM
#8
-
Jul 28th, 2005, 05:24 AM
#9
Lively Member
Re: Contest 6 - Sudoku solver - Discussion
Originally Posted by CVMichael
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
I made it.
-Lou
-
Jul 25th, 2005, 09:58 PM
#10
-
Jul 25th, 2005, 11:57 PM
#11
Re: Contest 6 - Sudoku solver - Discussion
Do you want us to place the timer code within our own code, or will you do that yourself?
-
Jul 26th, 2005, 11:01 AM
#12
-
Jul 26th, 2005, 03:53 AM
#13
Re: Contest 6 - Sudoku solver - Discussion
Originally Posted by manavo11
The class located here will be used to time the entries.
I suppose place that in our own code.
-
Jul 26th, 2005, 04:11 AM
#14
Re: Contest 6 - Sudoku solver - Discussion
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:
Sub Solve(filePath as string)
Sub DisplayResults()
And thats it. All the timing code would be put into the Judge's program and not the contestants code.
I don't live here any more.
-
Jul 26th, 2005, 11:03 AM
#15
-
Jul 26th, 2005, 11:44 AM
#16
Re: Contest 6 - Sudoku solver - Discussion
I want in !
How do I enter the contest ?
Or do I just post the code and that's it ?
-
Jul 26th, 2005, 04:21 AM
#17
Re: Contest 6 - Sudoku solver - Discussion
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?
-
Jul 26th, 2005, 04:32 AM
#18
Re: Contest 6 - Sudoku solver - Discussion
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.
Last edited by Merri; Jul 26th, 2005 at 04:45 AM.
-
Jul 26th, 2005, 05:11 AM
#19
Re: Contest 6 - Sudoku solver - Discussion
Format conversions? Its loading a file and extracting a few numbers. What hard about that?
I don't live here any more.
-
Jul 26th, 2005, 05:31 AM
#20
Re: Contest 6 - Sudoku solver - Discussion
Load()
'StartTimer
Solve()
'StopTimer
Display()
I don't live here any more.
-
Jul 26th, 2005, 02:01 PM
#21
Fanatic Member
Re: Contest 6 - Sudoku solver - Discussion
You know what's funny?? My brother wrote one a few months ago. It works too!
-
Jul 28th, 2005, 08:12 AM
#22
Fanatic Member
Re: Contest 6 - Sudoku solver - Discussion
I cant even solve this puzzles on paper, nevermind programming a computer to do it, so i think i wont enter.
-
Jul 28th, 2005, 09:33 AM
#23
Re: Contest 6 - Sudoku solver - Discussion
Originally Posted by x-ice
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...
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...
-
Jul 28th, 2005, 09:44 AM
#24
Re: Contest 6 - Sudoku solver - Discussion
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:
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
What do you think ?
This way it is easy to plug the class in the tester application (for whoever does the testing)
-
Jul 28th, 2005, 10:03 AM
#25
Re: Contest 6 - Sudoku solver - Discussion
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?)
-
Jul 28th, 2005, 12:29 PM
#26
Re: Contest 6 - Sudoku solver - Discussion
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!}
-
Jul 28th, 2005, 12:42 PM
#27
Re: Contest 6 - Sudoku solver - Discussion
Originally Posted by mendhak
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?)
My program does not do ANY guessing at all...
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...)
-
Jul 29th, 2005, 04:33 AM
#28
Re: Contest 6 - Sudoku solver - Discussion
Originally Posted by CVMichael
My program does not do ANY guessing at all...
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...)
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...
Or maybe you should hope that I've got my facts wrong.
-
Jul 29th, 2005, 05:14 AM
#29
Re: Contest 6 - Sudoku solver - Discussion
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.
-
Jul 28th, 2005, 01:33 PM
#30
Re: Contest 6 - Sudoku solver - Discussion
http://www.vbforums.com/showthread.p...27#post2102227
test your apps, thanks to NotLkh, our local maths expert.
Pino
-
Jul 29th, 2005, 06:01 AM
#31
Re: Contest 6 - Sudoku solver - Discussion
I guess his definition of guessing is different.
-
Jul 29th, 2005, 08:19 AM
#32
Re: Contest 6 - Sudoku solver - Discussion
Originally Posted by mendhak
I guess his definition of guessing is different.
I guess so...
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...
-
Jul 29th, 2005, 06:03 AM
#33
Re: Contest 6 - Sudoku solver - Discussion
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..
-
Jul 29th, 2005, 08:21 AM
#34
Re: Contest 6 - Sudoku solver - Discussion
Originally Posted by mendhak
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..
269175438
471832965
583694217
715426389
894317526
326958741
942561873
138749652
657283194
Solved in 0.0339 seconds... (In the IDE), in 675 iterations...
-
Jul 30th, 2005, 03:31 PM
#35
Re: Contest 6 - Sudoku solver - Discussion
Originally Posted by CVMichael
269175438
471832965
583694217
715426389
894317526
326958741
942561873
138749652
657283194
Solved in 0.0339 seconds... (In the IDE), in 675 iterations...
I'm impressed.
-
Jul 29th, 2005, 10:42 AM
#36
Re: Contest 6 - Sudoku solver - Discussion
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
Please clarify.
-
Jul 30th, 2005, 06:32 PM
#37
Re: Contest 6 - Sudoku solver - Discussion
Originally Posted by kaffenils
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
Please clarify.
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.
Has someone helped you? Then you can Rate their helpful post.
-
Jul 31st, 2005, 04:02 PM
#38
Hyperactive Member
Re: Contest 6 - Sudoku solver - Discussion
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
Last edited by jo0ls; Jul 31st, 2005 at 04:05 PM.
-
Jul 31st, 2005, 07:05 PM
#39
Re: Contest 6 - Sudoku solver - Discussion
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...
-
Aug 1st, 2005, 08:19 AM
#40
Re: Contest 6 - Sudoku solver - Discussion
What's the timing class to be used for VB.Net?
The problem:
Code:
..9..5...
47...2...
.836.4.1.
.15....8.
...3.7...
.2....74.
.4.5.187.
...7...52
...2..1..
is solved pretty quickly. How are you guys doing on other problems like this one:
Code:
.........
9.....1.7
...718...
2........
..5.8...3
..6.49.18
.18......
.6..3..74
...9...3.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|