Contest 6 - Sudoku solver - Discussion

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.

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

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.

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

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

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?

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:

Code:

---

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

---

Code:

---

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

---

Code:

---

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.

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.

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

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?

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?

True, it would be more like luck.

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

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

Quote:

---

Originally Posted by 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) :)

---

:confused:
Got a link?


:confused: :confused:
-Lou

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

Close, someone was asking you but wikipedia answered :D

http://www.vbforums.com/showpost.php...2&postcount=89

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

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

Quote:

---

Originally Posted by Merri

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

Code:

---

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:

Code:

---

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

---

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.

/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

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

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

VB Code:

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:

VB Code:

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.

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

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

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

Quote:

---

Originally Posted by Merri

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

VB Code:

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:

VB Code:

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:

VB Code:

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

Quote:

---

Originally Posted by Merri

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

Quote:

---

Originally Posted by eyeRmonkey

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:

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

Whats your opinion on this theoretical setup?

:wave:
-Lou

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

Quote:

---

Originally Posted by NotLKH

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:

1. the 81 cells and the 27 groups
2. 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?

Quote:

---

Originally Posted by Merri

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

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

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?

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.

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

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

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.

Quote:

---

Originally Posted by 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.

---

*stabs Merri in the hear and ran widly around holding a disk with his code on it over my head*

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

put all sudokus in one file, one row per sudoku

Quote:

---

Originally Posted by Merri

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

Quote:

---

Originally Posted by dukuso

put all sudokus in one file, one row per sudoku

---

What does that have to do with anything?

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

Hello, hhalkin...
gonna join the contest?

:wave:
-Lou

The more the Merrier. ;)

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.

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 !

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

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

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.

Quote:

---

Originally Posted by 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 !

---

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

Quote:

---

Originally Posted by 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?

---

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

Quote:

---

Originally Posted by 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.

---

Let's see :)

Quote:

---

Originally Posted by NotLKH

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

Quote:

---

Originally Posted by NotLKH

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

Quote:

---

Originally Posted by NotLKH

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

Quote:

---

Originally Posted by 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

---

Yes

Quote:

---

Originally Posted by Merri

- the folder files must be easy to benchmark

---

What exactly do you mean?

Quote:

---

Originally Posted by Merri

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

Quote:

---

Originally Posted by Merri

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

---

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

Quote:

---

Originally Posted by Merri

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

Quote:

---

Originally Posted by 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.

---

Yes :)

Quote:

---

Originally Posted by NotLKH

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

Quote:

---

Originally Posted by NotLKH

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.

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

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.

Quote:

---

Originally Posted by dukuso

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

---

I threw together a program to split these into .msk files.

Quote:

---

Originally Posted by 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).

---

So how do you suggest we show what our solver got as a solution?

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:

VB Code:

OpenSudoku "c:\test.sdk"
SolveSudoku

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

VB Code:

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.

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.