Contest 6 - Sudoku solver - Discussion

[manavo11]

This thread is to post any questions you have about the 6th contest :)

[Something Else]

Where can we find any patterns to test our progies against?
Know of any good ones??

:wave:

[manavo11]

Your program? ;)

Or www.websudoku.com :)

[Something Else]

Have you tried their evil level?
Too bad I don'thave VBnet at home.
Still, did you try my submission?

:wave:
-Lou

[manavo11]

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?

[Something Else]

No.
By submission, I meant the pattern I posted, ie...:

http://www.vbforums.com/attachment.php?attachmentid=38856&stc=1

Good for a speed test for all!

:wave:

[manavo11]

I'll give it a shot tomorrow :) Thanks for the suggestion :thumb:

[mendhak]

Do you want us to place the timer code within our own code, or will you do that yourself?

[penagate]

The class located here (http://www.vbforums.com/showpost.php?p=1783665&postcount=52) will be used to time the entries.

I suppose place that in our own code.

[wossname]

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:

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.

[penagate]

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?

[Merri]

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.

[wossname]

Format conversions? Its loading a file and extracting a few numbers. What hard about that?

[wossname]

Load()
'StartTimer
Solve()
'StopTimer
Display()

[manavo11]

Do you want us to place the timer code within our own code, or will you do that yourself?

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

[manavo11]

We should only have to submit a class nothing more. A class that implements an interface that is given to everyone.

Since I can't make for all of them, just make it like the prime numbers contest, a project...

[CVMichael]

I want in ! :D

How do I enter the contest ?

Or do I just post the code and that's it ?

[nkad]

You know what's funny?? My brother wrote one a few months ago. It works too!

[CVMichael]

No.
By submission, I meant the pattern I posted, ie...:

http://www.vbforums.com/attachment.php?attachmentid=38856&stc=1

Good for a speed test for all!

:wave:

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

[CVMichael]

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)

[Something Else]

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

I made it.
:wave:
-Lou

[x-ice]

I cant even solve this puzzles on paper, nevermind programming a computer to do it, so i think i wont enter.

[CVMichael]

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

[CVMichael]

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:

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)

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

[NotLKH]

For anyone who doesn't know it yet, you can find some sample tests HERE (http://www.vbforums.com/attachment.php?attachmentid=38964)
and their corresponding solutions HERE (http://www.vbforums.com/attachment.php?attachmentid=38965)

BTW,
CVMichael has posted his times in THIS THREAD (http://www.vbforums.com/showthread.php?t=343163&page=2)

{Good Job, BTW!}

:wave:

[CVMichael]

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

[Pino]

http://www.vbforums.com/showthread.php?p=2102227#post2102227

test your apps, thanks to NotLkh, our local maths expert.

Pino

[mendhak]

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.

[Merri]

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.

[mendhak]

I guess his definition of guessing is different. :p

[mendhak]

Guys, please try this sudoku puzzle as well:


..9..5...
47...2...
.836.4.1.
.15....8.
...3.7...
.2....74.
.4.5.187.
...7...52
...2..1..

[CVMichael]

I guess his definition of guessing is different. :p
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...

[CVMichael]

Guys, please try this sudoku puzzle as well:


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

[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 :confused:

Please clarify.

[Merri]

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.

[mendhak]

269175438
471832965
583694217
715426389
894317526
326958741
942561873
138749652
657283194

Solved in 0.0339 seconds... (In the IDE), in 675 iterations...
I'm impressed.

[manavo11]

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.

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.

[jo0ls]

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:

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

[CVMichael]

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

[ntg]

What's the timing class to be used for VB.Net?

The problem:
..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:
.........
9.....1.7
...718...
2........
..5.8...3
..6.49.18
.18......
.6..3..74
...9...3.

[Merri]

Solved it in 0,21 ms. Reposting this one in this topic:

wallyb.txt:
..2.9.1.7
.386.....
4........
.....5...
..9.1.3..
...4.....
........4
.....792.
8.6.3.7..

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.


Edit Duh, silly of me! Should remember NOT to run benchmarking in power saving mode :D Now gives me 190 ms.

[CVMichael]

How are you guys doing on other problems like this one:
.........
9.....1.7
...718...
2........
..5.8...3
..6.49.18
.18......
.6..3..74
...9...3.
What's the problem with that one ?

871394652
943526187
652718349
284153796
195687423
736249518
318472965
569831274
427965831

It solved in 0.000467 Seconds

[ntg]

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

[ntg]

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.

[CVMichael]

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)?
It solved it using LOGIC only... maybe your missing some rules in your program...

My configuration: P4, 1.4 GHz, VB6, Compiled with ALL optimizations, And by all optimizations, I mean this:

[NotLKH]

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

[manavo11]

What's the timing class to be used for VB.Net?

This : http://www.mentalis.org/soft/class.qpx?id=8

[ntg]

It solved it using LOGIC only... maybe your missing some rules in your program...
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.

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

This : http://www.mentalis.org/soft/class.qpx?id=8
Thanks manavo11. Fun contest, too. :thumb:

[Something Else]

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

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.

If so, it sounds like NotLKH is evolving along pretty good?

:wave:
-Lou

[Merri]

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

[Something Else]

0,023187 ms: 023_0837_XXXX__SOD_MASKED.msk
(or 0,000023 seconds)

Is "," the same as a decimal point?

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

[Merri]

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:

Format$(Q.RetTime * 1000, "0.000000") & " ms"

[dukuso]

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

[Pino]

Update -

http://www.vbforums.com/showthread.php?p=2107653#post2107653

[Merri]

NotLKH's second 532 puzzles list now solved within 900 ms. Optimization is such a cool thing.

[dukuso]

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.

[Merri]

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.

[dukuso]

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

[Merri]

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.

[ntg]

NotLKH's second 532 puzzles list now solved within 900 ms. Optimization is such a cool thing.
:eek: Somebody please format this guy's hard disk :afrog:

[CVMichael]

:eek: Somebody please format this guy's hard disk :afrog:
Yea :D, good idea :)

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:

[Merri]

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

[hhalkin]

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

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 at

http://www.setbb.com/phpbb/viewtopic.php?t=132&mforum=sudoku

Hubert

[Merri]

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

[dukuso]

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 ?

[Merri]

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.

[dukuso]

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.

[manavo11]

dukuso, the main goal is to solve as many as possible. Speed is the secondary factor...

[dukuso]

but will there be enough time to solve all puzzles or are contestants
expected to pick the easy ones ?

[NotLKH]

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

[manavo11]

but will there be enough time to solve all puzzles or are contestants
expected to pick the easy ones ?
I don't understand... :confused:

[Merri]

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.

[manavo11]

- It seems that we must clear an array, load a file and solve the sudoku and that this will be timed.

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.

- 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 should have clarified, that's what I was planning to do... Only the solving sub will be timed, not the loading or displaying part.

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

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

[dukuso]

I don't understand... :confused:

as I understand the rules, contestants will be given a set of sudokus,
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 ?

[Merri]

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.

[dukuso]

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.

[CVMichael]

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.

[NotLKH]

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

[Merri]

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 (http://www.mozilla.fi) a week ago and it is still under construction, yet have become the most popular site I administrate.

[dukuso]

70ms(1GHz) for the 123 from msk_003.
Not sure what you mean by "pure" logic, but it seems that
"mixed" logic (logic+backtracking) is faster (and easier)

[ntg]

Just curious people...what's your solution for this one?
6....2...
.4.....3.
...89..2.
..5...389
....3.5..
9....1...
42.68.7..
..71..89.
.........

[ntg]

BTW, I think that the following code of the StopWatch class needs to be revised.

'/// <summary>
'/// Returns the time that has passed since the Reset() method was called.
'/// </summary>
'/// <remarks>The time is returned in tenths-of-a-millisecond.
'/// If the Peek method returns '10000', it means the interval took exactely
'/// one second.</remarks>
'/// <returns>A long that contains the time that has passed since the
'/// Reset() method was called.</returns>
'/// <exception cref="NotSupportedException">The system does not
'/// have a high-resolution performance counter.</exception>
Public Function Peek() As Long
Return CType((((GetValue() - StartTime) / CType(Frequency, Double)) * 10000), Long)
End Function
Like the comments indicate, this will give you an accuracy up to 1/10 of a msec. The cast to long incurs rounding and it should be a cast to double.
Public Function Peek() As Double
Return CType((((GetValue() - StartTime) / CType(Frequency, Double)) * 10000), Double)
End Function
Any arguments?

[CVMichael]

Just curious people...what's your solution for this one?
6....2...
.4.....3.
...89..2.
..5...389
....3.5..
9....1...
42.68.7..
..71..89.
.........

My solver could not solve by logic only, took some time

689342175
542716938
173895624
215467389
764938512
938251467
421689753
357124896
896573241

Time 203.59 Milliseconds

[ntg]

It's not a question of timing...what's wrong with this solution?
693452178
842716935
751893624
165247389
274938561
983561247
429685713
537124896
816379452

[CVMichael]

Do you guys know some web-sites that show some logic rules for Sudoku ?
I've been using this one: Sudoko Solver by Logic (http://www.sudokusolver.co.uk/), but I don't know how to implement the complicated ones, and the solver on that website does not solve all sudokus by logic.
I'm wandering if there are more logic rules than that ?

[CVMichael]

It's not a question of timing...what's wrong with this solution?
693452178
842716935
751893624
165247389
274938561
983561247
429685713
537124896
816379452

693452178
842716935
751893624
165247389
274938561
983561247
429685713
537124896
816379452

The 8 is 2 times in the first vertical line

Edit
I modified the "guessing" part of my solver so that it does not return right away when it finds the first valid result. This way it finds ALL valid solution. But it found only one for this puzzle...

[ntg]

693452178
842716935
751893624
165247389
274938561
983561247
429685713
537124896
816379452
:blush:

[CVMichael]

ntg, don't you have a function to check if it's solved/valid ?

That's the first thing I did :)

[ntg]

Yeah, and it had a index-related bug:mad:. Fixed it now and I'm quite surprised that all other puzzles that've been posted here are solved correctly as were reported by that method.:bigyello:

Seems that I had my glitch for today (2 bad it's Sunday). This result came out of a rule I added but forgot to add inconsistency checking. It now gives the same result as that you've posted - big thanks CVMichael.

[CVMichael]

ntg, you gave me a briliant idea :)

In the previous post I was saying I made it find more than one solution...

I put "1" in the grid in the first cell, and I clicked on "Solve", i'ts giving me about 1000 solutions per second :D
I'm curious to see when it stops, it will probably be a few million solutions :D

[ntg]

All sudokus are 6,670,903,752,021,072,936,960. I think that if you set a cell to 1, you'll get 72^2 × 2^7 × 27,704,267,971 different solutions. If that's so, don't hold your breath waiting for the program to end. ;)

[CVMichael]

All sudokus are 6,670,903,752,021,072,936,960. I think that if you set a cell to 1, you'll get 72^2 × 2^7 × 27,704,267,971 different solutions. If that's so, don't hold your breath waiting for the program to end. ;)
That's good to know.... I was turning red... :D

Hmmm... that means that a Long type cannot even hold the count... I better stop it now

[Merri]

Save each solution to your hardisk in the contest format! 97 bytes * 27704267971 = a bit less than 2,45 terabytes :)


On the other news... I managed to speed up the solving of "next to very easy", which dropped the total time a little:

NotLKH1, 69 files: ~35 ms -> 0,5 ms per file
NotLKH2, 532 files: ~665 ms -> 0,8 ms per file
NotLKH3, 123 files: ~240 ms -> 1,95 ms per file
Hardest, 337 files: ~2600 ms -> 7,7 ms per file

Still running the very same logic I've used all the time since I combined my basic rules solver and my backtracker... only optimized the use of variables. However, I'm planning on adding more logic to this code as I probably don't have the time to figure out a new logic solver.

Also, as you can see, NotLKH is managing to improve his generator, even though it is still a long way to get close to the hardest :)


Late edit: oh yea, and of that sudokusolver url CVMichael posted... I have only the "Method A" and "Method B" coded. After that it is all backtracker if those aren't enough to solve the puzzle.

[NotLKH]

Here's some more to play with.
They've been seperated into sub-zip files, name = "difficulty" level.

Merri,
Seems like your about the only one here giving batch timings, so I'd like to ask a favor.

Do you think you could tabulate timings from this load, based on their "difficulty" code?

:wave:
-Thanks
-Lou

[Merri]

Here is something I did quickly:

