Contest 6 - Sudoku solver - Discussion

[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]

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]

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.

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

Got a link?



-Lou

[manavo11]

No?

Maybe it wasn't you? I remember someone saying that 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

http://www.vbforums.com/showpost.php...2&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!


-Lou

[manavo11]

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

[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!

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

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?


-Lou

[Merri]

Hehe, I tell a lot it seems 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:

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?


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

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]

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!

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

[dukuso]

put all sudokus in one file, one row per sudoku