Printable View
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.
:eek: Somebody please format this guy's hard disk :afrog:Quote:
Originally Posted by Merri
Yea :D, good idea :)Quote:
Originally Posted by ntg
I use fixed sized arrays, single dimensional array, and precalculated values, and all the "tricks" i can think of to make it fast, but I still can't get to work at the speeds Merri posted.... the fastest I got was like 0.3 milliseconds (that's 0.0003 seconds), but his speeds I see like 0.02 milliseconds... how the hell is that possible :confused: :confused:
Can't tell or we'll all post the same code :D I don't even dare to post a tip, because any tip I could give would be an instant "AHA! GOTCHA!"... this is a contest after all :)
I have just been introcuced to Sudoku, wrote a simple solver in tcl/tk on a Mac powerbook. All the puzzles presented by Lou are VERY easy. The hardest puzzles I have seen sofar (and my solver can solve them all) are those given atQuote:
Originally Posted by NotLKH
http://www.setbb.com/phpbb/viewtopic...&mforum=sudoku
Hubert
Here are the hardest attached in the file format we are using in the contest. It takes four seconds for my solver to complete all 337. However, there are only six which take more than 100 ms (one takes even over 300 ms). There are a few which are very easy as well (ie. didn't require backtracking).
I can solve these 337 in 196 ms but I need 0.14ms for your
023_0837_XXXX__SOD_MASKED.msk.
Well, you specialized on the easy ones !
this is with 2600MHz. What computer do you use ?
I have a 1800 MHz Athlon XP-M 2200+
Guess I should start coding more logic to my code, only three weeks to go. Have done some reading and it looks like there is no good single logic that could be used.
I'm not sure about the rules, it seems that you needn't solve all puzzles.
So maybe it's sufficient and a good strategy to specialize on the
easy ones, which are the vast majority, statistically.
I do use "single logic" , BTW.
dukuso, the main goal is to solve as many as possible. Speed is the secondary factor...
but will there be enough time to solve all puzzles or are contestants
expected to pick the easy ones ?
lol.
Even IF the entrents were "picking" which ones to solve {Which they're not}, how would they know which are the easy ones until they solve them?
:wave:
-Lou
I don't understand... :confused:Quote:
Originally Posted by dukuso
Hehe, I guess he is meaning that we would be solving every possible sudoku there is :D
Anyways, now I'll be getting into the real thing I'm posting for: the contest rules need clarifying. It seems to be unclear what will be timed. Thus some requests:
- It seems that we must clear an array, load a file and solve the sudoku and that this will be timed.
- It would make much more sense if only solving the sudoku would be timed (what if harddisk happened to get busy while loading a sudoku, causing a major slow down to one or more of the contestants?).
- I'm not clearing an array, because when I load a file, I just fill the array according to the file contents (ie. no point clearing it, just slowing down).
- There is no output format defined! My primary suggestion is a Long Array defined to have 81 items (0 To 80) with values from 1 to 9. A secondary suggestion would be a byte array, like SudokuBoard(1 To 9, 1 To 9) where first dimension is Y and second dimension X.
- I also suggest this array to be used as the input array to the solver function. The file loader would then fill the array.
Clearing the array is just an assumption I made that you would have to based on my solver I had made (the way it worked, far from optimized). It's not needed to clear/redim the array, you can load the file in a sub and fix the array in there.Quote:
Originally Posted by Merri
I should have clarified, that's what I was planning to do... Only the solving sub will be timed, not the loading or displaying part.Quote:
Originally Posted by Merri
Use whatever you like, as long as you have a sub that shows the results so we can visually see the solved sudoku somehow (your choise).Quote:
Originally Posted by Merri
as I understand the rules, contestants will be given a set of sudokus,Quote:
Originally Posted by manavo11
maybe similar to the posted one (?), and they will have to solve
them within some time-limit.
When time has elapsed, the correctly solved puzzles are counted.
When the solver finishes before the time has elapsed, then
this time counts in case of a tie.
correct ?
The codes will be submitted to a tester, who then uses a range of sudokus (not known by the contestants beforehand) which he tests for each code. The winner is primarily determined by the number of solved sudokus, if there is a tie then by speed.
so, would it make sense, if your solver rejects the hard ones or not ?
I mean, you can't know in advance whether you will have enough time
to finish all puzzles , can you ?
So pick the easy ones, while putting the hard ones on some stack,
only to be considered again once you still have time after
finishing the easy ones, etc.
OMG... what's so difficult to understand ?
The tester will get lets say 50 sudokus. Then he will test thouse 50 with one contestant, he gets how many was solved, and the total time. Then he tests the SAME 50 sudokus on the next contestant, he writes down how many was solved, and the speed, and so on...
The winner will be that has the MOST Sudokus solved, if there's a tie (i.e. someone has the same number of sudokus solved as someone else) then the winner is the one that has the fastest time.
I'm telling you now, that my solver will solve ALL the sudokus, how fast it will solve, that's another story... I'm sure it won't be faster than Merri's solver, and I'm sure that Merri's solver will solve ALL the sudokus also...
So if you decide so "pick" the ones that you want to solve, then you will lose the contest FOR SURE.
Ok. Here's some more new ones.
Again, if any of you find I screwed up, by finding more than one solution, please tell me so I can address this porblem.
:wave:
-Lou
No real big changes to my old code, but it can now solve the hardest set in about 2780 ms. NotLKH's newest set solved in about 260 ms. I've a yet-another-code in the works which is supposed to be able to solve all by pure logic... however, I'm not sure if the logic I've thought for it is valid. I also don't know if I have the time to complete it before the contest deadline, because I started up a new site a week ago and it is still under construction, yet have become the most popular site I administrate.