Total time for 518 files: 632,245998 milliseconds
000,021232 ms: 0000\023_0127
000,021232 ms: 0000\024_0007
000,021511 ms: 0000\023_0196
000,021511 ms: 0000\023_0203
000,021511 ms: 0000\024_0166
000,021790 ms: 0000\026_0467
000,022070 ms: 0000\025_0430
000,022908 ms: 0000\0025_0001
000,022908 ms: 0001\026_0385
000,023187 ms: 0001\024_0000
000,023187 ms: 0003\027_0185
000,024584 ms: 0000\023_0031
000,024863 ms: 0001\025_0084
000,025702 ms: 0001\024_0051
000,026260 ms: 0001\026_0362
000,026540 ms: 0001\024_0109
000,027098 ms: 0001\026_0263
000,027657 ms: 0001\026_0056
000,027937 ms: 0001\025_0230
000,028216 ms: 0001\024_0506
000,029892 ms: 0001\025_0204
000,029892 ms: 0001\028_0466
000,030171 ms: 0001\024_0090
000,030171 ms: 0007\026_0397
000,030451 ms: 0003\026_0193
000,030730 ms: 0001\026_0060
000,030730 ms: 0007\024_0153
000,031289 ms: 0001\024_0317
000,031289 ms: 0003\024_0236
000,031848 ms: 0001\024_0307
000,032127 ms: 0003\024_0073
000,032127 ms: 0003\024_0080
000,032686 ms: 0005\026_0229
000,033244 ms: 0001\024_0123
000,033244 ms: 0001\024_0303
000,034083 ms: 0001\025_0427
000,036038 ms: 0001\024_0327
000,036038 ms: 0003\024_0301
000,036038 ms: 0007\025_0223
000,036317 ms: 0001\024_0037
000,036597 ms: 0001\026_0256
000,037156 ms: 0001\025_0298
000,037435 ms: 0001\025_0369
000,037714 ms: 0001\026_0119
000,038273 ms: 0001\023_0343
000,038273 ms: 0001\026_0049
000,038832 ms: 0001\025_0449
000,039111 ms: 0003\024_0308
000,039670 ms: 0001\023_0206
000,039670 ms: 0001\025_0336
000,040229 ms: 0001\024_0292
000,040508 ms: 0001\023_0282
000,040787 ms: 0001\023_0089
000,041067 ms: 0001\024_0061
000,041905 ms: 0007\025_0286
000,042463 ms: 0001\024_0486
000,042463 ms: 0003\024_0422
000,043022 ms: 0001\026_0279
000,043302 ms: 0001\024_0285
000,043581 ms: 0000\023_0055
000,044419 ms: 0005\025_0458
000,044698 ms: 0001\024_0144
000,044978 ms: 0003\023_0260
000,045537 ms: 0005\024_0423
000,046095 ms: 0001\024_0174
000,046095 ms: 0001\024_0366
000,047492 ms: 0001\025_0233
000,047771 ms: 0001\023_0016
000,047771 ms: 0003\025_0470
000,048051 ms: 0001\024_0066
000,048051 ms: 0001\025_0156
000,048330 ms: 0001\023_0003
000,049168 ms: 0003\026_0502
000,049448 ms: 0001\025_0141
000,049448 ms: 0001\025_0201
000,050006 ms: 0003\025_0040
000,050565 ms: 0001\026_0411
000,050844 ms: 0001\024_0335
000,050844 ms: 0003\025_0276
000,051124 ms: 0001\024_0176
000,051124 ms: 0001\024_0247
000,051683 ms: 0001\026_0444
000,051683 ms: 0005\024_0406
000,051962 ms: 0007\025_0005
000,052800 ms: 0007\023_0199
000,052800 ms: 0007\025_0379
000,053079 ms: 0003\024_0290
000,053917 ms: 0001\023_0374
000,053917 ms: 0003\024_0477
000,054197 ms: 0001\024_0403
000,055594 ms: 0001\024_0265
000,055594 ms: 0001\025_0387
000,055594 ms: 0007\025_0149
000,055873 ms: 0000\026_0270
000,055873 ms: 0003\026_0145
000,056152 ms: 0003\023_0211
000,056152 ms: 0007\024_0297
000,056432 ms: 0001\027_0138
000,056711 ms: 0003\025_0371
000,056711 ms: 0007\025_0033
000,056990 ms: 0001\024_0447
000,056990 ms: 0007\022_0130
000,057829 ms: 0001\026_0036
000,058108 ms: 0001\024_0351
000,058667 ms: 0007\022_0409
000,059225 ms: 0001\025_0395
000,059784 ms: 0001\024_0478
000,060063 ms: 0001\025_0191
000,060622 ms: 0007\023_0396
000,060902 ms: 0001\023_0212
000,060902 ms: 0001\024_0019
000,060902 ms: 0001\025_0009
000,061181 ms: 0007\025_0413
000,061740 ms: 0005\022_0311
000,062578 ms: 0003\027_0473
000,063137 ms: 0001\024_0375
000,063416 ms: 0001\025_0093
000,063695 ms: 0007\026_0018
000,064813 ms: 0001\026_0420
000,064813 ms: 0003\025_0341
000,065930 ms: 0001\022_0321
000,065930 ms: 0001\025_0136
000,066768 ms: 0005\023_0404
000,067048 ms: 0003\024_0097
000,067048 ms: 0003\026_0456
000,067327 ms: 0001\025_0283
000,068165 ms: 0019\023_0503
000,068444 ms: 0003\025_0323
000,069283 ms: 0005\024_0052
000,069841 ms: 0001\024_0184
000,069841 ms: 0007\025_0394
000,070400 ms: 0001\025_0175
000,070679 ms: 0001\023_0376
000,070959 ms: 0007\025_0189
000,071238 ms: 0001\024_0179
000,071797 ms: 0007\023_0070
000,072076 ms: 0003\026_0492
000,072356 ms: 0001\024_0218
000,072356 ms: 0003\027_0121
000,072914 ms: 0007\025_0079
000,073752 ms: 0001\024_0075
000,075708 ms: 0007\025_0481
000,076267 ms: 0007\022_0431
000,076825 ms: 0007\022_0140
000,077943 ms: 0007\024_0410
000,078502 ms: 0021\023_0170
000,079619 ms: 0007\022_0361
000,080178 ms: 0007\025_0152
000,081016 ms: 0003\024_0151
000,081016 ms: 0007\025_0171
000,081295 ms: 0015\023_0043
000,082413 ms: 0001\026_0453
000,082413 ms: 0003\024_0014
000,082692 ms: 0003\025_0143
000,082971 ms: 0005\024_0129
000,083251 ms: 0007\024_0386
000,083810 ms: 0001\027_0054
000,083810 ms: 0003\024_0225
000,084368 ms: 0007\025_0210
000,086044 ms: 0003\023_0010
000,086044 ms: 0007\024_0412
000,087441 ms: 0005\024_0415
000,089117 ms: 0007\024_0117
000,089117 ms: 0007\024_0222
000,089397 ms: 0001\024_0231
000,089676 ms: 0007\024_0083
000,089956 ms: 0001\025_0389
000,090235 ms: 0007\024_0067
000,090794 ms: 0007\023_0155
000,091073 ms: 0001\025_0469
000,092190 ms: 0001\026_0390
000,092470 ms: 0007\024_0459
000,094146 ms: 0007\023_0355
000,094984 ms: 0007\023_0048
000,095822 ms: 0005\026_0131
000,098057 ms: 0001\025_0500
000,099175 ms: 0005\024_0108
000,100013 ms: 0003\024_0234
000,100851 ms: 0003\024_0509
000,101130 ms: 0001\022_0304
000,101968 ms: 0001\026_0013
000,101968 ms: 0007\025_0275
000,103365 ms: 0003\025_0029
000,104483 ms: 0007\022_0326
000,105321 ms: 0003\024_0192
000,110629 ms: 0011\024_0354
000,111187 ms: 0007\024_0305
000,111467 ms: 0007\022_0180
000,112305 ms: 0001\023_0438
000,112584 ms: 0001\024_0443
000,123200 ms: 0001\023_0095
000,127670 ms: 0015\024_0001
000,127949 ms: 0007\025_0249
000,129346 ms: 0005\025_0110
000,130743 ms: 0001\025_0092
000,136051 ms: 0003\023_0025
000,140241 ms: 0015\024_0104
000,205892 ms: 0071\023_0059
000,212317 ms: 0003\024_0107
000,224330 ms: 0001\025_0457
000,224610 ms: 0007\025_0372
000,234108 ms: 0077\023_0137
000,235784 ms: 0007\023_0328
000,238578 ms: 0007\025_0246
000,258133 ms: 0007\025_0215
000,268470 ms: 0001\023_0038
000,279644 ms: 0007\025_0320
000,282717 ms: 0007\024_0261
000,289422 ms: 0007\024_0252
000,292216 ms: 0001\025_0436
000,292775 ms: 0023\026_0330
000,307581 ms: 0007\025_0461
000,311213 ms: 0071\023_0187
000,313448 ms: 0007\025_0227
000,314844 ms: 0069\023_0221
000,315403 ms: 0001\023_0008
000,321829 ms: 0003\024_0178
000,329371 ms: 0007\026_0091
000,335518 ms: 0007\025_0004
000,338870 ms: 0003\025_0356
000,348368 ms: 0007\023_0126
000,352838 ms: 0005\023_0475
000,361778 ms: 0029\025_0388
000,371276 ms: 0001\026_0460
000,409829 ms: 0001\0025_0004
000,418489 ms: 0001\023_0445
000,419048 ms: 0003\023_0214
000,427429 ms: 0003\026_0208
000,429105 ms: 0007\024_0081
000,442235 ms: 0003\025_0165
000,445308 ms: 0007\025_0378
000,448381 ms: 0007\024_0468
000,454527 ms: 0003\024_0135
000,457321 ms: 0001\024_0479
000,463187 ms: 0007\025_0200
000,477156 ms: 0013\023_0332
000,480508 ms: 0007\025_0088
000,490006 ms: 0007\025_0505
000,495594 ms: 0015\026_0237
000,497549 ms: 0005\023_0085
000,507886 ms: 0007\024_0120
000,511797 ms: 0001\025_0122
000,515429 ms: 0007\023_0202
000,516825 ms: 0007\027_0465
000,522133 ms: 0001\023_0198
000,529118 ms: 0015\025_0421
000,535264 ms: 0007\024_0169
000,539454 ms: 0007\025_0364
000,540851 ms: 0015\024_0177
000,543645 ms: 0015\023_0337
000,545600 ms: 0013\024_0441
000,546438 ms: 0001\026_0134
000,550629 ms: 0007\023_0349
000,554819 ms: 0005\024_0428
000,568229 ms: 0007\025_0164
000,572140 ms: 0031\025_0106
000,580800 ms: 0005\025_0269
000,583035 ms: 0003\025_0099
000,586667 ms: 0003\025_0331
000,590298 ms: 0005\025_0239
000,591695 ms: 0003\024_0173
000,592533 ms: 0001\022_0024
000,592813 ms: 0003\025_0280
000,600356 ms: 0015\023_0163
000,602591 ms: 0003\026_0267
000,607619 ms: 0007\025_0102
000,610972 ms: 0003\025_0299
000,611530 ms: 0001\024_0072
000,613486 ms: 0003\025_0381
000,615441 ms: 0001\0025_0006
000,617676 ms: 0001\024_0205
000,622705 ms: 0007\024_0382
000,623543 ms: 0001\024_0451
000,630248 ms: 0005\025_0450
000,651479 ms: 0023\0025_0004
000,653156 ms: 0007\023_0400
000,654273 ms: 0015\026_0454
000,654552 ms: 0001\026_0348
000,656787 ms: 0013\025_0338
000,657067 ms: 0029\025_0058
000,661816 ms: 0007\023_0032
000,665448 ms: 0003\025_0419
000,676343 ms: 0015\025_0472
000,676622 ms: 0023\025_0161
000,677740 ms: 0003\0025_0002
000,693943 ms: 0011\026_0162
000,697016 ms: 0001\026_0125
000,699530 ms: 0013\026_0398
000,700368 ms: 0007\025_0284
000,718248 ms: 0007\025_0065
000,727467 ms: 0007\028_0463
000,738083 ms: 0005\022_0118
000,745905 ms: 0015\025_0146
000,753727 ms: 0009\025_0244
000,756241 ms: 0005\024_0408
000,760432 ms: 0007\024_0416
000,760711 ms: 0015\026_0157
000,764064 ms: 0003\025_0046
000,766299 ms: 0003\027_0434
000,777752 ms: 0003\025_0220
TO BE CONTINUED...

Atleast you can identify which are the hard ones and which the easy ones... for my code. Didn't really have a killer sudoku, although I believe the last one there might be even more evil to others.

[Merri]

CONTINUED...
000,779987 ms: 0029\024_0078
000,788648 ms: 0007\024_0507
000,800102 ms: 0007\024_0487
000,807086 ms: 0001\023_0368
000,815467 ms: 0003\023_0248
000,818540 ms: 0007\025_0501
000,819378 ms: 0007\024_0216
000,822172 ms: 0023\025_0399
000,829994 ms: 0015\023_0452
000,832508 ms: 0007\022_0302
000,841727 ms: 0001\026_0352
000,854578 ms: 0001\026_0259
000,857372 ms: 0007\025_0128
000,863238 ms: 0007\024_0271
000,865752 ms: 0007\026_0334
000,869664 ms: 0069\022_0491
000,870781 ms: 0013\024_0272
000,874692 ms: 0007\024_0425
000,876648 ms: 0005\026_0077
000,876648 ms: 0007\024_0347
000,877206 ms: 0015\025_0484
000,885867 ms: 0003\027_0496
000,891733 ms: 0005\026_0017
000,895086 ms: 0007\024_0493
000,900114 ms: 0007\023_0253
000,902629 ms: 0013\026_0358
000,909054 ms: 0001\022_0186
000,914641 ms: 0007\027_0350
000,914641 ms: 0067\0023_0003
000,919111 ms: 0007\025_0429
000,919391 ms: 0007\024_0250
000,926654 ms: 0005\023_0096
000,928889 ms: 0023\026_0241
000,930845 ms: 0031\024_0401
000,932241 ms: 0005\023_0289
000,940902 ms: 0007\024_0209
000,954870 ms: 0001\024_0433
000,957664 ms: 0001\025_0100
000,963530 ms: 0003\023_0417
000,968838 ms: 0007\026_0310
000,971073 ms: 0007\023_0437
000,971632 ms: 0003\026_0074
000,984203 ms: 0003\025_0498
000,991746 ms: 0007\027_0242
001,000686 ms: 0007\026_0064
001,019124 ms: 0003\024_0319
001,021918 ms: 0003\023_0190
001,032533 ms: 0007\022_0160
001,032533 ms: 0015\025_0455
001,039518 ms: 0007\022_0504
001,040356 ms: 0015\024_0057
001,043708 ms: 0007\028_0329
001,047060 ms: 0007\025_0219
001,059911 ms: 0005\025_0424
001,060749 ms: 0007\026_0384
001,063264 ms: 0007\024_0114
001,064381 ms: 0079\023_0034
001,074997 ms: 0007\024_0296
001,076673 ms: 0001\023_0257
001,084775 ms: 0007\023_0365
001,098743 ms: 0007\025_0485
001,107403 ms: 0011\025_0414
001,108521 ms: 0007\023_0159
001,112432 ms: 0015\023_0373
001,120533 ms: 0071\023_0340
001,121092 ms: 0007\024_0194
001,127797 ms: 0005\023_0273
001,144838 ms: 0007\025_0228
001,149587 ms: 0001\025_0133
001,154057 ms: 0015\024_0499
001,162438 ms: 0003\025_0489
001,164394 ms: 0065\022_0182
001,172216 ms: 0003\024_0380
001,174730 ms: 0007\024_0063
001,185346 ms: 0007\024_0062
001,190375 ms: 0013\025_0041
001,191772 ms: 0007\027_0258
001,196521 ms: 0007\024_0439
001,208533 ms: 0007\024_0405
001,218591 ms: 0007\025_0391
001,226133 ms: 0025\024_0262
001,228089 ms: 0007\021_0318
001,233676 ms: 0007\025_0435
001,239822 ms: 0015\023_0195
001,249600 ms: 0013\024_0139
001,252673 ms: 0007\024_0345
001,256864 ms: 0007\024_0150
001,264686 ms: 0009\025_0497
001,277537 ms: 0085\023_0462
001,279492 ms: 0007\022_0068
001,299886 ms: 0005\024_0442
001,301562 ms: 0001\024_0377
001,307708 ms: 0079\023_0316
001,316368 ms: 0001\025_0243
001,317486 ms: 0001\026_0082
001,329499 ms: 0009\025_0006
001,333410 ms: 0017\024_0288
001,340394 ms: 0015\026_0370
001,342908 ms: 0003\024_0266
001,349892 ms: 0003\025_0094
001,371962 ms: 0001\0025_0000
001,377549 ms: 0005\027_0360
001,380064 ms: 0017\026_0115
001,388165 ms: 0009\025_0142
001,389003 ms: 0065\022_0344
001,392635 ms: 0007\025_0197
001,397664 ms: 0031\025_0306
001,403810 ms: 0001\024_0047
001,405207 ms: 0007\024_0022
001,415264 ms: 0015\024_0407
001,424762 ms: 0007\025_0103
001,445156 ms: 0007\025_0251
001,484267 ms: 0015\025_0086
001,521702 ms: 0003\024_0021
001,523937 ms: 0005\026_0116
001,547962 ms: 0005\026_0471
001,566680 ms: 0071\023_0483
001,582045 ms: 0001\025_0494
001,642667 ms: 0003\025_0207
001,646299 ms: 0001\024_0488
001,679264 ms: 0015\025_0148
001,707200 ms: 0001\024_0357
001,711391 ms: 0003\024_0464
001,732343 ms: 0015\023_0363
001,759162 ms: 0007\025_0105
001,768381 ms: 0001\025_0309
001,768661 ms: 0001\027_0474
001,770616 ms: 0003\024_0181
001,809727 ms: 0003\025_0300
001,827327 ms: 0023\024_0476
001,835429 ms: 0007\025_0217
001,854705 ms: 0065\022_0339
001,915048 ms: 0013\027_0353
001,941588 ms: 0007\024_0295
001,975111 ms: 0007\023_0359
002,011988 ms: 0029\026_0393
002,013105 ms: 0003\023_0044
002,030984 ms: 0023\025_0312
002,067022 ms: 0003\023_0069
002,104457 ms: 0007\026_0383
002,138540 ms: 0003\025_0101
002,141054 ms: 0001\024_0042
002,143569 ms: 0007\025_0333
002,151670 ms: 0031\026_0268
002,156699 ms: 0007\024_0050
002,167035 ms: 0003\025_0226
002,193016 ms: 0079\021_0028
002,210337 ms: 0007\026_0053
002,252521 ms: 0007\024_0183
002,269003 ms: 0077\023_0113
002,277105 ms: 0007\024_0254
002,298616 ms: 0003\024_0490
002,314819 ms: 0093\023_0147
002,333537 ms: 0007\024_0087
002,384940 ms: 0015\025_0293
002,460648 ms: 0013\024_0132
002,488026 ms: 0007\028_0495
002,495848 ms: 0013\022_0020
002,526299 ms: 0007\026_0367
002,555073 ms: 0007\024_0448
002,600051 ms: 0023\025_0314
002,645867 ms: 0007\024_0325
002,700343 ms: 0079\023_0482
002,706210 ms: 0003\025_0111
002,818235 ms: 0011\026_0023
002,847289 ms: 0007\025_0278
002,930540 ms: 0007\024_0264
002,934451 ms: 0011\023_0015
002,985575 ms: 0007\022_0294
002,994794 ms: 0079\023_0392
003,033067 ms: 0007\023_0112
003,069105 ms: 0005\025_0346
003,198731 ms: 0005\026_0446
003,279467 ms: 0007\0025_0005
003,418591 ms: 0015\024_0224
003,514972 ms: 0079\023_0167
003,589004 ms: 0079\023_0045
003,646553 ms: 0007\025_0124
003,756343 ms: 0005\024_0188
003,828140 ms: 0007\025_0071
003,830654 ms: 0007\024_0235
004,076775 ms: 0003\026_0480
004,134883 ms: 0001\025_0076
004,135162 ms: 0007\024_0277
004,172039 ms: 0007\023_0238
004,248864 ms: 0079\023_0315
004,296635 ms: 0003\025_0287
004,301105 ms: 0007\025_0011
004,311721 ms: 0003\023_0158
004,352788 ms: 0009\025_0255
004,565943 ms: 0007\025_0168
004,673778 ms: 0013\025_0281
004,696686 ms: 0001\025_0402
004,894756 ms: 0007\023_0154
004,918782 ms: 0017\024_0012
004,932470 ms: 0003\024_0432
005,033321 ms: 0011\026_0322
005,193956 ms: 0015\023_0027
005,616077 ms: 0079\022_0026
005,804090 ms: 0015\023_0274
005,929245 ms: 0023\024_0098
006,087086 ms: 0007\028_0342
006,094071 ms: 0015\023_0426
006,275099 ms: 0015\023_0035
006,373994 ms: 0007\025_0240
006,390477 ms: 0005\023_0030
006,576814 ms: 0079\023_0213
006,793321 ms: 0003\022_0039
007,385296 ms: 0067\023_0232
008,125334 ms: 0009\025_0291
008,313626 ms: 0027\023_0245
009,081322 ms: 0007\025_0508
009,528865 ms: 0011\024_0440
010,530668 ms: 0007\024_0324
010,996370 ms: 0015\022_0418
017,339355 ms: 0025\022_0313
023,312460 ms: 0015\024_0172
040,148678 ms: 0015\023_0002

Sheesh. 10000 characters limit really kills. Anyways, I guess you're 1337 enough to be able to sort out the data into an array and then make it show what you want.

[ntg]

Can I play too? :lol:

[NotLKH]

Thanks Merri!

NTG,
Do you have any kind of rating sequence in your filenames?

:wave:
-Lou

[NotLKH]

Hmmm,
looks like I might have to submit only type 15's and 79's.

[Brick1]

last week i discovered sudoku so yesterday i wrote a solver that combines both logic rules and recursive backtracking. Once you set your goals at speed its not hard to optimize data structures and looping. So progression is easy at the beginning. But after a while you meet your bounderies.
I dont see how one can solve a sudoku in less than 1 ms when it takes me 2.8 ms to set up the game depending variables. So let's do the test:

Q.StartTime
For i = 1 To 1000000
Next
Q.StopTime

My average is about 12.50 ms, what's yours?

[ntg]

NTG,
Do you have any kind of rating sequence in your filenames?
:wave:
-Lou
Ehm....no. Actually, these were taken from the web. :p

[ntg]

last week i discovered sudoku so yesterday i wrote a solver that combines both logic rules and recursive backtracking. Once you set your goals at speed its not hard to optimize data structures and looping. So progression is easy at the beginning. But after a while you meet your bounderies.
I dont see how one can solve a sudoku in less than 1 ms when it takes me 2.8 ms to set up the game depending variables. So let's do the test:

Q.StartTime
For i = 1 To 1000000
Next
Q.StopTime

My average is about 12.50 ms, what's yours?
Yeah, that's also how I felt at first. My understanding (and anyone please jump in to correct me if I'm mistaken) is that if your variable setup has nothing to do with each particular sudoku (so we're actually talking about all the things you need to do in order to load the puzzle into your internal representation), then this will not be included in the timing. Same stands for displaying your solution (spit it out in a 9x9 text matrix or use GDI and display dancing elephants forming the solution, it's the same). On the other hand, if your initial variable setup is geared towards solving the actual puzzle in any way (performing puzzle-specific initialization or reductions), this will be included in the final timing. I take it that it's also inferred that if you have to create certain structures or precalculate stuff that don't have to do with any one puzzle (so this would have to be done only once at the beginning of the application's run), then such code will also be excluded from the timing.

Now...I haven't got the faintest idea what's the purpose of that specific loop...but my time would be ~1ms for that. Just keep in mind that all contest entries will be executed on the same computer.

[manavo11]

BTW, I think that the following code of the StopWatch class needs to be revised.

'/// <summary>
'/// Returns the time that has passed since the Reset() method was called.
'/// </summary>
'/// <remarks>The time is returned in tenths-of-a-millisecond.
'/// If the Peek method returns '10000', it means the interval took exactely
'/// one second.</remarks>
'/// <returns>A long that contains the time that has passed since the
'/// Reset() method was called.</returns>
'/// <exception cref="NotSupportedException">The system does not
'/// have a high-resolution performance counter.</exception>
Public Function Peek() As Long
Return CType((((GetValue() - StartTime) / CType(Frequency, Double)) * 10000), Long)
End Function
Like the comments indicate, this will give you an accuracy up to 1/10 of a msec. The cast to long incurs rounding and it should be a cast to double.
Public Function Peek() As Double
Return CType((((GetValue() - StartTime) / CType(Frequency, Double)) * 10000), Double)
End Function
Any arguments?

Any other .Net person want to comment on this? If something should be changed I should make a comment in the contest rules thread...

[Merri]

Hmmm,
looks like I might have to submit only type 15's and 79's.
In the contest test sudokus there should be a variety of different kinds of sudokus: very easy, easy, medium, hard and very hard. If you pick the hardest only based on what is hard for my solver, you probably favor someone else. I guess there will be some background lurkers taking part in this contest not telling their times, laughing at the slow speed of my backtracker code...


Q.StartTime
For i = 1 To 1000000
Next
Q.StopTime

My average is about 12.50 ms, what's yours?

You compiled your code and with all optimizations turned on? No? Do it :) Also... the trick is not to do that much math.

[eyeRmonkey]

What should I use to time my program? I tried the one mentioned in the 'Rules' post, but it says it returns seconds, but there is no way my program is taking 5 seconds? Do I divide the number it returns by 1000? Does it actually return miliseconds? Or should I use a different timer method?

[Merri]

Try displaying the data with Format$(Q.RetTime, "0.000000") - if you have E stuff there, it is pretty confusing... using Format$ will fix that.

[Something Else]

In the contest test sudokus there should be a variety of different kinds of sudokus: very easy, easy, medium, hard and very hard. If you pick the hardest only based on what is hard for my solver, you probably favor someone else.
Sorry!

I agree that a variety should be used. I'm not out to get you, I'm just concerned that, on average, my submissions are "too easy".

{honestly, how many times have I heard how easy mine are, that there are harder ones, like these... :cry: }

So, do you really think my variety is best for the contest?
You really don't think I should try to submit only challanging ones?

-Lou

[Merri]

Yes, I do. Because that would be the most "fair" thing for everyone. If there are different kind of sudokus instead of a lot of the same kind, it wouldn't be too harsh to every code. Like, some code might be bad at one certain thing and if all the sudokus happen to be like that as they are diffucult in a same way, it would be very unfair against that code: the contest would be more like a test against the code. The contest wouldn't also see a broader view to the situatation: the code might be very good speedwise in something else, but if there are only sudokus of the same kind, the code couldn't show the potential.

So this is why I think variety is a good thing. It gives every code the chance it deserves. I think that in the end there should be equal amount of sudokus that are beforehand thought to be of certain difficulty. Like, ten very easy, ten easy, ten medium, ten difficult and ten very hard. All of them should try to be that in a different way. How to figure that out, well, it is your task and not mine :)

[ntg]

In the contest test sudokus there should be a variety of different kinds of sudokus: very easy, easy, medium, hard and very hard.
That sounds exactly right, that should give every algo a fair chance. My code for example won't solve very easy problems fast but it works better for more difficult puzzles and I'd hate to see only easy-medium puzzles being used for timing.

[dukuso]

make 2 contests, one for easy(average) sudokus, one for hard ones ?
you can use the same processing software, same organization etc.

Apparantly these are two different problems, though.

[eyeRmonkey]

Try displaying the data with Format$(Q.RetTime, "0.000000") - if you have E stuff there, it is pretty confusing... using Format$ will fix that.
I just used Round(objTimer.RetTime, 15). I figured it out a few minutes after I posted because I widened my textbox and saw that the E stuff was there.

[eyeRmonkey]

Ok I have 3 questions:

1) I'll start with the stupid one: Is a millisecond 0.001 or 0.0001?

2) What is backtracking? I have a few logic things in my program, but I don't have anything that I would define as backtracking. Could someone explain this to me please. Thanks.

3) Should I optimize for Pentium Pro in my program? It makes the program run faster on my comp, but I don't know how it will effect the comp these programs are going to be tested on. Will that comp have a Pentium chip?

[si_the_geek]

1) 0.001

2) I think this is where you place numbers without actually knowing that they are correct, and trying to continue from there. If this fails, backtracking is the process of returning to where you were before placing the number.

3) I presume you mean ticking the box in the "Compile" options. I think all computers these days are compatible with P-Pro, but I could be wrong. The "Advanced" options will certainly make a difference, if your code is safe ;).
I don't know what the exact process will be for marking, so these options may or may not make a difference.

[NotLKH]

The way I "backtrack" is extremely inefficient at this time.
However, you might be able to improve upon it.

For each cell thats unassigned,
- For each possible could be for that cell
- - Make a copy of your structure
- - Delete all the other could be's for that cell in the copy
- - Try to solve the copy
- - - If the copy disastrously fails to solve, ie.. it turns out that two or more cells in a group ends up with the same number, then delete this could_be from its original cell
- - - else, if it "worked", ie... it might not be solved, but it is Not conclusively impossible, don't do anything except test the next possible.

Once you've done this, hopefully some of the couldbe's have been deleted in such a way that the changed structure now solves.

Again, doing it this way is extremely inefficient. but its a start.

:wave:
-Lou

[eyeRmonkey]

3) I presume you mean ticking the box in the "Compile" options. I think all computers these days are compatible with P-Pro, but I could be wrong. The "Advanced" options will certainly make a difference, if your code is safe ;).
I don't know what the exact process will be for marking, so these options may or may not make a difference.
I hope we can clear this up before submission time. :thumb:

[CVMichael]

I honestly don't care about the optimizations in the project advanced settings.

Why ? Because even if the tester decides to test in de IDE with no optimizations, he will do the same with the other contestants... So, why worry about that ?
In whatever conditions the tester will test my code, in the same conditions he will test the other people. So if the algorithm is exactly the same on 2 people (i doubt it, but lets say...), then it will be the same time for both contestants...

And of course... the tester will test all submissions on the same computer

[manavo11]

3) Should I optimize for Pentium Pro in my program? It makes the program run faster on my comp, but I don't know how it will effect the comp these programs are going to be tested on. Will that comp have a Pentium chip?

Personally I don't have a pentium at all, but as CVMichael says, all entries will be marked on the same PC under the same conditions...

[eyeRmonkey]

That makes sense. Especially because we can't submit .EXEs, so if the tester wanted to test it in .EXE format, then they would have to compile it and would therefore compile everyones (and in the same way).

[manavo11]

Exactly ;)

[eyeRmonkey]

Merri,

I have to say, you motivate me to give up because I know you are going to win (well, at least beat me). ;) Not really, but your "VB speed guru" title fits you well. I have been reading your posts in "Code It Better" and its crazy how fast your program is. Mine solves 10 in the time yours solves 300.

I decided I will just get it to solve all the puzzels and I will be happy. I will keep speed in mind as I code it, but not worry too much about it. Then when I am done I will play around with things to see what is fastest.

[manavo11]

Keep trying :) At the end, it will be more fun to look at Merri's code and see what he did differently if you have tried it yourself ;)

[eyeRmonkey]

I totally agree. This is all a great learning experience for me anyway because I have only been into VB6 for a little over a month.

[manavo11]

Then I'll just keep on encouraging you :) The more people participate the better :)

[eyeRmonkey]

:lol: :p

I'm working on it. At the moment it can only solve the most basic ones, but I am working on adding a couple other logic rules to it.

I'm kinda worried about adding back-tracking, because I think it will slow down my program a ton, but it sounds like it is necessary for the harder ones.

[Merri]

There is going to be a personal history lesson. If you're not up to it, skip the following paragraph. For the others... enjoy the fun.

Yeah, it is always better to first make it work and then start optimizing it. Of course the level of optimization I started with was pretty high, I have much more previous experience :) I've been using VB since late 1997 and a basic language since ~1990 (when I were about six years old). Though I've "only" been getting into speed optimization for about two years now, ever since bothering another guru and trying to match up with him in speed... I lost as he had done a code a couple of years before which he has proven to be the fastest possible in VB6, but I got very close when I tried all kinds of approaches. I also found out "The Secret to Speed".

Anyways... it is pretty hard as I know my code still isn't the fastest out there (mostly due to my "poor" backtracker) yet my code seems to be much faster than other participants. I still think there are probably some people who just lurk behind the scenes and will submit a superb code. My approach might also lose if tested under the IDE, because targetting speed for IDE is much different from targetting speed for a compiled EXE.

My code will be fully commented for everyone's viewing pleasure :) And also, I don't know how much it is worth to win the contest anyways... it didn't really destroy my life to take part in the Prime Numbers contest last year and only lose due to the slow speed of listbox adding which I didn't optimize at all (the only trick I did was to hide the listbox when adding items). Of course I'm angry about the silliness of it as I can't understand why we should optimize a listbox adding in a prime numbers contest. Atleast this time I'll lose due to bad code.


This is getting long... maybe I should write more?

[Merri]

Okay... I have just made something I'm pretty happy with. Due to that I won't be saying my times anymore, mostly to make it harder for the possible lurkers to see where I am going. I also might be just bluffing...


Edit
Here are the hardest three puzzles I've found this far:

67....3..
.4.....8.
....1....
...8..1.5
.2.4.....
......6..
...7...2.
5...6....
1........

.86......
....5..1.
...4...3.
5..3...4.
.7....2..
...1.....
.....86.7
3........
......8..

3...8....
...7....5
1........
......36.
..2..4...
.7.......
....6.13.
.452.....
......8..

These are pain for me. They take almost 500 times longer to solve than the easiest I have.

[eyeRmonkey]

Thanks, I had been wondering what the hardest ones are (not that I'm close to being able to solve them). I'm guessing they take a lot of backtracking if yours takes a lot of time. ;)

From what I have read (and the code I have made) it seems to me that optimized code tends to be very hard to read. I hope your comments are really good. :)

I'm up for hearing a continuation of that long post.

[ntg]

:p OK, for all the lurkers out there:

NotLKH1, 69 files, ~30ms
NotLKH2, 532 files, ~270ms
NotLKH3, 123 files, ~80ms
Hardest, 337 files, ~745ms

Using VB.Net, P4@3,2Ghz. I still can't get the fastest solution below 0,2 ms no matter what I do. There are still improvements that can be made though. :bigyello:

[eyeRmonkey]

By the way are we going to be given puzzels with non-unique solutions? I know our solver has to be able to solve all puzzles to have a shot at winning, so does that include non-unique ones/ones that need to be brute-forced?

[manavo11]

No... I thought that was established that those aren't true sudokus or something :ehh: Anyway, it doesn't seem fair to have those since it's kind of a matter of luck then, right?

[eyeRmonkey]

True, it would be more like luck.

Sorry, you might have established it earlier, I probably missed it. Thanks for clearing it up. :)

[manavo11]

I don't think I did explicitely mention it but when Lou said they aren't true sudokus I assumed it's obvious that we won't test them (in other words I'm lazy) :)

[Something Else]

I don't think I did explicitely mention it but when Lou said they aren't true sudokus I assumed it's obvious that we won't test them (in other words I'm lazy) :)
:confused:
Got a link?


:confused: :confused:
-Lou

[manavo11]

No? :)

Maybe it wasn't you? I remember someone saying that :ehh: And there are 3 threads going on (Games section, Contest Section and Chit Chat)... In one of them someone said that :)

[manavo11]

Close, someone was asking you but wikipedia answered :D

http://www.vbforums.com/showpost.php?p=2115332&postcount=89

[Something Else]

I've been concerned that I might be making multi-solution puzzles.

I thought you were saying I said they weren't true sudoku's, "they" meaning my submissions.


Thanks for the clarification!

:wave:
-Lou

[manavo11]

Oh no no no! Your submissions are just fine as the testers have proven :) Sorry for the mixup :wave:

[kaffenils]

yet my code seems to be much faster than other participants.

I haven't had time to code much lately since I am on holiday, but these are my temporary results. I still have some good ideas on how to optimize even further, so my guess is that the "long" running sudokus will be much much faster. Keep in mind that the results are from a P3 700 Mhz. You still beat me on the hardest sudokus.

My results (in milliseconds):
Total time: 1751,659219
wossname.txt solved. Time used 3,042565
wallyb.txt solved. Time used 148,997708
veryeasy.txt solved. Time used 0,163429
tomker.txt solved. Time used 290,79478
supertough1.txt solved. Time used 303,626299
sudoku3.txt solved. Time used 2,412876
sudoku2.txt solved. Time used 0,58974
sudoku1.txt solved. Time used 0,148902
dukuso3.txt solved. Time used 303,340508
dukuso2.txt solved. Time used 215,274567
dukuso1.txt solved. Time used 291,233662
0068_0003_023.msk solved. Time used 0,52381
0067_0000_023.msk solved. Time used 0,34781
0066_0000_023.msk solved. Time used 0,324064
0065_0001_023.msk solved. Time used 0,481625
0064_0001_023.msk solved. Time used 0,486654
0063_0003_023.msk solved. Time used 0,630527
0062_0003_023.msk solved. Time used 0,482743
0061_0000_023.msk solved. Time used 0,334121
0060_0001_023.msk solved. Time used 0,442235
0059_0001_023.msk solved. Time used 0,438045
0058_0000_023.msk solved. Time used 0,285511
0057_0003_023.msk solved. Time used 0,412064
0056_0003_023.msk solved. Time used 0,509562
0055_0000_023.msk solved. Time used 0,308698
0054_0003_023.msk solved. Time used 0,492241
0053_0001_023.msk solved. Time used 0,415695
0052_0003_023.msk solved. Time used 0,449219
0051_0001_023.msk solved. Time used 0,488889
0050_0003_023.msk solved. Time used 0,441676
0049_0001_023.msk solved. Time used 3,240635
0048_0001_023.msk solved. Time used 0,423238
0047_0003_023.msk solved. Time used 0,617676
0046_0003_023.msk solved. Time used 0,400889
0045_0000_023.msk solved. Time used 0,275175
0044_0001_023.msk solved. Time used 0,496432
0043_0000_023.msk solved. Time used 0,297244
0042_0003_023.msk solved. Time used 0,805968
0041_0000_023.msk solved. Time used 0,267073
0040_0003_023.msk solved. Time used 0,585549
0039_0003_023.msk solved. Time used 122,883774
0038_0001_023.msk solved. Time used 0,485816
0037_0003_023.msk solved. Time used 0,450616
0036_0001_023.msk solved. Time used 0,427987
0035_0003_023.msk solved. Time used 0,376305
0034_0001_023.msk solved. Time used 0,622146
0033_0003_023.msk solved. Time used 0,587505
0032_0003_023.msk solved. Time used 0,398375
0031_0003_023.msk solved. Time used 0,393625
0030_0003_023.msk solved. Time used 2,606756
0029_0003_023.msk solved. Time used 0,625219
0028_0000_023.msk solved. Time used 0,295848
0027_0001_023.msk solved. Time used 0,488051
0026_0001_023.msk solved. Time used 0,381613
0025_0003_023.msk solved. Time used 5,461588
0024_0001_023.msk solved. Time used 0,584432
0023_0003_023.msk solved. Time used 0,545321
0022_0003_023.msk solved. Time used 1,501867
0021_0000_023.msk solved. Time used 0,298362
0020_0001_023.msk solved. Time used 0,389156
0019_0001_023.msk solved. Time used 0,412902
0018_0001_023.msk solved. Time used 0,415137
0017_0003_023.msk solved. Time used 20,805717
0016_0003_023.msk solved. Time used 2,196369
0015_0003_023.msk solved. Time used 0,657905
0014_0001_023.msk solved. Time used 0,587505
0013_0003_023.msk solved. Time used 0,437206
0012_0001_023.msk solved. Time used 0,472406
0011_0001_023.msk solved. Time used 0,452013
0010_0003_023.msk solved. Time used 0,500902
0009_0001_023.msk solved. Time used 0,500064
0008_0003_023.msk solved. Time used 0,591695
0007_0001_023.msk solved. Time used 0,390832
0006_0003_023.msk solved. Time used 0,489448
0005_0003_022.msk solved. Time used 0,641702
0004_0001_022.msk solved. Time used 4,991975
0003_0003_022.msk solved. Time used 0,561803
0002_0003_022.msk solved. Time used 0,402844
0001_0001_022.msk solved. Time used 0,499225
0000_0001_022.txt solved. Time used 0,517105


Results from Merri's solver:
Benchmarking...
0,067048 ms: 0000_0001_022.txt
3,535645 ms: 0001_0001_022.msk
0,091632 ms: 0002_0003_022.msk
0,949003 ms: 0003_0003_022.msk
2,662350 ms: 0004_0001_022.msk
1,850235 ms: 0005_0003_022.msk
0,160356 ms: 0006_0003_023.msk
0,081854 ms: 0007_0001_023.msk
2,838350 ms: 0008_0003_023.msk
0,076546 ms: 0009_0001_023.msk
0,084927 ms: 0010_0003_023.msk
0,202819 ms: 0011_0001_023.msk
0,140241 ms: 0012_0001_023.msk
0,278806 ms: 0013_0003_023.msk
19,585171 ms: 0014_0001_023.msk
0,092190 ms: 0015_0003_023.msk
50,603918 ms: 0016_0003_023.msk
7,015417 ms: 0017_0003_023.msk
0,114260 ms: 0018_0001_023.msk
0,106438 ms: 0019_0001_023.msk
1,356318 ms: 0020_0001_023.msk
0,065092 ms: 0021_0000_023.msk
6,493004 ms: 0022_0003_023.msk
0,800102 ms: 0023_0003_023.msk
2,845334 ms: 0024_0001_023.msk
2,192178 ms: 0025_0003_023.msk
0,071517 ms: 0026_0001_023.msk
0,132140 ms: 0027_0001_023.msk
0,063695 ms: 0028_0000_023.msk
5,990706 ms: 0029_0003_023.msk
12,262452 ms: 0030_0003_023.msk
0,159797 ms: 0031_0003_023.msk
0,112305 ms: 0032_0003_023.msk
0,270984 ms: 0033_0003_023.msk
0,076546 ms: 0034_0001_023.msk
0,150019 ms: 0035_0003_023.msk
4,640813 ms: 0036_0001_023.msk
0,070121 ms: 0037_0003_023.msk
0,205892 ms: 0038_0001_023.msk
12,765589 ms: 0039_0003_023.msk
0,129346 ms: 0040_0003_023.msk
0,065092 ms: 0041_0000_023.msk
0,238578 ms: 0042_0003_023.msk
0,063695 ms: 0043_0000_023.msk
0,124597 ms: 0044_0001_023.msk
0,063416 ms: 0045_0000_023.msk
4,159467 ms: 0046_0003_023.msk
0,208406 ms: 0047_0003_023.msk
0,163429 ms: 0048_0001_023.msk
5,038070 ms: 0049_0001_023.msk
0,151137 ms: 0050_0003_023.msk
0,070679 ms: 0051_0001_023.msk
0,936152 ms: 0052_0003_023.msk
0,113981 ms: 0053_0001_023.msk
0,144990 ms: 0054_0003_023.msk
0,065371 ms: 0055_0000_023.msk
2,688051 ms: 0056_0003_023.msk
0,122641 ms: 0057_0003_023.msk
0,068724 ms: 0058_0000_023.msk
0,073473 ms: 0059_0001_023.msk
0,104203 ms: 0060_0001_023.msk
0,067606 ms: 0061_0000_023.msk
0,118171 ms: 0062_0003_023.msk
0,218464 ms: 0063_0003_023.msk
2,054451 ms: 0064_0001_023.msk
0,212038 ms: 0065_0001_023.msk
0,066489 ms: 0066_0000_023.msk
0,081016 ms: 0067_0000_023.msk
0,222933 ms: 0068_0003_023.msk
353,006318 ms: dukuso1.txt
104,280013 ms: dukuso2.txt
38,606583 ms: dukuso3.txt
0,069841 ms: sudoku1.txt
0,169575 ms: sudoku2.txt
5,610210 ms: sudoku3.txt
42,242799 ms: supertough1.txt
348,630901 ms: tomker.txt
0,077943 ms: veryeasy.txt
64,338065 ms: wallyb.txt
5,631163 ms: wossname.txt
Total time for 80 files: 1121,759888 milliseconds

[eyeRmonkey]

I was wondering who will be doing the marking of the entries? I need to know if the person who scores them will have windows XP so I know if I can use the rtlcomparememory API in my program.

[eyeRmonkey]

/rant on
GRRRRRRR! Ruff!

Ok, Merri, so you talked me into (without knowing it) making my puzzle 1-D. I spent like 5 hours figuring out how to change everything to 1-D and after I was done... I found out that it takes 3 times as long to solve a puzzle now.

I think it has something to do with the way I eliminate possiblities from each group. I thought I had the most efficient forumla I could think of, but maybe VB does math too slow or something.

SHMA!!

Maybe its also because the solver isnt done and all the logic rules aren't in place. If all the rules were there maybe I would find a 1-D array to be faster, but I doubt it. 3 times as slow for a very simple puzzle.

/rant off

[eyeRmonkey]

Woooot. Sorry for triple posting. But I finally got my solver to do something other than solve this:
.695.78.1
5.2.83.4.
31.694...
.37.65.8.
284731.96
956.483.7
8.14569.3
793.1.46.
6.53.91..

Which I had to make by taking a solution and removing a few parts. The crappy thing is that it takes 4 - 5 ms per puzzle where as other peoples solve in under 1 ms. I'll be happy if I can get it to solve everything though. YAY! :D

[Merri]

When you change a puzzle to 1D, you have to make sure you don't keep doing too much calculations. For example:


For Y = 0 To 8
For X = 0 To 8
Board(Y * 9 + X) = Y
Next X
Next Y


Is remarkably slower when compared to:

YX = 0
For Y = 0 To 8
For X = 0 To 8
Board(YX + X) = Y
Next X
YX = YX + 9
Next Y


This only one of the hundreds of tricks to speed up code :) As you can see, the code gets longer and consumes more memory when it is faster, but it is basically doing the same thing. You just try to calculate less yet doing the same thing you were doing before.


Edit Also, zero based arrays are much faster in VB6 than other bases.

[dukuso]

how about board[(y<<4)+x]=y ?
that's how I would avoid multiplication by 9 in C

[Merri]

There is no bitshifting operator in VB6. Though I'd still use a temporary variable to hold the result of Y<<4 if I were optimizing C for speed :)

[dukuso]

I just tried to estimate how much time I lose due to 2-dim arrays : about 3%.

[eyeRmonkey]

When you change a puzzle to 1D, you have to make sure you don't keep doing too much calculations. For example:


For Y = 0 To 8
For X = 0 To 8
Board(Y * 9 + X) = Y
Next X
Next Y


Is remarkably slower when compared to:

YX = 0
For Y = 0 To 8
For X = 0 To 8
Board(YX + X) = Y
Next X
YX = YX + 9
Next Y


This only one of the hundreds of tricks to speed up code :) As you can see, the code gets longer and consumes more memory when it is faster, but it is basically doing the same thing. You just try to calculate less yet doing the same thing you were doing before.

No I had been doing something like this:
For i = 1 to 81
' Do stuff
Next i

And then when I needed to get the row and column I would use integer division and a few other calculations. Doing it this way made groups really hard. The way you mentioned is a lot easier. I will try that later. Thanks. :)



Edit Also, zero based arrays are much faster in VB6 than other bases.

NOW YOU TELL ME!!! I had been using Option Base 1 to make things make sense in my head. More work to do now I guess. :)

[NotLKH]

And then when I needed to get the row and column I would use integer division and a few other calculations. Doing it this way made groups really hard. The way you mentioned is a lot easier. I will try that later. Thanks. :)

You could also create a 2dimensional map array, ie.. Dim CELL_TO_ROW_COL( 80, 1) as integer,

and, when you need to use the col and row coordinate for cell N, you just reference CELL_TO_ROW_COL( 80, 0) & CELL_TO_ROW_COL( 80, 1).

I've been revamping my version up to not use columns or rows whatsoever.
Just intermappings between:


the 81 cells and the 27 groups
the 9 3x3 Groups with the 18 row and column groups.


Whats your opinion on this theoretical setup?

:wave:
-Lou

[Merri]

Hehe, I tell a lot it seems :D Zero based arrays are easier for the computer and they start to make more sense once you get the idea. Oh well, I give you a tip for more optimization: make arrays that hold all the stuff you need to calculate over and over again (X and Y positions, square index...).

[eyeRmonkey]

You could also create a 2dimensional map array, ie.. Dim CELL_TO_ROW_COL( 80, 1) as integer,

and, when you need to use the col and row coordinate for cell N, you just reference CELL_TO_ROW_COL( 80, 0) & CELL_TO_ROW_COL( 80, 1).

I've been revamping my version up to not use columns or rows whatsoever.
Just intermappings between:


the 81 cells and the 27 groups
the 9 3x3 Groups with the 18 row and column groups.


Whats your opinion on this theoretical setup?

:wave:
-Lou
Not quite sure what you mean. Do you keep track of everything twice of what? Do you have 81 cells 2 times?

[eyeRmonkey]

... I give you a tip for more optimization: make arrays that hold all the stuff you need to calculate over and over again (X and Y positions, square index...).
I thought of this back when I was still planning on not entering the contest and was going over it in my head. I don't know why I never applied it. :thumb:

Any more tips? *nudge nudge*

EDIT: I have been using a UDT to hold the Row and Col (X and Y). Is that slower than a normal variable because of the fact that using a dot is always slower than not? Or does that dot thing not apply?

[NotLKH]

Do you think the requirements should be tweaked a bit?
It seems that many of you can handle processing directories of submissions en masse.

For the contest, it would seem like it'd be easier to judge if the progie, upon clicking "Start", that it should query for a source directory, whereby all the .msk files reside that need to be solved.

As each one is solved, the solution you've generated would be outputted to a directory parrallel to the source directory, generated by you, and recognizably named after your username. Also, once solved, a timing file is created, with the time you've detected it took to solve a submission.

An option control would also be resident on your form, to toggle between "Silent" mode, and "Visual" mode {ie.. just outputing to screen your solutions, as you solve them.}

Thus, as the judges run each entrant, all they have to do is build a compiler to return the results of ALL the entrants, plus it would also compare the entrants solutions against the "official" .sol file.

This way, you could place any optimizations into the form_load event that you want, that don't need to ever be regenerated when you do mass processing.

-Lou

[eyeRmonkey]

I like that idea, but it is probably up to manavo for the final decision.

I was also wondering if we could get a final say-so as to wether the judges will be testing compiled code or in the IDE? It would just make me feel more confident in what I am testing. If they do it compiled I would assume most optimizations would be on? Of course that could cause some programs to crash, but if they did crash, then they probably wouldn't have won anyway? Can give word on this subject manavo?

[Merri]

NotLKH: I don't like the idea as such, I want some freedom to the design. So cleaned up:

- there must be an option to pick a folder with the sudokus
- the folder files must be easy to benchmark
- the timing results must be outputted so that they're viewable by the user
- the solutions should be outputted into a user configurable directory if the user wants

I don't want to create a separate "silent" mode. I have added some visual candy so that it is easier for a human to check if the results are valid... though these are just nice extra. But the above mentioned changes/requirements should be enough?


Also, I do optimizations when a file is loaded the first time. My module is 100% independent from the actual program.

[NotLKH]

Well, I don't disagree with what you've suggested,
however, the timings should also not only be viewable, but also outted to a data file.

That way the judges won't have to manually tabulate the results, especially if they use the number of puzzles I can potentially provide.

The "Silent" mode is just a streamlining, so that the judges don't have to put up with screen outputs & updates.

And, your suggestion to be able to "Pick" a folder, well, again, all well and good. But Pasting the path is what I'd prefer, or even Drag and Drop, if I was forced to run/judge the entrents.

What you're making is a good distributable app to a generic user, and it sounds great. I was thinking about what would make it a better program for the intents of this contest, and that would be quick access to the source directory with as few human required input events as possible, and standard outputting of the data that needs to be judged, standard such that a judge could programically analyze the results, without having to do much of anything by eye and hand.

:)
-Lou

[ntg]

:wave: Hey lurkers:
NotLKH1, 69 files, ~26ms
NotLKH2, 532 files, ~233ms
NotLKH3, 123 files, ~68ms
Hardest, 337 files, ~648ms

I've been reading what you guys are discussing about optimizing array access, precalculating things and stuff like that. Personally, I won't do any more relevant optimizations because it's going to take the fun out of it, plus the code is already beginning to look like primo gusto macaroni to me. The sole code optimizations I did was to minimize method calls and substitute my original class design in favor of an array approach (although anyone who would read the class implementation would understand it in about 5 seconds - instead the current implementation would take considerably more time to comprehend and I really hate that). I think that major speed gains can be realized by improving the algorithmic approach to the solution of this instead of focusing on pure code optimization. Merri and dukuso in particular who already have very fast implementations for simple puzzles would drive everybody to the ground with a good backtracking algo.

[Merri]

Before, pretty much all I did was a combination of algorithm and code optimization as much as I could with the backtracker code I had. Since then I have coded a whole new backtracker with code optimization only. I don't dare say more... Or well, I say one timing: NotLKH1 in ~5.1 ms.

[eyeRmonkey]

Before, pretty much all I did was a combination of algorithm and code optimization as much as I could with the backtracker code I had. Since then I have coded a whole new backtracker with code optimization only. I don't dare say more... Or well, I say one timing: NotLKH1 in ~5.1 ms.
*stabs Merri in the hear and ran widly around holding a disk with his code on it over my head*

[Merri]

*sniff* Now my hear is broken :/ Good thing I can always do a recode! :D

Edit Oh... and make it ~4.7 ms... this is getting scary.

[dukuso]

put all sudokus in one file, one row per sudoku

[ntg]

...and make it ~4.7 ms
That's the way to go, I was kind of expecting you to say something like that. Once you figure it out, there are certain things that can be optimized when you go guessing and backtracking. They're not a lot of things but they make a big difference.

put all sudokus in one file, one row per sudoku
What does that have to do with anything?

[eyeRmonkey]

I think he was reffering to how to process multiple sudokus. I personally like multiple files more.

[NotLKH]

Hello, hhalkin...
gonna join the contest?

:wave:
-Lou

[eyeRmonkey]

The more the Merrier. ;)

[eyeRmonkey]

Woot! I am so happy. I can finally solve all but 6 of NotLKH1. The only reason I can't solve those 6 are because I don't have a backtracker yet. .5-3 ms each, but that will hopefully go down a ton after I start doing real optimizations.

[dukuso]

input,output and timing is much easier, when you allow multiple
solutions and just count the solutions instead of printing them.

e.g.:

.........
.........
.........
...975684
...821793
...436512
...582936
...693471
...714825

230400 solutions, 15sec*GHz = 1.5e10 CPU-cycles.
Only one puzzle needed for the whole contest !

[dukuso]

my 100 hardest sudokus:
http://magictour.free.fr/top100
284ms*GHz

[eyeRmonkey]

:lol: dukuso, I think we have already decided that sudokus with multiple solutions are not considered "proper" and that we aren't going to use them. :)

[dukuso]

then maybe for the next contest on another webpage using another language...
And you can still use them here "inofficially" for comparing your solvers.
I'm planning to use the winning program for rating hard sudokus -
provided it does perform well on hard sudokus and not only on the easy ones.

[Merri]

input,output and timing is much easier, when you allow multiple
solutions and just count the solutions instead of printing them.

e.g.:

.........
.........
.........
...975684
...821793
...436512
...582936
...693471
...714825

230400 solutions, 15sec*GHz = 1.5e10 CPU-cycles.
Only one puzzle needed for the whole contest !

Interesting... my solver counts this in 4600 ms. It gives a valid answer, 230400 solutions.

[manavo11]

I like that idea, but it is probably up to manavo for the final decision.

I was also wondering if we could get a final say-so as to wether the judges will be testing compiled code or in the IDE? It would just make me feel more confident in what I am testing. If they do it compiled I would assume most optimizations would be on? Of course that could cause some programs to crash, but if they did crash, then they probably wouldn't have won anyway? Can give word on this subject manavo?

You people post too much :)

Don't know how to test... But however it is, all the entries will be marked with the same standards so don't worry :)

[manavo11]

Do you think the requirements should be tweaked a bit?
It seems that many of you can handle processing directories of submissions en masse.

Let's see :)

For the contest, it would seem like it'd be easier to judge if the progie, upon clicking "Start", that it should query for a source directory, whereby all the .msk files reside that need to be solved.

As each one is solved, the solution you've generated would be outputted to a directory parrallel to the source directory, generated by you, and recognizably named after your username. Also, once solved, a timing file is created, with the time you've detected it took to solve a submission.

I like the idea, and that way we can test a lot of sudokus instead of manually putting a few ;)

An option control would also be resident on your form, to toggle between "Silent" mode, and "Visual" mode {ie.. just outputing to screen your solutions, as you solve them.}

Doesn't seem that important a "feature"...

Thus, as the judges run each entrant, all they have to do is build a compiler to return the results of ALL the entrants, plus it would also compare the entrants solutions against the "official" .sol file.

This way, you could place any optimizations into the form_load event that you want, that don't need to ever be regenerated when you do mass processing.

-Lou

I like the idea :) I have to read farther down to see the rest of the posts and compare... Hold on :)

[manavo11]

NotLKH: I don't like the idea as such, I want some freedom to the design. So cleaned up:

- there must be an option to pick a folder with the sudokus

Yes

- the folder files must be easy to benchmark

What exactly do you mean?

- the timing results must be outputted so that they're viewable by the user

In a seperate file I guess, a list with all of them and the times or something like that.

- the solutions should be outputted into a user configurable directory if the user wants

That's the whole point, to compare them after ;)

I don't want to create a separate "silent" mode. I have added some visual candy so that it is easier for a human to check if the results are valid... though these are just nice extra. But the above mentioned changes/requirements should be enough?

Doesn't seem that important the silent mode...

[manavo11]

Well, I don't disagree with what you've suggested,
however, the timings should also not only be viewable, but also outted to a data file.

That way the judges won't have to manually tabulate the results, especially if they use the number of puzzles I can potentially provide.

Yes :)

The "Silent" mode is just a streamlining, so that the judges don't have to put up with screen outputs & updates.

Never mind with this, it's not a big issue...

And, your suggestion to be able to "Pick" a folder, well, again, all well and good. But Pasting the path is what I'd prefer, or even Drag and Drop, if I was forced to run/judge the entrents.

In inputbox or something to input a dir is just fine, nothing fancy.

[manavo11]

Alright then, to sum it up :

-Prompt for input of the directory containing the sudokus
-Read all sudoku files in the specified folder
-Output the solved sudoku in a folder in the app path folder with the username of the contestant
-Time and keep track of the time for each sudoku solved and output in a list at the end

Is this about it? Any other suggestions? Did I miss anything? :

[Merri]

Only a small addition: "include a feature to output the solved sudoku within a folder in the app path folder with the username of the contest" - I don't want the program to output the sudokus each time I do something, that'd kill my laptop's harddisk (it is a slow one, listening to music can kill it every now and then).

On the other news... I finally coded a new logic to my code instead of optimizing the old ones. It is successful enough, NotLKH1 now below 4 ms. Overall I were very happy to see the new logic drop the required time in many of the sudokus :)

On the sad news, it seems I don't have many logic choices left... most are too complex to code, they'd just slow down the execution.

[eyeRmonkey]

my 100 hardest sudokus:
http://magictour.free.fr/top100
284ms*GHz
I threw together a program to split these into .msk files.

[eyeRmonkey]

Only a small addition: "include a feature to output the solved sudoku within a folder in the app path folder with the username of the contest" - I don't want the program to output the sudokus each time I do something, that'd kill my laptop's harddisk (it is a slow one, listening to music can kill it every now and then).
So how do you suggest we show what our solver got as a solution?

[Merri]

Because the same function is used, I don't see a problem? My program can actually solve the puzzle without displaying the result or storing it in any way. However, I can get it if I want to. Codewise:

- OpenSudoku (Function Boolean)
- PrepareSudoku (Sub ByRef SudokuBoard() As Byte)
- ReturnSudoku (Sub ByRef SudokuBoard() As Byte)
- SolveSudoku (Function Boolean)

If I call OpenSudoku, it returns True if it opens the file. OpenSudoku also calls PrepareSudoku which initializes the sudoku for processing. Currently this function seems to be able to open any known sudoku file format.

If I call PrepareSudoku, I give it a byte array with a puzzle in it. It then initializes the sudoku for processing.

If I call ReturnSudoku, I give it a byte array in which I want to have the current puzzle. It then fills this byte array (and resizes it if need be) with the values.

If I call SolveSudoku, it solves the current puzzle. It returns False if it fails (and it will do that only if you give it an invalid sudoku).


I have thought about adding SaveSudoku. Anyways, the point with the above: I don't need to think about returning a completed sudoku or problems with opening a file. Example code:


OpenSudoku "c:\test.sdk"
SolveSudoku


It opens the file and solves it. No need to display it or get a return value.


Dim SudokuBoard(80) As Byte
PrepareSudoku SudokuBoard
SolveSudoku
ReturnSudoku SudokuBoard
MsgBox StrConv(SudokuBoard, vbUnicode)


This code solves an empty board and shows the results as a one lined string in a message box.


Edit Duh, probably misread it before... I show my results visually, but there is no problem doing an other kind of output.

[eyeRmonkey]

Well, thanks for giving me about 20 tips as to how to modify my program to me more like yours. ;)

My point is that I ASSUME yours can only display 1 board at a time visually. That doesn't allow for mass processing AND mass output. So either the tester has to ensure that function to check the validity of a sudoku is correct or the tester needs to solve 1 at a time and compare the visual results with the actual solution in some way.

[CVMichael]

I threw together a program to split these into .msk files.
It seems that I have a LOONG way to go...

dukuso's_hardest_000.msk SOLVED in 1,814.934859 milliseconds !
dukuso's_hardest_001.msk SOLVED in 20,988.223364 milliseconds !
dukuso's_hardest_002.msk SOLVED in 1,084.403185 milliseconds !
dukuso's_hardest_003.msk SOLVED in 7,949.478775 milliseconds !
dukuso's_hardest_004.msk SOLVED in 517.331672 milliseconds !
dukuso's_hardest_005.msk SOLVED in 688.069573 milliseconds !
dukuso's_hardest_006.msk SOLVED in 28.336004 milliseconds !
dukuso's_hardest_007.msk SOLVED in 34.762239 milliseconds !
dukuso's_hardest_008.msk SOLVED in 116.598339 milliseconds !
dukuso's_hardest_009.msk SOLVED in 180.910982 milliseconds !
dukuso's_hardest_010.msk SOLVED in 1,317.542872 milliseconds !
dukuso's_hardest_011.msk SOLVED in 816.710504 milliseconds !
dukuso's_hardest_012.msk SOLVED in 63.958408 milliseconds !
dukuso's_hardest_013.msk SOLVED in 66.043031 milliseconds !
dukuso's_hardest_014.msk SOLVED in 29.587839 milliseconds !
dukuso's_hardest_015.msk SOLVED in 349.861784 milliseconds !
dukuso's_hardest_016.msk SOLVED in 822.774403 milliseconds !
dukuso's_hardest_017.msk SOLVED in 1,103.592216 milliseconds !
dukuso's_hardest_018.msk SOLVED in 7,181.811375 milliseconds !
dukuso's_hardest_019.msk SOLVED in 1,841.077288 milliseconds !
dukuso's_hardest_020.msk SOLVED in 478.773420 milliseconds !
dukuso's_hardest_021.msk SOLVED in 127.953134 milliseconds !
dukuso's_hardest_022.msk SOLVED in 1,874.943324 milliseconds !
dukuso's_hardest_023.msk SOLVED in 1,569.060034 milliseconds !
dukuso's_hardest_024.msk SOLVED in 3,256.705810 milliseconds !
dukuso's_hardest_025.msk SOLVED in 1,184.486576 milliseconds !
dukuso's_hardest_026.msk SOLVED in 1,127.795851 milliseconds !
dukuso's_hardest_027.msk SOLVED in 525.698378 milliseconds !
dukuso's_hardest_028.msk SOLVED in 641.548018 milliseconds !
dukuso's_hardest_029.msk SOLVED in 4,680.740709 milliseconds !
dukuso's_hardest_030.msk SOLVED in 2.567365 milliseconds !
dukuso's_hardest_031.msk SOLVED in 2,191.370691 milliseconds !
dukuso's_hardest_032.msk SOLVED in 1,568.653279 milliseconds !
dukuso's_hardest_033.msk SOLVED in 926.920042 milliseconds !
dukuso's_hardest_034.msk SOLVED in 72.577939 milliseconds !
dukuso's_hardest_035.msk SOLVED in 1,122.788511 milliseconds !
dukuso's_hardest_036.msk SOLVED in 17,217.268955 milliseconds !
dukuso's_hardest_037.msk SOLVED in 3.290642 milliseconds !
dukuso's_hardest_038.msk SOLVED in 158.018407 milliseconds !
dukuso's_hardest_039.msk SOLVED in 2,711.075849 milliseconds !
dukuso's_hardest_040.msk SOLVED in 4,585.880887 milliseconds !
dukuso's_hardest_041.msk SOLVED in 235.107255 milliseconds !
dukuso's_hardest_042.msk SOLVED in 7,684.072696 milliseconds !
dukuso's_hardest_043.msk SOLVED in 2,694.652533 milliseconds !
dukuso's_hardest_044.msk SOLVED in 94.306679 milliseconds !
dukuso's_hardest_045.msk SOLVED in 3.803835 milliseconds !
dukuso's_hardest_046.msk SOLVED in 1,171.015031 milliseconds !
dukuso's_hardest_047.msk SOLVED in 492.836939 milliseconds !
dukuso's_hardest_048.msk SOLVED in 1,336.245249 milliseconds !
dukuso's_hardest_049.msk SOLVED in 1,851.328311 milliseconds !
dukuso's_hardest_050.msk SOLVED in 1,563.441443 milliseconds !
dukuso's_hardest_051.msk SOLVED in 229.470226 milliseconds !
dukuso's_hardest_052.msk SOLVED in 1,751.772362 milliseconds !
dukuso's_hardest_053.msk SOLVED in 5,373.513952 milliseconds !
dukuso's_hardest_054.msk SOLVED in 3.258794 milliseconds !
dukuso's_hardest_055.msk SOLVED in 2,124.089794 milliseconds !
dukuso's_hardest_056.msk SOLVED in 362.830751 milliseconds !
dukuso's_hardest_057.msk SOLVED in 697.073511 milliseconds !
dukuso's_hardest_058.msk SOLVED in 3,070.439399 milliseconds !
dukuso's_hardest_059.msk SOLVED in 31.392537 milliseconds !
dukuso's_hardest_060.msk SOLVED in 592.567491 milliseconds !
dukuso's_hardest_061.msk SOLVED in 131.283725 milliseconds !
dukuso's_hardest_062.msk SOLVED in 5.294528 milliseconds !
dukuso's_hardest_063.msk SOLVED in 186.337370 milliseconds !
dukuso's_hardest_064.msk SOLVED in 499.935327 milliseconds !
dukuso's_hardest_065.msk SOLVED in 2,933.956690 milliseconds !
dukuso's_hardest_066.msk SOLVED in 3,703.020635 milliseconds !
dukuso's_hardest_067.msk SOLVED in 81.654791 milliseconds !
dukuso's_hardest_068.msk SOLVED in 1,566.145418 milliseconds !
dukuso's_hardest_069.msk SOLVED in 16.566351 milliseconds !
dukuso's_hardest_070.msk SOLVED in 6,697.108990 milliseconds !
dukuso's_hardest_071.msk SOLVED in 138.773783 milliseconds !
dukuso's_hardest_072.msk SOLVED in 3,035.243027 milliseconds !
dukuso's_hardest_073.msk SOLVED in 2,812.802465 milliseconds !
dukuso's_hardest_074.msk SOLVED in 1,645.052933 milliseconds !
dukuso's_hardest_075.msk SOLVED in 71.782028 milliseconds !
dukuso's_hardest_076.msk SOLVED in 1,567.040783 milliseconds !
dukuso's_hardest_077.msk SOLVED in 4.113372 milliseconds !
dukuso's_hardest_078.msk SOLVED in 160.286852 milliseconds !
dukuso's_hardest_079.msk SOLVED in 209.047519 milliseconds !
dukuso's_hardest_080.msk SOLVED in 1,637.917668 milliseconds !
dukuso's_hardest_081.msk SOLVED in 158.578255 milliseconds !
dukuso's_hardest_082.msk SOLVED in 106.245906 milliseconds !
dukuso's_hardest_083.msk SOLVED in 422.900117 milliseconds !
dukuso's_hardest_084.msk SOLVED in 586.114716 milliseconds !
dukuso's_hardest_085.msk SOLVED in 343.262901 milliseconds !
dukuso's_hardest_086.msk SOLVED in 276.229521 milliseconds !
dukuso's_hardest_087.msk SOLVED in 100.897181 milliseconds !
dukuso's_hardest_088.msk SOLVED in 585.171858 milliseconds !
dukuso's_hardest_089.msk SOLVED in 75.375781 milliseconds !
dukuso's_hardest_090.msk SOLVED in 5,191.501993 milliseconds !
dukuso's_hardest_091.msk SOLVED in 1,175.437940 milliseconds !
dukuso's_hardest_092.msk SOLVED in 2.269283 milliseconds !
dukuso's_hardest_093.msk SOLVED in 2,440.270202 milliseconds !
dukuso's_hardest_094.msk SOLVED in 7,537.211852 milliseconds !
dukuso's_hardest_095.msk SOLVED in 327.713718 milliseconds !
dukuso's_hardest_096.msk SOLVED in 111.759176 milliseconds !
dukuso's_hardest_097.msk SOLVED in 1,912.464852 milliseconds !
dukuso's_hardest_098.msk SOLVED in 38.651560 milliseconds !
dukuso's_hardest_099.msk SOLVED in 19.043202 milliseconds !
Files Processed: 100, Total Solved: 100, Total time: 172,901.809588, Average Time: 1,729.018096

[CVMichael]

Well, thanks for giving me about 20 tips as to how to modify my program to me more like yours. ;)
Could you highlight those 20 tips somehow ? Cuz I didn’t get any tips from anyone, maybe I’m just too blind to see them.

[eyeRmonkey]

Could you highlight those 20 tips somehow ? Cuz I didn’t get any tips from anyone, maybe I’m just too blind to see them.
:lol: Well maybe its just because my program is so messed up to start with, but he uses a bunch of things that seem much faster that what I am using. I'm not gonna tell you if you don't know. You probably don't see them because you are already doing things similar to what he posted.

I get the feeling you are doing something wrong because nothing takes me more than 20 ms in the IDE and nothing takes more than 6 ms in .EXE.

I wish this contest wasn't a contest because I am so curious to see how everyone is doing what they are doing. I guess I will just have to wait and see.

[Merri]

I've been giving so many tips here that it is making me sick! You can conclude all kinds of stuff from what I've said. A programmer needs his social skills too!

eyeRmonkey: I could do mass output while doing benchmarking for example. Because of the interface, it is easy to use the solver as I like. Currently the visual view isn't linked to my benchmarker in any way.


More sudokus! These include the hardest I've found so far. Beware the minimal sudokus!

[CVMichael]

You can clearly see when my backtracker kicks in...

000.txt - 2.5243 ms
001.txt - 1.6399 ms
002.txt - 3.6608 ms
003.txt - 3.8343 ms
004.txt - 1.3488 ms
005.txt - 4.3369 ms
006.txt - 1.9092 ms
007.txt - 2.1768 ms
008.txt - 2.3430 ms
009.txt - 1.8094 ms
010.txt - 1.4924 ms
011.txt - 2.3746 ms
012.txt - 1.9064 ms
013.txt - 2.5506 ms
014.txt - 1.8986 ms
015.txt - 1.5441 ms
016.txt - 1.4773 ms
017.txt - 1.4980 ms
018.txt - 1.6913 ms
019.txt - 1.5793 ms
020.txt - 1.2935 ms
021.txt - 1.2429 ms
022.txt - 1.0985 ms
023.txt - 1.1085 ms
024.txt - 2,165.0185 ms
025.txt - 1.2644 ms
026.txt - 1.5725 ms
027.txt - 2.4539 ms
028.txt - 3.1381 ms
029.txt - 1.6276 ms
030.txt - 2.3740 ms
031.txt - 2.1142 ms
032.txt - 2.0883 ms
033.txt - 2.2978 ms
034.txt - 2.6434 ms
035.txt - 1.0959 ms
036.txt - 1.2834 ms
037.txt - 1.5156 ms
038.txt - 2.1260 ms
039.txt - 1.0806 ms
040.txt - 13.0533 ms
041.txt - 1.6441 ms
042.txt - 2.5411 ms
043.txt - 14.7834 ms
044.txt - 1.7553 ms
045.txt - 1.5991 ms
046.txt - 1.5955 ms
047.txt - 1.3334 ms
048.txt - 1.5172 ms
049.txt - 1.2474 ms
050.txt - 1.4616 ms
051.txt - 1.7994 ms
052.txt - 1.3764 ms
053.txt - 1.3692 ms
054.txt - 1.9201 ms
055.txt - 1.4960 ms
056.txt - 6.2961 ms
057.txt - 3.2194 ms
058.txt - 1.8399 ms
059.txt - 1.3069 ms
060.txt - 1.1180 ms
061.txt - 1.3627 ms
062.txt - 1.1957 ms
063.txt - 1.0683 ms
064.txt - 1.8108 ms
065.txt - 1.1515 ms
066.txt - 1.4250 ms
067.txt - 4.3992 ms
068.txt - 1.9536 ms
069.txt - 1.2256 ms
070.txt - 1.1806 ms
071.txt - 1.5387 ms
072.txt - 1.6038 ms
073.txt - 2.5154 ms
074.txt - 1.5642 ms
075.txt - 4.5545 ms
076.txt - 2.0142 ms
077.txt - 13.1447 ms
078.txt - 2.1045 ms
079.txt - 1.8279 ms
080.txt - 1.3678 ms
081.txt - 1.2217 ms
082.txt - 1.5798 ms
083.txt - 1.3865 ms
084.txt - 1.3111 ms
085.txt - 1.7122 ms
086.txt - 2.7124 ms
087.txt - 1.4714 ms
088.txt - 2.0648 ms
089.txt - 1.4982 ms
090.txt - 59.5964 ms
091.txt - 23.1236 ms
092.txt - 1.3370 ms
093.txt - 14.7910 ms
094.txt - 1.5555 ms
095.txt - 46.4939 ms
096.txt - 2.4076 ms
097.txt - 1.5220 ms
098.txt - 8.4944 ms
099.txt - 23.8248 ms
100.txt - 1.4287 ms
101.txt - 1.4720 ms
102.txt - 1.5854 ms
103.txt - 1.3457 ms
104.txt - 1.4080 ms
105.txt - 1.5963 ms
106.txt - 2.0964 ms
107.txt - 1.5874 ms
108.txt - 1.4552 ms
109.txt - 1.6097 ms
110.txt - 1.8703 ms
111.txt - 3.0954 ms
112.txt - 16.4867 ms
113.txt - 67.2197 ms
114.txt - 1.7905 ms
115.txt - 1.5921 ms
116.txt - 1.8402 ms
117.txt - 35.7082 ms
118.txt - 389.6585 ms
119.txt - 1.6999 ms
120.txt - 2.8425 ms
121.txt - 586.9436 ms
122.txt - 527.5914 ms
123.txt - 123.2903 ms
124.txt - 1.8921 ms
125.txt - 3.0135 ms
126.txt - 1.5739 ms
127.txt - 1.2356 ms
128.txt - 10.4108 ms
129.txt - 4.1494 ms
130.txt - 2.7478 ms
131.txt - 1,927.2868 ms
132.txt - 1,105.3690 ms
133.txt - 1.2678 ms
134.txt - 1.2742 ms
135.txt - 1.3024 ms
136.txt - 1.5410 ms
137.txt - 1.2650 ms
138.txt - 1.1406 ms
139.txt - 1.4091 ms
140.txt - 1.7388 ms
141.txt - 1.5860 ms
142.txt - 7.2414 ms
143.txt - 4.7660 ms
144.txt - 18.2314 ms
145.txt - 1.2354 ms
146.txt - 1.6661 ms
147.txt - 2.3070 ms
148.txt - 2.0656 ms
149.txt - 4.6436 ms
150.txt - 6.8964 ms
151.txt - 3.2093 ms
152.txt - 1.4150 ms
153.txt - 1.1180 ms
154.txt - 27.4661 ms
155.txt - 1.4561 ms
156.txt - 1.5779 ms
157.txt - 1.2940 ms
158.txt - 1.3762 ms
159.txt - 1.0985 ms
160.txt - 3.2728 ms
161.txt - 1.3046 ms
162.txt - 1.1054 ms
163.txt - 1.0675 ms
164.txt - 1.2166 ms
165.txt - 1.0627 ms
166.txt - 1.4940 ms
167.txt - 1.2060 ms
168.txt - 2.3274 ms
169.txt - 1.1971 ms
170.txt - 1.3309 ms
171.txt - 1.9651 ms
172.txt - 1.9438 ms
173.txt - 237.1480 ms
174.txt - 1.3985 ms
175.txt - 1.1680 ms
176.txt - 33.5540 ms
177.txt - 3.2552 ms
178.txt - 1.4963 ms
179.txt - 1.0946 ms
180.txt - 1.2113 ms
181.txt - 5.6348 ms
182.txt - 6.2782 ms
183.txt - 26.4176 ms
184.txt - 26.5500 ms
185.txt - 68.9856 ms
186.txt - 4.4967 ms
187.txt - 1.6952 ms
188.txt - 670.1908 ms
189.txt - 198.3515 ms
190.txt - 401.3748 ms
191.txt - 479.8657 ms
192.txt - 1.7092 ms
193.txt - 3.3415 ms
194.txt - 2.2631 ms
195.txt - 2.6632 ms
196.txt - 4.6738 ms
197.txt - 1.7681 ms
198.txt - 7.4711 ms
199.txt - 2.3598 ms
200.txt - 1.1496 ms
201.txt - 1.2275 ms
202.txt - 17.7031 ms
203.txt - 1.1018 ms
204.txt - 1.2094 ms
205.txt - 1.2460 ms
206.txt - 3.7854 ms
207.txt - 1.3362 ms
208.txt - 1.2080 ms
209.txt - 1.2155 ms
210.txt - 2.7040 ms
211.txt - 4.0019 ms
212.txt - 1.2261 ms
213.txt - 1.2817 ms
214.txt - 1.5742 ms
215.txt - 1.3999 ms
216.txt - 1.4611 ms
217.txt - 1.9525 ms
218.txt - 1.4502 ms
219.txt - 1.3136 ms
220.txt - 9.6685 ms
221.txt - 1.3965 ms
222.txt - 1.5614 ms
223.txt - 1.0677 ms
224.txt - 1.1895 ms
225.txt - 1.3044 ms
226.txt - 1.1222 ms
227.txt - 1.6315 ms
228.txt - 1.1457 ms
229.txt - 1.4474 ms
230.txt - 1.3091 ms
231.txt - 2.2145 ms
232.txt - 2.2321 ms
233.txt - 214.5468 ms
234.txt - 0.9127 ms
235.txt - 0.9163 ms
236.txt - 1.1158 ms
237.txt - 1.5547 ms
238.txt - 1.4602 ms
239.txt - 1.9835 ms
240.txt - 1.1862 ms
241.txt - 1.7664 ms
242.txt - 1.3854 ms
243.txt - 3.3957 ms
244.txt - 1.9391 ms
245.txt - 2.2852 ms
246.txt - 1.6265 ms
247.txt - 3.0825 ms
248.txt - 2.3813 ms
249.txt - 1.6485 ms
250.txt - 1.2588 ms
251.txt - 1.5019 ms
252.txt - 1.4295 ms
253.txt - 1.9860 ms
254.txt - 1.3041 ms
255.txt - 1.2560 ms
256.txt - 0.9501 ms
257.txt - 2.3631 ms
258.txt - 1.4809 ms
259.txt - 4.0541 ms
260.txt - 4.0631 ms
261.txt - 2.0218 ms
262.txt - 2.0195 ms
263.txt - 2.2469 ms
264.txt - 1.9678 ms
265.txt - 2.0215 ms
266.txt - 2.8962 ms
267.txt - 109.0035 ms
268.txt - 1.7986 ms
269.txt - 3.2462 ms
270.txt - 1.9257 ms
271.txt - 1.6617 ms
272.txt - 1.4591 ms
273.txt - 37.5411 ms
274.txt - 86.3216 ms
275.txt - 1.5591 ms
276.txt - 23.0764 ms
277.txt - 24.5313 ms
278.txt - 242.9060 ms
279.txt - 53.6814 ms
280.txt - 1.6443 ms
281.txt - 2.1732 ms
282.txt - 187.9719 ms
283.txt - 227.5588 ms
284.txt - 0.9300 ms
285.txt - 1.0236 ms
286.txt - 0.9417 ms
287.txt - 0.9303 ms
288.txt - 1.2446 ms
289.txt - 1.2625 ms
290.txt - 1.8128 ms
291.txt - 1.1476 ms
292.txt - 1.3999 ms
293.txt - 4.5310 ms
294.txt - 2.4685 ms
295.txt - 1.1985 ms
296.txt - 1.6913 ms
297.txt - 1.8972 ms
298.txt - 1.1985 ms
299.txt - 1.2133 ms
300.txt - 3.6063 ms
301.txt - 1.6997 ms
302.txt - 1.7290 ms
303.txt - 2.3475 ms
304.txt - 3.5611 ms
305.txt - 1.2546 ms
306.txt - 1.7466 ms
307.txt - 1.2566 ms
308.txt - 1.4812 ms
309.txt - 1.2963 ms
310.txt - 5.8952 ms
311.txt - 1.4616 ms
312.txt - 1.2756 ms
313.txt - 1.7656 ms
314.txt - 1.3309 ms
315.txt - 1.9461 ms
316.txt - 1.5927 ms
317.txt - 1.7273 ms
318.txt - 6.4869 ms
319.txt - 6.9157 ms
320.txt - 2.3590 ms
321.txt - 1.4340 ms
322.txt - 1.1091 ms
323.txt - 5.1484 ms
324.txt - 11.4285 ms
325.txt - 21,115.4932 ms
326.txt - 1.9827 ms
327.txt - 1.1555 ms
328.txt - 1.9019 ms
329.txt - 1.7242 ms
330.txt - 1.1974 ms
331.txt - 1.2722 ms
332.txt - 2.0813 ms
333.txt - 1.2010 ms
334.txt - 2.2743 ms
335.txt - 4.8221 ms
336.txt - 2.0695 ms
337.txt - 2.2869 ms
338.txt - 2.7138 ms
339.txt - 5.9994 ms
340.txt - 1.7100 ms
341.txt - 2.1274 ms
342.txt - 1.3647 ms
343.txt - 1.7723 ms
344.txt - 21.6606 ms
345.txt - 1.5130 ms
346.txt - 1.4669 ms
347.txt - 1.4276 ms
348.txt - 2.6095 ms
349.txt - 2.7621 ms
350.txt - 2.2874 ms
351.txt - 3.0127 ms
352.txt - 2.6696 ms
353.txt - 1.3521 ms
354.txt - 1.5318 ms
355.txt - 1.8106 ms
356.txt - 1.4516 ms
357.txt - 1.4767 ms
358.txt - 1.2449 ms
359.txt - 1.9022 ms
360.txt - 361.5337 ms
361.txt - 236.3859 ms
362.txt - 1.9494 ms
363.txt - 2.6196 ms
364.txt - 1.4915 ms
365.txt - 2.5825 ms
366.txt - 1.7539 ms
367.txt - 1.4435 ms
368.txt - 1.7161 ms
369.txt - 1.7969 ms
370.txt - 4.7042 ms
371.txt - 3.0537 ms
372.txt - 1.8821 ms
373.txt - 1.7731 ms
374.txt - 1.9718 ms
375.txt - 1.4703 ms
376.txt - 0.9954 ms
377.txt - 4.3137 ms
378.txt - 1.2261 ms
379.txt - 1.3312 ms
380.txt - 1.0878 ms
381.txt - 1.3024 ms
382.txt - 2.3120 ms
383.txt - 2.0609 ms
384.txt - 1.1166 ms
385.txt - 2.3299 ms
386.txt - 2.4400 ms
387.txt - 1.1203 ms
388.txt - 2.0933 ms
389.txt - 1.2493 ms
390.txt - 1.1144 ms
391.txt - 1.2513 ms
392.txt - 4.1773 ms
393.txt - 3.7508 ms
394.txt - 3.3091 ms
395.txt - 1.0767 ms
396.txt - 2.2911 ms
397.txt - 2.5045 ms
398.txt - 1.7458 ms
399.txt - 9.1302 ms
400.txt - 1.5270 ms
401.txt - 1.2694 ms
402.txt - 1.5899 ms
403.txt - 6.9984 ms
404.txt - 1.4055 ms
405.txt - 3.1686 ms
406.txt - 2.2707 ms
407.txt - 1.2387 ms
408.txt - 2.4092 ms
409.txt - 1.5748 ms
410.txt - 1.8944 ms
411.txt - 1.7974 ms
412.txt - 1.4086 ms
413.txt - 1.2680 ms
414.txt - 1.5644 ms
415.txt - 1.6050 ms
416.txt - 1.6125 ms
417.txt - 1.3060 ms
418.txt - 2.2151 ms
419.txt - 1.3884 ms
420.txt - 3.7485 ms
421.txt - 2.0447 ms
422.txt - 1.2345 ms
423.txt - 1.7072 ms
424.txt - 1.8807 ms
425.txt - 4.9638 ms
426.txt - 2.1145 ms
427.txt - 2.5554 ms
428.txt - 1.9374 ms
429.txt - 2.1673 ms
430.txt - 1.4885 ms
431.txt - 17.9185 ms
432.txt - 5.6007 ms
433.txt - 2.5783 ms
434.txt - 1.8189 ms
435.txt - 1.8069 ms
436.txt - 1.0962 ms
437.txt - 1.9885 ms
438.txt - 1.3789 ms
439.txt - 1.1270 ms
440.txt - 1.5904 ms
441.txt - 1.7938 ms
442.txt - 1.3627 ms
443.txt - 1.2074 ms
444.txt - 1.4555 ms
445.txt - 2.3179 ms
446.txt - 2.1503 ms
447.txt - 1.0613 ms
448.txt - 1.8025 ms
449.txt - 1.2951 ms
450.txt - 1.7851 ms
Files Processed: 451, Total Solved: 451, Total time: 33,173.741076, Average Time: 73.555967

I'm at the point of giving up on this thing, I've spent a TON of time on this, and I didn't make much improvement in speed.

[Merri]

I give you a BIG tip: make your backtracker use the same code you use for logic. My history: I first made my fast logic thingy, then I made a different backtracker, then I combined the both, then I saw I just couldn't make it good with the backtracker I had, I dumbed it out and made a new backtracker based on the existing logic.

[eyeRmonkey]

You can clearly see when my backtracker kicks in...
....
I'm at the point of giving up on this thing, I've spent a TON of time on this, and I didn't make much improvement in speed.
How did you get your times down to so low all of the sudden? The last set of times you posted were in the 50-1000 range. Now you have 1-2 ms and 1000-2000ms. Were the last speeds you posted from the IDE?

[ntg]

For all the lurkers out there: :wave:

NotLKH1, 69 files, ~15ms
NotLKH2, 532 files, ~187ms
NotLKH3, 123 files, ~55ms
Merri's Hardest, 337 files, ~513ms
Dukuso's Hardest, 100 files, ~275ms

No time for minimum sudokus as they don't have the format of the rest *.msk files. Attaching an image of my user interface - nothing fancy here. I output solutions of all directory *.msk files on the clipboard like:

Filename: E:\Projects\dotNetProjects\_Personal_\Soduku\bin\FILES\0003_0003_022.msk
Solved in 0,46628574 ms
.........
..4..3...
.2.91.4.6
.........
...32..1.
95.....32
.1...5..7
..7....53
..6.4....


189476325
764253198
325918476
273591864
648327519
951864732
812635947
497182653
536749281


Filename: E:\Projects\dotNetProjects\_Personal_\Soduku\bin\FILES\0004_0001_022.msk
Solved in 0,34931381 ms
9..2.....
....5...8
..4.1...6
59...8...
63...7...
......95.
...9.3...
.6....84.
..1...6..


983276514
126354798
754819326
597148263
632597481
418632957
845963172
369721845
271485639

My tip: when you're done applying logic rules and you have to start guessing, don't just start with the first empty cell. Finding the right cell makes a huge difference in speed. :bigyello:

[Merri]

Oh, oops. I didn't notice the format difference, my solver can load several file formats :D Actually, any file... It is fun to try to load Windows system files and see if there happen to be any valid sudokus!



Humm... wonder if I'll...


...I shall persist!


...no...


...what is this weird feeling...


...I can't hold it! NO!


NotLKH1: 2.9 ms (0.042 ms per file)
NotLKH2: 39 ms (0.073 ms per file)
NotLKH3: 13 ms (0.106 ms per file)
NotLKH4: 37 ms (0.071 ms per file)
Hardest: 85 ms (0.252 ms per file)
dukuso's TOP 100: 38 ms (0.38 ms per file)
Minimum: 73 ms (0.162 ms per file)

There we go.

[NotLKH]

...I can't hold it! NO!

...
There we go.
lol!

[Merri]

Btw... should I some time actually solve a sudoku by myself? Still have never solved one.

[NotLKH]

I suggest, at the very least,
Run your progie on some samples, but without backtracking.

Then output your Cells, the values of the solved ones, and the could_be's of the unsolved cells, in a human friendly fashion,

and THEN try to solve that by hand.

You should see some more strategies to throw into your progie that way.

:wave:
-Lou

[manavo11]

http://www.vbforums.com/showthread.php?t=351477

Added the updates suggested. Just FYI :)

[Merri]

Well, I've pretty much read up about all the strategies :) I'm thinking about it as a programming task, not as a solver. There is only one potential logic left that might be fast enough to implement into my solver... about all the other ones would be more of performance killers than of help. So I can't take that as an excuse to solve one :D

[NotLKH]

Looks good.
"Option to output the solved sudoku in a folder in the app path folder with your username"

You might want to restrict the output filename a little bit more.

Someone might name them with no relation to the input file whatsoever.

I Doubt it, but its possible.

:wave:

[edit]
"Time and keep track of the time for each sudoku solved and output in a list at the end (with the total time if possible)"

You might also want to be strict about how the entries in this list are formatted.
What is the pertinant data?

Filename and seconds
Anything else?

What is the order of the data?
What deliminates each line of data?
What deliminates between the data of each line?
Some people use commas, some decimal points for the time. Is this an issue?

How should the total time entry be formatted and where should it go?


IF someones solver fails to solve a soduko, they still need to enter the time it took.

Should each line report the status of the processed sudoku? ie... "Solved" or "Failed"?

Hmmm, I think these are about all the potential issues.

:)
-Lou

[manavo11]

Lou, the input ones are *.msk and the output ones *.sol?

I'll edit it, thanks for the suggestion :)

Edited! Any more suggestions?

Thanks again :)

[eyeRmonkey]

FileName001.msk: (SOLVED or FAILED) in 0,000000 seconds!
FileName002.msk: (SOLVED or FAILED) in 0,000000 seconds!
FileName003.msk: (SOLVED or FAILED) in 0,000000 seconds!
.
.
.
Total Time: 0,000000 seconds
I'm not sure why we are using a comma in the seconds. Is that suppose to be the decimal point in seconds (not milliseconds)? I'm assuming so.

[manavo11]

Yep. That's how I know it, "," decimal point and "." to show thousands, millions, etc...

[eyeRmonkey]

Yep. That's how I know it, "," decimal point and "." to show thousands, millions, etc...
Ok, maybe I am an idiot, but you just confused me more. First off, since when does a "." mark thousands, millions, etc. and do you want any "."s in the time or just a "," where the decimal point normally is?

[manavo11]

That's how we learn it in Greece :ehh: The "." isn't needed. Or use the dot if you want in the Format function... Doesn't make much difference...

[eyeRmonkey]

More sudokus! These include the hardest I've found so far. Beware the minimal sudokus!

Ok, I used the program I made to fix dukuso's puzzles and modified it a little to fix merri's "minimum sudokus." I attached them here.

Note: the first (original) file (000.txt) was in a different format then the rest (and caused my program to not output the right type of file) so there might be others in the group, if so please let me know.

[eyeRmonkey]

That's how we learn it in Greece :ehh: The "." isn't needed. Or use the dot if you want in the Format function... Doesn't make much difference...
Now I have choices to make? Thats no good. I need to be told exactly what to do. I have no decision making capacity. I guess I will just use the format function then replace "." with ","

I just needed to clear up that the , represented the decimal point in seconds and that we weren't talking about miliseconds or 1000 seconds or something like that.

[manavo11]

I specified in the rules that the "," is the decimal point character :)

[ntg]

...what is this weird feeling...
...I can't hold it! NO!

lol merri :lol:

[eyeRmonkey]

I specified in the rules that the "," is the decimal point character :)
Thanks. ;)

I'll stop being dumb now. :D

[eyeRmonkey]

Hey Merri, can you define what a "minimum sudoku" is? How is it different than a normal one?

[dukuso]

maybe we should stop measuring time in ms...

Let 1 Merri (mr) be the number of CPU-cycles needed by Merri's solver
to solve one of the easy sudokus. (about 72000)
My solver takes about 4mr for a msk_001-sudoku and 20mr for a top100-sudoku.
My exact-cover matrix has 729*324 (=placements*constraints) cells,
that's 3.3mr, but the matrix is sparse, so I only store the
addresses of the nonzero entries which is 2*0.04mr .
Would I process this list just only for each of the about 55 placements
of a sudoku-clue with one examination per CPU-cycle, then I would already
need 4.4mr, so there must be a better method.

I guess, if your solver takes 10mr for an average sudoku,
that's already pretty good...

[Merri]

Hey Merri, can you define what a "minimum sudoku" is? How is it different than a normal one?

It has only 17 starting values, yet the puzzle has only one solution. There is no known single solution puzzle with only 16 given values. If we put it straight, I think some of this kind of puzzles cause the most work for a backtracker.

[dukuso]

the number of clues has not been a useful measure for hardness.
In fact most of the 17-clue-puzzles from Gordon Royle's webpage
were rather easy to solve.

[Merri]

Yes, most of course. But some of them are the hardest my solver has got its hands into, thus there is some point behind my words.

[dukuso]

you're right. I never noticed this. Distribution of clues in my 100 hardest:
10,0,1,1,65,0,2,9,5,4,1,1 counts for 17,18,..,28 clues.
Even my 3 top-hardest are 17-clue-puzzles.
I'll ask Gordon for his other 17-clue sudokus, he has about 5000 of them !

[Merri]

The interesting part being: I thought some of them must be the hardest when I first read about them :)

[dukuso]

that's what the creator thought too. But it soon turned out that they were not, see:
http://www.sudoku.com/forums/viewtopic.php?t=605&postdays=0&postorder=asc&start=15
having this in mind, I didn't very much check which of these finally made their
way into my top100 list.
In the hardest 17-puzzle, you can fill in some numbers and it's still hard:

.18...73.
...3.72..
.73......
....713..
6...3..4.
3........
4..5....3
.2..83...
.3.....6.

[Something Else]

lol.

The only way that is a seventeen is if you think .18...73. is a 2 entry! But it really is a 4 entry.

.18...73.
...3.72..
.73......
....713..
6...3..4.
3........
4..5....3
.2..83...
.3.....6.

That is a 24 entry.

BTW, I've been marking my sol & msk files since the getgo with the #Entries as the first number in the filename.


:wave:
-Lou

[Merri]

The discussion you pointed to... he clearly haven't thought in that point that there are always easy ones and hard ones. Majority of the puzzles are always easy, otherwise it wouldn't be hard to find the hard ones. So majority with 17 clues are easy, but the select few among them are very hard.

Btw, that one isn't hard. Atleast for my solver.


Something Else: re-read his post :)

[Something Else]

"In the hardest 17-puzzle, you can fill in some numbers and it's still hard:"
and then its followed with a puzzle with 24 entries.

Its NOT sayingthat its a 17 entry WITH some cells solved, its implying that if you look at this 17 entry, you'll find some numbers to fill in.

If they were filled in, how would you know what numbers were easily filled in?

Or is this not what you're talking about?

:wave:
-Lou

[Merri]

I'm saying that, atleast to me, he is clearly stating he is giving a 17 puzzle with additional numbers included (which is different thing than solved) and claiming it still is hard with those numbers included.

In the other hand... it is quite hard to follow what dukuso is saying or meaning with what he says every now and then :D

[dukuso]

I'm taking the first puzzle from http://magictour.free.fr/top100
which is by far the hardest for my solver which I ever found,
even when considering 1000 random equivalence transformations
of that sudoku :

.18...7.....3..2...7...........71...6......4.3........4..5....3.2..8...........6.


.18...7..
...3..2..
.7.......
....71...
6......4.
3........
4..5....3
.2..8....
.......6.

I can't understand why it's so easy to solve for Merri.
I swapped the 1s and 3s in that sudoku, since one of my programs solves for
the one-digit. You can fill in all 9 threes in above sudoku by relatively simple logic.
These then are painted as ones and vice versa. Plus one seven could also be filled in.
That was the 24-clue-sudoku which I posted.
The point is, that this 24-clue sudoku was no easier for my solver
than the original 17-clue-puzzle.
Clear now ?

[NotLKH]

Especially if you notice that if you count the number of run on number groups per line, you DO have 17 such groups:

.18...73.
...3.72..
.73......
....713..
6...3..4.
3........
4..5....3
.2..83...
.3.....6.

Line 1: 18, 73 : 2 run on groups of numbers
Line 2: 3, 72 : 2 RunOn's
Line 3: 73 : 1 RunOn
Line 4: 713 : 1
Line 5: 6,3,4 : 3
Line 6: 3 : 1
Line 7: 4,5,3 : 3
Line 8: 2, 83 : 2
Line 9: 3, 6 : 2

So, # RunOn's = 2 + 2 + 1 + 1 + 3 + 1 + 3 + 2 + 2 = 17
Which is coincidentally the number of the order that he claims it to be.

So, if he did start with a true 17, ie.. 17 single hints given,
And then added his fillins, resulting in 24 revealed cells, somehow it ended up with 17 runon groups of numbers, which led me to think that he was counting the groups instead of the individual numbers themselves.

I wonder what it looked like before he added his fillins, if this is the case.

:wave:
-Lou

[NotLKH]

I'm taking the first puzzle from http://magictour.free.fr/top100I can't understand why it's so easy to solve for Merri....The point is, that this 24-clue sudoku was no easier for my solver
than the original 17-clue-puzzle.
Clear now ?

Thanks!
-Lou

[Merri]

The point is, that this 24-clue sudoku was no easier for my solver than the original 17-clue-puzzle.

Maybe because the result is different. The numbers 1 and 3 switch their place on several occasions. The 24 clue one is a bit harder for my solver as well. But since the numbers switch their place in the solution, it is a completely different sudoku.

[eyeRmonkey]

Ok, not to change the subject, buuuuut...

I was wondering about when the timer should start. Here me out:

Everyone has to store the possiblities that each cell could be in some manner. Lets assume they use a string to do this (although I hope no one is). The string would originally be "123456789" for each cell.
Now lets assume that the actual value of each cell is stored in a different (byte?) array.
When the original board is loaded into the solver the program sets the byte array to the given numbers.
Now the time starts
Now the solver takes any cell that was originally solved for and removes the rest of the possiblites from the string for that cell.
(Now the solver does everything else.)
Time stops.

My questions is if the step in bold should be included in timing or not. Because if someone did is similarly, but instead automatically eliminated all the possibilities in the string AND set the byte array before the time started that wouldn't necessarily be against the rules.

Did that make sense?

I know not everyone will do theirs in a manner similar to this, but I think some people will.

[Merri]

As told before, I have a function called PrepareSudoku. What it actually does is, besides initializing my optimization arrays (only in first call), convert the given array into the internal format I use to process in. However, it does not do any real calculation. It only fills the array and counts how many solved cells there are. It does not work out any possibles. Thus all the real work is done by the solver, which I time. PrepareSudoku is not included in timing.

Removing possibles should be counted in the timing, because that is what the whole thing is about. But I think setting the sudoku can be counted as initialization, which is not required to be timed (though in the other hand it wouldn't make a big difference).

[eyeRmonkey]

That is how I have it now Merri (the way you just mentioned).

I was just thinking that if someone took a class approach then maybe sudoku.setval(cellnumber, value) might automatically remove all other possibles. What I mean is that when they are loading the original puzzle, their class will do work (untimed) that out methods time. They would have a leg up on us, just by design.

[Merri]

True, but doing it that way is slow, so there isn't much to complain :) Though, that would be solving the puzzle, because it is using a solving method.

[eyeRmonkey]

Yeah, plus its a waste... nevermind. I think I won't finish that because I would be giving away more hints (not that I have that many to give).

[dukuso]

I wrote that my top1-example is still hard for my solver when
I rotate and permute the sudoku without destroying its structure and the
number of solutions.
And I wrote that I don't understand why it's so easy for Merri's solver.

Now I permuted the order of the constraints and placements,
and that did indeed make my solver solve it much faster.
(but without being faster on the list as a whole)

So, what was happening ? Presumably I went into a
large region of the search tree with no solution
and lots of useless branches, while Merri avoided this region
either by mere luck or by lookahead-prediction.

But such things happen rarely and it might be better to
tolerate it rather than to waste time on predicting how to
avoid it ?!?
I know, there are also sudokus which my program solves much
faster than Merri's - it would help, if we were able to
detect which problems are best solved by which method.

It makes me also believe that further optimizations
in the algorithm are possible....

[dukuso]

can't we forget about the contest and work together on the
best program in teamwork instead ?
I mean, it's better to exchange ideas right now,
since after the contest people will be no longer interested to
improve the programs.

[dukuso]

Gordon Royle kindly uploaded all his 17-clue-puzzles !

4.6sec*GHz for these 7600:
http://www.csse.uwa.edu.au/~gordon/sudoku17

[dglienna]

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.

[dukuso]

wouldn't that be a cool contest, if people would collaborate to find
the best program and everyone is _somehow_ scored by the
"value" of her contribution ?

[Merri]

Well, only 11 days before the contest is over. I make my own code public right away after the deadline, atleast elsewhere if not here. I'm actually expanding my program in other ways, I have made a multifile converter for an example (still a bit buggy though). Should next make the required feature for the contest, I still don't save the data in the required way...

My problem is starting to be that there isn't much to improve. The list of includeable logics is pretty short... probably the only one I can do to speed things up is Nishio. Probably I'll continue to do some work even after the contest, if my interest just keeps going on.

The contribution contest would be pretty hard to rate. It sounds nice as an idea, but it doesn't work well in practise. Atleast I think it is unlikely to be so.

Her contribution sounds a bit weird btw :D

[Merri]

Here are the 7611 17 clues in the contest format :) Though... the ZIP file contains a 7-zip file. I had to do this because for some reason the ZIP file became over 1 MB in size, even though the files it stored took only about 300 kB compressed! So, I decided to use the best format I know: ending result is 129 kB. So... curse the ZIP.

How to uncompress:
- extract clues.7z.txt from the ZIP file
- rename the file to clues.7z
- extract in a program that can open 7z files (IZarc (http://www.florida.plus.com/izarc/) is a good one)


Oh... and solved them all in ~1710 ms.

[Merri]

But they're in msk format already in my post?

[eyeRmonkey]

Ignore me. I have edited that reply 5 times then re-read yours and notice I am still worng. Let me edit it again.

EDIT: Ok, I deleted that reply. Now, what I was trying to say is can you upload them in separate .zip's?

[Merri]

In the other hand... you could always get my converter program (http://merri.net/sudoku.zip) to change sudoku files from a format to another. You can get that list for example, save it as a text file and then convert that "batch" file to separate sudokus. The converter can save five different file formats and read several others.



I hate silly TYPOS!

[eyeRmonkey]

Nice one. Yours is much more flexible than mine. I had to modify mine every time I was dealing with a different format.

EDIT: MERRI!!! I think I am going to wet myself. That is beautiful! So clean... SO FAST!! Gimme gimme code! GIMME! ... Ok, I'm done. Deep breaths. I'm better now. :wave:

EDIT: Can I steal your icon? I think I'll resource hack it, unless you don't want me to.

[Merri]

You shouldn't steal my icon! It is a copyrighted work afterall! ;) I'll sue you!

Code will come in... what, 11 days?

[ntg]

Hey lurkers, ;) about 3secs for those 7611 puzzles. I won't do much more work on this, so I'll be posting in a few days because my girlfriend is pressuring me to take vacations on something called the real world - we'll probably go to the place on attached pics (try not to cry too much everyone :D ).

[Merri]

Well, as your wordings in each of your posts say... bit happens. Try to survive!

[eyeRmonkey]

You shouldn't steal my icon! It is a copyrighted work afterall! ;) I'll sue you!

Code will come in... what, 11 days?
Oh, I didn't know you made the icon. In that case, I will use one that doesn't relate to sudoku in ANY way. ;)

[ntg]

BTW, I scrapped my entire project and created a new one that I'm sure will beat everyone's entry. I'll only ask manavo11 to save everyone's puzzle solutions to disk and run my code last.
Private Sub cmdWinTheContest_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles cmdWinTheContest.Click

Dim SW As New StopWatch

Dim files() As String = System.IO.Directory.GetFiles(mskDir, "*.sol.*")
For i As Integer = 0 To files.GetUpperBound(0)
If files(i).IndexOf("merri") > -1 Then
System.IO.File.Move(files(i), files(i).Replace("merri", "ntg"))
Else
System.IO.File.Delete(files(i))
End If
Next

MessageBox.Show("Time=" + (SW.Peek() / 10).ToString("N8") + " - beat THAT!", "I win", MessageBoxButtons.OK)

SW = Nothing

End Sub

[eyeRmonkey]

:lol: :lol: :lol:

Nice one ntg. I had been wondering if someone would try to sneak something like that into their code to try to cheat, but I doubt it.

[Merri]

At this point I can only say: VB.NET looks horrible! Good thing I don't need to do those complicated and long lines...

Wonder if my solver is faster than just moving files... atleast on my computer it took much longer creating the files than solving them :D

[manavo11]

BTW, I scrapped my entire project and created a new one that I'm sure will beat everyone's entry. I'll only ask manavo11 to save everyone's puzzle solutions to disk and run my code last.

What makes you think you're so special? :p :D j/k

[eyeRmonkey]

I'm not sure if this was ever clarified, but are VB.net and VB6 going to be judged together or separately?

[manavo11]

Separately!

[Merri]

Hey, 10 days still to go... I could take this VB2005 and make a VB.NET2 version of my code, too. I'm sure everyone would appreciate that! :D

[eyeRmonkey]

/slap merri

I could go make a javascript version of my code seeing as how that is the only other language that I know (unless you count the 1 line of C++ code I can write). I'm sure I would win in that catagory. :)

[eyeRmonkey]

Someone say something. I check this thread 20 times a day it seems. I'm getting sick of seeing my reply as the last one. ;)

How is the code going? Someone want to post times (not that it matters all that much). How about you just post your entire project, then I can combine all you good ideas with my project. Sounds good, right? :D