[RESOLVED] [VB] Sudoku Solver

Re: [VB] Sudoku Solver

Quote:

Originally Posted by CVMichael

254869317
713542896
869371425
972458631
638127954
541693278
187934562
495216783
326785149

Time taken: 1.06426517520869 Seconds

Not Bad at all!
Now, how fast can your progie solve it?

:wave:

Re: [VB] Sudoku Solver

Quote:

Originally Posted by NotLKH

Not Bad at all!
Now, how fast can your progie solve it?

:wave:

Ammm.... that was resolved by my program...

I don't think any human being can solve that in a second....

Re: [VB] Sudoku Solver

NotLKH, I saw somethingElse with your wife...but over to the importent stuff. Pino added this to the contest thread:

http://www.vbforums.com/showthread.p...27#post2102227

If you have more stuff or want to alter something, I guess Pino or Manavo is the guys to talk to. They are often online and have all the privelidges they need to make you happy..:)

Again, thanks a bunch.
- ØØ -

Re: [VB] Sudoku Solver

Thanks!
-Lou

Re: [VB] Sudoku Solver

Can anyone post their timing results ?

I wanna compare, to know if I should spend time improving my solver or not ?

Re: [VB] Sudoku Solver

Quote:

Originally Posted by CVMichael

Can anyone post their timing results ?

I wanna compare, to know if I should spend time improving my solver or not ?

Depends on the difficulty level. I've got down to 130 ms but there are still some bugs 'cos it does not solve some puzzles. I think I'm trying to take too many shortcuts :sick: It worked OK when it was taking 1.5 seconds!!

Re: [VB] Sudoku Solver

This with the current code I have. I'm thinking about changing my approach, I guess I just figured out how I can do one fast (relatively short) general purpose algorithm instead of coding hundreds and hundreds of lines of human logic.

Code:

0000_0001_022.msk: SOLVED in 0,000082 seconds! 0001_0001_022.msk: SOLVED in 0,000135 seconds! 0002_0003_022.msk: SOLVED in 0,000111 seconds! 0003_0003_022.msk: SOLVED in 0,000258 seconds! 0004_0001_022.msk: FAILED TO SOLVE (0,000219 seconds) 0005_0003_022.msk: FAILED TO SOLVE (0,000133 seconds) 0006_0003_023.msk: SOLVED in 0,000197 seconds! 0007_0001_023.msk: SOLVED in 0,000096 seconds! 0008_0003_023.msk: FAILED TO SOLVE (0,000123 seconds) 0009_0001_023.msk: SOLVED in 0,000090 seconds! 0010_0003_023.msk: SOLVED in 0,000099 seconds! 0011_0001_023.msk: FAILED TO SOLVE (0,000199 seconds) 0012_0001_023.msk: FAILED TO SOLVE (0,000141 seconds) 0013_0003_023.msk: SOLVED in 0,000201 seconds! 0014_0001_023.msk: SOLVED in 0,000127 seconds! 0015_0003_023.msk: SOLVED in 0,000104 seconds! 0016_0003_023.msk: FAILED TO SOLVE (0,000072 seconds) 0017_0003_023.msk: FAILED TO SOLVE (0,000087 seconds) 0018_0001_023.msk: SOLVED in 0,000126 seconds! 0019_0001_023.msk: SOLVED in 0,000123 seconds! 0020_0001_023.msk: SOLVED in 0,000236 seconds! 0021_0000_023.msk: SOLVED in 0,000072 seconds! 0022_0003_023.msk: FAILED TO SOLVE (0,000113 seconds) 0023_0003_023.msk: SOLVED in 0,000256 seconds! 0024_0001_023.msk: SOLVED in 0,000118 seconds! 0025_0003_023.msk: FAILED TO SOLVE (0,000163 seconds) 0026_0001_023.msk: SOLVED in 0,000082 seconds! 0027_0001_023.msk: SOLVED in 0,000156 seconds! 0028_0000_023.msk: SOLVED in 0,000075 seconds! 0029_0003_023.msk: SOLVED in 0,000248 seconds! 0030_0003_023.msk: FAILED TO SOLVE (0,000070 seconds) 0031_0003_023.msk: SOLVED in 0,000213 seconds! 0032_0003_023.msk: FAILED TO SOLVE (0,000147 seconds) 0033_0003_023.msk: FAILED TO SOLVE (0,000200 seconds) 0034_0001_023.msk: SOLVED in 0,000093 seconds! 0035_0003_023.msk: SOLVED in 0,000163 seconds! 0036_0001_023.msk: SOLVED in 0,000211 seconds! 0037_0003_023.msk: SOLVED in 0,000079 seconds! 0038_0001_023.msk: SOLVED in 0,000149 seconds! 0039_0003_023.msk: FAILED TO SOLVE (0,000083 seconds) 0040_0003_023.msk: SOLVED in 0,000161 seconds! 0041_0000_023.msk: SOLVED in 0,000074 seconds! 0042_0003_023.msk: SOLVED in 0,000239 seconds! 0043_0000_023.msk: SOLVED in 0,000074 seconds! 0044_0001_023.msk: SOLVED in 0,000137 seconds! 0045_0000_023.msk: SOLVED in 0,000072 seconds! 0046_0003_023.msk: SOLVED in 0,000191 seconds! 0047_0003_023.msk: FAILED TO SOLVE (0,000149 seconds) 0048_0001_023.msk: SOLVED in 0,000166 seconds! 0049_0001_023.msk: FAILED TO SOLVE (0,000174 seconds) 0050_0003_023.msk: SOLVED in 0,000156 seconds! 0051_0001_023.msk: SOLVED in 0,000078 seconds! 0052_0003_023.msk: SOLVED in 0,000201 seconds! 0053_0001_023.msk: SOLVED in 0,000123 seconds! 0054_0003_023.msk: SOLVED in 0,000160 seconds! 0055_0000_023.msk: SOLVED in 0,000074 seconds! 0056_0003_023.msk: SOLVED in 0,000174 seconds! 0057_0003_023.msk: SOLVED in 0,000126 seconds! 0058_0000_023.msk: SOLVED in 0,000073 seconds! 0059_0001_023.msk: SOLVED in 0,000084 seconds! 0060_0001_023.msk: SOLVED in 0,000116 seconds! 0061_0000_023.msk: SOLVED in 0,000076 seconds! 0062_0003_023.msk: SOLVED in 0,000128 seconds! 0063_0003_023.msk: SOLVED in 0,000218 seconds! 0064_0001_023.msk: SOLVED in 0,000136 seconds! 0065_0001_023.msk: SOLVED in 0,000188 seconds! 0066_0000_023.msk: SOLVED in 0,000073 seconds! 0067_0000_023.msk: SOLVED in 0,000071 seconds! 0068_0003_023.msk: FAILED TO SOLVE (0,000148 seconds)

Speedwise I'm all good... that shouldn't be a surprise :D If I wanted this code to perform better, I'd need to code a lot more pure logic.

Edit Commented out a part in the code that caused an invalid answer to be made...

Re: [VB] Sudoku Solver

My code solves ANY puzzle you give it, if it's solvable, it WILL solve it for sure. The problem is with speed... and aparently, I have to think of a way to make it faster... My code right now it's only 158 lines (only the solver part), but it does many iterations...one of the puzzles went up to ~ 2,000,000 iterations, took about 2 minutes, but it DID solve it...

It's weird, sometimes it solves difficult ones fast, and sometimes it solves easy ones in a long time (depending on the numbers, and their locations). So my code does not take more if it's more difficult, it takes more time depending on what numbers has to find, and how many options are in one square...

Merri, did you code it in VB6 ? Cuz those speeds are questionable... I just can't believe that for all of them it solved in less than a millisecond. If I were to do it in C++, maybe I would get close to those speeds...

Re: [VB] Sudoku Solver

It is pure VB6, compiled with advanced optimizations turned on. VB6 can be fast if you code close to the way C/C++ is coded. My code does very few iterations, mainly because it is pretty dumb (it does only a few basic things).

I started to code the thing speed optimized, but after a few tries it seems I have to code a completely different kind of code if I want to keep the code short. I think I don't have the time to code a wise and fast human logic code (especially because all of those logics don't help to solve every single sudoku; I've done a bit of reading all over the web).

Edit And in case wondering: all of those sudokus are valid, I have coded a validator that checks the answer is correct. Of course I didn't include validation code in the benchmark. Benchmark has only the main solver included. I'm not sure if I should include all the initialization code (which I have in file loading atm) in there. There are all kinds of optimization arrays that I use to speed up the process.

Re: [VB] Sudoku Solver

WAW, I never thought that optimizing it, and compiling it would make such a differemce...

I cheked all the optimizations, and compiled it (No change to the algorithm), these are my new results
Edit, I added the test with a P4 2.4MHz (P4 1.4 MHz was before)

Code:

0000_0001_022.msk SOLVED in 0.287948 seconds ! 0001_0001_022.msk SOLVED in 0.438416 seconds ! 0002_0003_022.msk SOLVED in 0.362996 seconds ! 0003_0003_022.msk SOLVED in 3.645449 seconds ! 0004_0001_022.msk SOLVED in 0.270467 seconds ! 0005_0003_022.msk SOLVED in 0.457557 seconds ! 0006_0003_023.msk SOLVED in 0.002827 seconds ! 0007_0001_023.msk SOLVED in 0.172526 seconds ! 0008_0003_023.msk SOLVED in 0.149416 seconds ! 0009_0001_023.msk SOLVED in 2.484164 seconds ! 0010_0003_023.msk SOLVED in 2.363259 seconds ! 0011_0001_023.msk SOLVED in 0.598318 seconds ! 0012_0001_023.msk SOLVED in 0.741144 seconds ! 0013_0003_023.msk SOLVED in 0.732081 seconds ! 0014_0001_023.msk SOLVED in 0.120726 seconds ! 0015_0003_023.msk SOLVED in 0.371666 seconds ! 0016_0003_023.msk SOLVED in 0.028882 seconds ! 0017_0003_023.msk SOLVED in 0.446015 seconds ! 0018_0001_023.msk SOLVED in 1.069428 seconds ! 0019_0001_023.msk SOLVED in 0.386867 seconds ! 0020_0001_023.msk SOLVED in 0.014436 seconds ! 0021_0000_023.msk SOLVED in 0.012320 seconds ! 0022_0003_023.msk SOLVED in 0.015810 seconds ! 0023_0003_023.msk SOLVED in 1.203462 seconds ! 0024_0001_023.msk SOLVED in 1.271842 seconds ! 0025_0003_023.msk SOLVED in 0.664934 seconds ! 0026_0001_023.msk SOLVED in 0.050855 seconds ! 0027_0001_023.msk SOLVED in 0.107242 seconds ! 0028_0000_023.msk SOLVED in 0.014142 seconds ! 0029_0003_023.msk SOLVED in 0.328170 seconds ! 0030_0003_023.msk SOLVED in 3.381428 seconds ! 0031_0003_023.msk SOLVED in 3.294486 seconds ! 0032_0003_023.msk SOLVED in 0.947270 seconds ! 0033_0003_023.msk SOLVED in 1.301865 seconds ! 0034_0001_023.msk SOLVED in 0.233115 seconds ! 0035_0003_023.msk SOLVED in 0.048189 seconds ! 0036_0001_023.msk SOLVED in 0.086981 seconds ! 0037_0003_023.msk SOLVED in 0.050578 seconds ! 0038_0001_023.msk SOLVED in 0.030469 seconds ! 0039_0003_023.msk SOLVED in 1.207334 seconds ! 0040_0003_023.msk SOLVED in 0.324173 seconds ! 0041_0000_023.msk SOLVED in 0.859896 seconds ! 0042_0003_023.msk SOLVED in 2.281628 seconds ! 0043_0000_023.msk SOLVED in 0.040724 seconds ! 0044_0001_023.msk SOLVED in 0.150261 seconds ! 0045_0000_023.msk SOLVED in 0.502185 seconds ! 0046_0003_023.msk SOLVED in 1.655138 seconds ! 0047_0003_023.msk SOLVED in 0.263479 seconds ! 0048_0001_023.msk SOLVED in 0.109991 seconds ! 0049_0001_023.msk SOLVED in 0.184529 seconds ! 0050_0003_023.msk SOLVED in 1.573665 seconds ! 0051_0001_023.msk SOLVED in 5.071790 seconds ! 0052_0003_023.msk SOLVED in 0.091918 seconds ! 0053_0001_023.msk SOLVED in 0.008073 seconds ! 0054_0003_023.msk SOLVED in 2.391423 seconds ! 0055_0000_023.msk SOLVED in 0.427153 seconds ! 0056_0003_023.msk SOLVED in 24.573525 seconds ! 0057_0003_023.msk SOLVED in 0.119403 seconds ! 0058_0000_023.msk SOLVED in 0.164148 seconds ! 0059_0001_023.msk SOLVED in 0.015558 seconds ! 0060_0001_023.msk SOLVED in 0.039397 seconds ! 0061_0000_023.msk SOLVED in 14.920490 seconds ! 0062_0003_023.msk SOLVED in 0.058760 seconds ! 0063_0003_023.msk SOLVED in 0.344639 seconds ! 0064_0001_023.msk SOLVED in 0.687604 seconds ! 0065_0001_023.msk SOLVED in 0.713891 seconds ! 0066_0000_023.msk SOLVED in 0.251985 seconds ! 0067_0000_023.msk SOLVED in 8.290482 seconds ! 0068_0003_023.msk SOLVED in 2.650295 seconds !

My previous test the highest was 218 seconds, now the same one is 25 seconds, quite a difference !

Edit
My timing is included with the validation becuase it cannot solve without it... the way it works, it tries a number, and validates at the end, if it's not valid, then goes back and tries another number, and so on, that's why it takes so long to do it...

Re: [VB] Sudoku Solver

Merri, can you post a few of the sudoku puzzles that your app was able to solve and a few that it failed on? Post them in the ...4... format please, because I'm just that lazy. :)

Re: [VB] Sudoku Solver

OK, I must have missed a post or something, because you both seem to be working with MSK files.

So what am I missing?

Re: [VB] Sudoku Solver

There is an attachment in the page three. There are also solutions for all of them in page four. Don't know why NotLKH named them as *.msk and *.sol

Re: [VB] Sudoku Solver

I'm too busy to do this :(

Re: [VB] Sudoku Solver

I got it to work a little faster, but it still does not even compare with Merri's speeds....

These are my new speeds:

Code:

0000_0001_022.msk SOLVED in 0.254477 seconds ! 0001_0001_022.msk SOLVED in 0.373606 seconds ! 0002_0003_022.msk SOLVED in 0.313741 seconds ! 0003_0003_022.msk SOLVED in 3.050348 seconds ! 0004_0001_022.msk SOLVED in 0.225612 seconds ! 0005_0003_022.msk SOLVED in 0.426900 seconds ! 0006_0003_023.msk SOLVED in 0.002394 seconds ! 0007_0001_023.msk SOLVED in 0.120851 seconds ! 0008_0003_023.msk SOLVED in 0.114130 seconds ! 0009_0001_023.msk SOLVED in 1.610821 seconds ! 0010_0003_023.msk SOLVED in 1.462444 seconds ! 0011_0001_023.msk SOLVED in 0.374089 seconds ! 0012_0001_023.msk SOLVED in 0.604493 seconds ! 0013_0003_023.msk SOLVED in 0.631803 seconds ! 0014_0001_023.msk SOLVED in 0.106865 seconds ! 0015_0003_023.msk SOLVED in 0.327831 seconds ! 0016_0003_023.msk SOLVED in 0.026677 seconds ! 0017_0003_023.msk SOLVED in 0.418917 seconds ! 0018_0001_023.msk SOLVED in 0.916444 seconds ! 0019_0001_023.msk SOLVED in 0.250842 seconds ! 0020_0001_023.msk SOLVED in 0.012339 seconds ! 0021_0000_023.msk SOLVED in 0.011315 seconds ! 0022_0003_023.msk SOLVED in 0.013690 seconds ! 0023_0003_023.msk SOLVED in 0.825243 seconds ! 0024_0001_023.msk SOLVED in 1.065825 seconds ! 0025_0003_023.msk SOLVED in 0.569411 seconds ! 0026_0001_023.msk SOLVED in 0.058811 seconds ! 0027_0001_023.msk SOLVED in 0.092646 seconds ! 0028_0000_023.msk SOLVED in 0.012015 seconds ! 0029_0003_023.msk SOLVED in 0.281798 seconds ! 0030_0003_023.msk SOLVED in 2.786000 seconds ! 0031_0003_023.msk SOLVED in 2.807790 seconds ! 0032_0003_023.msk SOLVED in 0.811070 seconds ! 0033_0003_023.msk SOLVED in 1.140219 seconds ! 0034_0001_023.msk SOLVED in 0.199686 seconds ! 0035_0003_023.msk SOLVED in 0.042819 seconds ! 0036_0001_023.msk SOLVED in 0.069305 seconds ! 0037_0003_023.msk SOLVED in 0.047670 seconds ! 0038_0001_023.msk SOLVED in 0.025088 seconds ! 0039_0003_023.msk SOLVED in 1.056909 seconds ! 0040_0003_023.msk SOLVED in 0.281891 seconds ! 0041_0000_023.msk SOLVED in 0.763498 seconds ! 0042_0003_023.msk SOLVED in 1.979333 seconds ! 0043_0000_023.msk SOLVED in 0.031541 seconds ! 0044_0001_023.msk SOLVED in 0.129039 seconds ! 0045_0000_023.msk SOLVED in 0.443941 seconds ! 0046_0003_023.msk SOLVED in 1.393400 seconds ! 0047_0003_023.msk SOLVED in 0.224529 seconds ! 0048_0001_023.msk SOLVED in 0.097558 seconds ! 0049_0001_023.msk SOLVED in 0.159716 seconds ! 0050_0003_023.msk SOLVED in 1.340751 seconds ! 0051_0001_023.msk SOLVED in 4.469149 seconds ! 0052_0003_023.msk SOLVED in 0.092811 seconds ! 0053_0001_023.msk SOLVED in 0.006616 seconds ! 0054_0003_023.msk SOLVED in 1.947379 seconds ! 0055_0000_023.msk SOLVED in 0.356866 seconds ! 0056_0003_023.msk SOLVED in 20.991355 seconds ! 0057_0003_023.msk SOLVED in 0.100669 seconds ! 0058_0000_023.msk SOLVED in 0.144101 seconds ! 0059_0001_023.msk SOLVED in 0.013654 seconds ! 0060_0001_023.msk SOLVED in 0.031400 seconds ! 0061_0000_023.msk SOLVED in 12.777963 seconds ! 0062_0003_023.msk SOLVED in 0.049240 seconds ! 0063_0003_023.msk SOLVED in 0.303904 seconds ! 0064_0001_023.msk SOLVED in 0.586654 seconds ! 0065_0001_023.msk SOLVED in 0.612514 seconds ! 0066_0000_023.msk SOLVED in 0.206935 seconds ! 0067_0000_023.msk SOLVED in 5.355710 seconds ! 0068_0003_023.msk SOLVED in 1.687794 seconds !

I think for more speed I'll need to use a different aproach... I just hope with new aproach, I will be able to solve all of them :), hopefully I won't run into the same problem you guys do (failing to solve)

By the way, who else except Merri is doing this ? I feel kinda alone here :D

mendhak, and NotLKH, are you guys participating in the contest ?

Re: [VB] Sudoku Solver

Naaa,...

I can't be the puzzle poster, and then compete!
My times are 20 MS and less with all of em!

Really!

There is little difference in generation and solving, so my solver is 90% the same as my generator.
So, natch, how could it be fair for me to enter???

:wave: :wave:
-Lou

Re: [VB] Sudoku Solver

Will you post your generator ?
If you think i'll use it for my sudoku solver (I won't), will you post it when the contest is done ?
I am really curious to se how you generate the puzzles...
I want to make a generator, but I don't even know how to start...

Re: [VB] Sudoku Solver

Quote:

Originally Posted by CVMichael

Will you post your generator ?
If you think i'll use it for my sudoku solver (I won't), will you post it when the contest is done ?
I am really curious to se how you generate the puzzles...
I want to make a generator, but I don't even know how to start...

Hi,

Try this.

Make a random number generator. Work through the grid reducing the random choice as appropriate for each miniblock,row and column, in that order. i.e. complete each miniblock of 9 working from left to right.

Repeat the above until the slots are completed but keep a check on progress and if you cannot fill all 81 slots, you will often find that you can complete 79 and if you check the rows and colums of the missing slot you can find the correct missing numbers.

notlkh has explained his approach in the thread on this subject in the vb.net forum.

Re: [VB] Sudoku Solver

Thanks, I found the thread, and I'm gonna look to see if I can find something to help me make it faster.

I'm almost there ! these are my new speeds:

Code:

0000_0001_022.msk 2 SOLVED in 0.041832 seconds !, in 8,323 iterations. 0001_0001_022.msk 2 SOLVED in 0.217594 seconds !, in 44,498 iterations. 0002_0003_022.msk 2 SOLVED in 0.307713 seconds !, in 53,545 iterations. 0003_0003_022.msk 2 SOLVED in 1.741179 seconds !, in 354,271 iterations. 0004_0001_022.msk 2 SOLVED in 0.443270 seconds !, in 83,103 iterations. 0005_0003_022.msk 2 SOLVED in 0.202927 seconds !, in 38,219 iterations. 0006_0003_023.msk 2 SOLVED in 0.003029 seconds !, in 636 iterations. 0007_0001_023.msk 2 SOLVED in 0.003435 seconds !, in 588 iterations. 0008_0003_023.msk 2 SOLVED in 0.177523 seconds !, in 34,545 iterations. 0009_0001_023.msk 2 SOLVED in 0.244403 seconds !, in 38,865 iterations. 0010_0003_023.msk 2 SOLVED in 1.115781 seconds !, in 218,029 iterations. 0011_0001_023.msk 2 SOLVED in 0.572198 seconds !, in 124,087 iterations. 0012_0001_023.msk 2 SOLVED in 0.110519 seconds !, in 20,259 iterations. 0013_0003_023.msk 2 SOLVED in 0.483003 seconds !, in 93,940 iterations. 0014_0001_023.msk 2 SOLVED in 0.017221 seconds !, in 4,012 iterations. 0015_0003_023.msk 2 SOLVED in 0.045131 seconds !, in 9,470 iterations. 0016_0003_023.msk 2 SOLVED in 0.050617 seconds !, in 9,753 iterations. 0017_0003_023.msk 2 SOLVED in 0.185674 seconds !, in 27,234 iterations. 0018_0001_023.msk 2 SOLVED in 0.017349 seconds !, in 3,634 iterations. 0019_0001_023.msk 2 SOLVED in 0.034389 seconds !, in 7,030 iterations. 0020_0001_023.msk 2 SOLVED in 0.021386 seconds !, in 4,258 iterations. 0021_0000_023.msk 1 SOLVED in 0.001595 seconds !, in 10 iterations. 0022_0003_023.msk 2 SOLVED in 0.025443 seconds !, in 4,986 iterations. 0023_0003_023.msk 2 SOLVED in 1.604814 seconds !, in 309,201 iterations. 0024_0001_023.msk 2 SOLVED in 0.920696 seconds !, in 174,973 iterations. 0025_0003_023.msk 2 SOLVED in 0.631125 seconds !, in 119,705 iterations. 0026_0001_023.msk 2 SOLVED in 0.001015 seconds !, in 56 iterations. 0027_0001_023.msk 2 SOLVED in 0.066356 seconds !, in 12,599 iterations. 0028_0000_023.msk 1 SOLVED in 0.000569 seconds !, in 13 iterations. 0029_0003_023.msk 2 SOLVED in 0.515487 seconds !, in 101,163 iterations. 0030_0003_023.msk 2 SOLVED in 1.165299 seconds !, in 246,651 iterations. 0031_0003_023.msk 2 SOLVED in 4.632048 seconds !, in 985,805 iterations. 0032_0003_023.msk 2 SOLVED in 0.488466 seconds !, in 98,676 iterations. 0033_0003_023.msk 2 SOLVED in 2.171629 seconds !, in 440,701 iterations. 0034_0001_023.msk 2 SOLVED in 0.365028 seconds !, in 73,366 iterations. 0035_0003_023.msk 2 SOLVED in 0.085730 seconds !, in 16,193 iterations. 0036_0001_023.msk 2 SOLVED in 0.134306 seconds !, in 28,693 iterations. 0037_0003_023.msk 2 SOLVED in 0.024477 seconds !, in 4,380 iterations. 0038_0001_023.msk 2 SOLVED in 0.011920 seconds !, in 2,457 iterations. 0039_0003_023.msk 2 SOLVED in 0.606416 seconds !, in 116,755 iterations. 0040_0003_023.msk 2 SOLVED in 0.065404 seconds !, in 12,240 iterations. 0041_0000_023.msk 1 SOLVED in 0.000511 seconds !, in 11 iterations. 0042_0003_023.msk 2 SOLVED in 3.895522 seconds !, in 743,586 iterations. 0043_0000_023.msk 1 SOLVED in 0.000512 seconds !, in 11 iterations. 0044_0001_023.msk 2 SOLVED in 0.030201 seconds !, in 6,298 iterations. 0045_0000_023.msk 1 SOLVED in 0.000512 seconds !, in 11 iterations. 0046_0003_023.msk 2 SOLVED in 0.346637 seconds !, in 68,997 iterations. 0047_0003_023.msk 2 SOLVED in 0.133716 seconds !, in 29,402 iterations. 0048_0001_023.msk 2 SOLVED in 0.067248 seconds !, in 14,759 iterations. 0049_0001_023.msk 2 SOLVED in 0.011002 seconds !, in 2,161 iterations. 0050_0003_023.msk 2 SOLVED in 2.663629 seconds !, in 526,526 iterations. 0051_0001_023.msk 2 SOLVED in 0.234381 seconds !, in 48,967 iterations. 0052_0003_023.msk 2 SOLVED in 0.043285 seconds !, in 8,763 iterations. 0053_0001_023.msk 2 SOLVED in 0.001717 seconds !, in 230 iterations. 0054_0003_023.msk 2 SOLVED in 3.702536 seconds !, in 789,825 iterations. 0055_0000_023.msk 1 SOLVED in 0.000618 seconds !, in 13 iterations. 0056_0003_023.msk 2 SOLVED in 6.160506 seconds !, in 1,257,748 iterations. 0057_0003_023.msk 2 SOLVED in 0.021095 seconds !, in 3,723 iterations. 0058_0000_023.msk 1 SOLVED in 0.000559 seconds !, in 12 iterations. 0059_0001_023.msk 2 SOLVED in 0.013650 seconds !, in 2,548 iterations. 0060_0001_023.msk 2 SOLVED in 0.027646 seconds !, in 6,304 iterations. 0061_0000_023.msk 1 SOLVED in 0.000674 seconds !, in 15 iterations. 0062_0003_023.msk 2 SOLVED in 0.029491 seconds !, in 5,828 iterations. 0063_0003_023.msk 2 SOLVED in 0.418120 seconds !, in 81,143 iterations. 0064_0001_023.msk 2 SOLVED in 0.017616 seconds !, in 3,611 iterations. 0065_0001_023.msk 2 SOLVED in 0.523140 seconds !, in 102,981 iterations. 0066_0000_023.msk 1 SOLVED in 0.000619 seconds !, in 14 iterations. 0067_0000_023.msk 1 SOLVED in 0.000678 seconds !, in 15 iterations. 0068_0003_023.msk 2 SOLVED in 3.332755 seconds !, in 624,753 iterations.

I added 2 more pieces of information... first is the 2 and 1, where 2 means I did some "guessing" (it's not really guessing, more like testing... anyways), and 1 means it did not do any guessing AT ALL....
Also, the last "field" is how many iterations/(big loops) it had to do to solve it.

Finally I have results that are less than 1 Millisecond !!! :), only a few, but ow well, i'll keep trying...

Re: [VB] Sudoku Solver

Have to say at this point: I love it when VB6 has a stack limit. Read: I got my new shiny super solver working...

... but it ran out of stack space before it could complete most of the sudokus. Now trying to figure out an alternative way to do it.

Edit Woohoo! Got it running fine! :D Doing initial timing...

Re: [VB] Sudoku Solver

Here it is: the results of my new algorithm that works by doing a lot of very good guesses.

Code:

0000_0001_022.msk: SOLVED in 0,001556 seconds! 0001_0001_022.msk: SOLVED in 0,000883 seconds! 0002_0003_022.msk: SOLVED in 0,002042 seconds! 0003_0003_022.msk: SOLVED in 0,078447 seconds! 0004_0001_022.msk: SOLVED in 0,032395 seconds! 0005_0003_022.msk: SOLVED in 0,027291 seconds! 0006_0003_023.msk: SOLVED in 0,001168 seconds! 0007_0001_023.msk: SOLVED in 0,000541 seconds! 0008_0003_023.msk: SOLVED in 0,000918 seconds! 0009_0001_023.msk: SOLVED in 0,000556 seconds! 0010_0003_023.msk: SOLVED in 0,000600 seconds! 0011_0001_023.msk: SOLVED in 0,001324 seconds! 0012_0001_023.msk: SOLVED in 0,014289 seconds! 0013_0003_023.msk: SOLVED in 0,001344 seconds! 0014_0001_023.msk: SOLVED in 0,002667 seconds! 0015_0003_023.msk: SOLVED in 0,001286 seconds! 0016_0003_023.msk: SOLVED in 0,010309 seconds! 0017_0003_023.msk: SOLVED in 0,003610 seconds! 0018_0001_023.msk: SOLVED in 0,001452 seconds! 0019_0001_023.msk: SOLVED in 0,002513 seconds! 0020_0001_023.msk: SOLVED in 0,001145 seconds! 0021_0000_023.msk: SOLVED in 0,000576 seconds! 0022_0003_023.msk: SOLVED in 0,001293 seconds! 0023_0003_023.msk: SOLVED in 0,032776 seconds! 0024_0001_023.msk: SOLVED in 0,005714 seconds! 0025_0003_023.msk: SOLVED in 0,000620 seconds! 0026_0001_023.msk: SOLVED in 0,001178 seconds! 0027_0001_023.msk: SOLVED in 0,002901 seconds! 0028_0000_023.msk: SOLVED in 0,000633 seconds! 0029_0003_023.msk: SOLVED in 0,018073 seconds! 0030_0003_023.msk: SOLVED in 0,058659 seconds! 0031_0003_023.msk: SOLVED in 0,004735 seconds! 0032_0003_023.msk: SOLVED in 0,001000 seconds! 0033_0003_023.msk: SOLVED in 0,003901 seconds! 0034_0001_023.msk: SOLVED in 0,014809 seconds! 0035_0003_023.msk: SOLVED in 0,001335 seconds! 0036_0001_023.msk: SOLVED in 0,002285 seconds! 0037_0003_023.msk: SOLVED in 0,001407 seconds! 0038_0001_023.msk: SOLVED in 0,002716 seconds! 0039_0003_023.msk: SOLVED in 0,001160 seconds! 0040_0003_023.msk: SOLVED in 0,012611 seconds! 0041_0000_023.msk: SOLVED in 0,000696 seconds! 0042_0003_023.msk: SOLVED in 0,011734 seconds! 0043_0000_023.msk: SOLVED in 0,000498 seconds! 0044_0001_023.msk: SOLVED in 0,001740 seconds! 0045_0000_023.msk: SOLVED in 0,001010 seconds! 0046_0003_023.msk: SOLVED in 0,000726 seconds! 0047_0003_023.msk: SOLVED in 0,005725 seconds! 0048_0001_023.msk: SOLVED in 0,000632 seconds! 0049_0001_023.msk: SOLVED in 0,001302 seconds! 0050_0003_023.msk: SOLVED in 0,001774 seconds! 0051_0001_023.msk: SOLVED in 0,007148 seconds! 0052_0003_023.msk: SOLVED in 0,001905 seconds! 0053_0001_023.msk: SOLVED in 0,000834 seconds! 0054_0003_023.msk: SOLVED in 0,009946 seconds! 0055_0000_023.msk: SOLVED in 0,001478 seconds! 0056_0003_023.msk: SOLVED in 0,000877 seconds! 0057_0003_023.msk: SOLVED in 0,000705 seconds! 0058_0000_023.msk: SOLVED in 0,001126 seconds! 0059_0001_023.msk: SOLVED in 0,001607 seconds! 0060_0001_023.msk: SOLVED in 0,000720 seconds! 0061_0000_023.msk: SOLVED in 0,007399 seconds! 0062_0003_023.msk: SOLVED in 0,000811 seconds! 0063_0003_023.msk: SOLVED in 0,000990 seconds! 0064_0001_023.msk: SOLVED in 0,000918 seconds! 0065_0001_023.msk: SOLVED in 0,005556 seconds! 0066_0000_023.msk: SOLVED in 0,000587 seconds! 0067_0000_023.msk: SOLVED in 0,000949 seconds! 0068_0003_023.msk: SOLVED in 0,004548 seconds! Total time: 0,428659 seconds

Hoping to optimize further... had a bit rough moments while coding it (as can be seen from my previous post). Luckily I accidentaly fixed the error I had and it is now all good :) Shouldn't code throughout night...

Update Total time now pushed from 0,67 seconds to 0,43 seconds.

Re: [VB] Sudoku Solver

Quote:

Originally Posted by taxes

notlkh has explained his approach in the thread on this subject in the vb.net forum.

My method works along the lines of:

Build a Base pattern, the "solution"

For each row of 3x3 Squares, determine a randome viable row assignment for the numbers 1 thru 9. The result is, for each row {0 thru 2} of each 3x3 square, will contain 3 numbers. Therefore, once you've done every SQUARE ROW, each and every cell will be a possibles list of 3 numbers.
Now, with all the numbers having been assigned their Row assignment, determine their column assignment for each Column of 3 x 3 Squares. My technique here is, For an individual SQUARE COLUMN

Select a cell.
Randomly select one of its possible values from its Possible's list
Remove all the possibles except the selected possible from that cells possibles list, leaving only 1 value left in that cells possibles list
Enter an iteration where;

for every possible list that has a single value listed, remove that value from every other possible list in that Possibles parent SQUARE;
for every possible list that has a single value listed, remove that value from every other possible list common to its column, across every SQUARE in this SQUARE COLUMN.
And other assorted elimination strategies...
Once all the numbers have been eliminated that could be eliminated, for every list that contains only 1 possible value, place that value into the solution matrix, and clear its list.
If All the lists in this SQUARE COLUMN Are NOT yet empty, Seed a new cell via method Step 1.b.1, until the SQ_COL is completely solved, or has become impossible to solve, ie... a List is empty, but the output solution matrix cell for that spot has not been assigned.
Mask the Base Pattern. This is pretty simple.... Care too guess how its done???

Now, Step 1.b.1 is critical to the efficiency rating of my method. Exactly how you select which cell you'll seed with a single value will give you anywheres from a 60 percent success rate to a 97 percent rating. I'll give you some things to select, but I won't tell you in what order they're favored by. {I don't use them all, but I've tested them}

Inspecting each Cells Possible list, from left to right, Top to Bottom, of each 3x3 SQUARE in the SQUARE COLUMN of 3 SQUARES, traveling from the TOP SQUARE to the BOTTOM SQUARE, select one of the following cells:

First Cell with a possibles list containing 3 values
First Cell with a possibles list containing 2 values
First Cell with a possibles list containing 1 value: Should never happen.
First Cell with a possibles list containing 2 values, in a row where the other two Cells have a possibles list containing 3 values.
First Cell with a possibles list containing 2 values, in a row where the other two Cells have a possibles list containing 2 values.
First Cell with a possibles list containing 3 values, in a row where the other two Cells have a possibles list containing 2 values.
First Cell with a possibles list containing 3 values, in a row where the other two Cells have a possibles list containing 3 values.
:wave:
-Lou

Re: [VB] Sudoku Solver

Merri, I'm getting close....

Code:

0000_0001_022.msk SOLVED in 0.008207 seconds ! 0001_0001_022.msk SOLVED in 0.001797 seconds ! 0002_0003_022.msk SOLVED in 0.000579 seconds ! 0003_0003_022.msk SOLVED in 0.000631 seconds ! 0004_0001_022.msk SOLVED in 0.016747 seconds ! 0005_0003_022.msk SOLVED in 0.000539 seconds ! 0006_0003_023.msk SOLVED in 0.000504 seconds ! 0007_0001_023.msk SOLVED in 0.072772 seconds ! 0008_0003_023.msk SOLVED in 0.000627 seconds ! 0009_0001_023.msk SOLVED in 0.001713 seconds ! 0010_0003_023.msk SOLVED in 0.000534 seconds ! 0011_0001_023.msk SOLVED in 0.000588 seconds ! 0012_0001_023.msk SOLVED in 0.000525 seconds ! 0013_0003_023.msk SOLVED in 0.000521 seconds ! 0014_0001_023.msk SOLVED in 0.001827 seconds ! 0015_0003_023.msk SOLVED in 0.000594 seconds ! 0016_0003_023.msk SOLVED in 0.029741 seconds ! 0017_0003_023.msk SOLVED in 0.056030 seconds ! 0018_0001_023.msk SOLVED in 0.000491 seconds ! 0019_0001_023.msk SOLVED in 0.000591 seconds ! 0020_0001_023.msk SOLVED in 0.001880 seconds ! 0021_0000_023.msk SOLVED in 0.000550 seconds ! 0022_0003_023.msk SOLVED in 0.006138 seconds ! 0023_0003_023.msk SOLVED in 0.000606 seconds ! 0024_0001_023.msk SOLVED in 0.000534 seconds ! 0025_0003_023.msk SOLVED in 0.016297 seconds ! 0026_0001_023.msk SOLVED in 0.000624 seconds ! 0027_0001_023.msk SOLVED in 0.001878 seconds ! 0028_0000_023.msk SOLVED in 0.000548 seconds ! 0029_0003_023.msk SOLVED in 0.000623 seconds ! 0030_0003_023.msk SOLVED in 0.000815 seconds ! 0031_0003_023.msk SOLVED in 0.001777 seconds ! 0032_0003_023.msk SOLVED in 0.000629 seconds ! 0033_0003_023.msk SOLVED in 0.001897 seconds ! 0034_0001_023.msk SOLVED in 0.000472 seconds ! 0035_0003_023.msk SOLVED in 0.011410 seconds ! 0036_0001_023.msk SOLVED in 0.000612 seconds ! 0037_0003_023.msk SOLVED in 0.012749 seconds ! 0038_0001_023.msk SOLVED in 0.023135 seconds ! 0039_0003_023.msk SOLVED in 0.493007 seconds ! 0040_0003_023.msk SOLVED in 0.000488 seconds ! 0041_0000_023.msk SOLVED in 0.000699 seconds ! 0042_0003_023.msk SOLVED in 0.000634 seconds ! 0043_0000_023.msk SOLVED in 0.000505 seconds ! 0044_0001_023.msk SOLVED in 0.076257 seconds ! 0045_0000_023.msk SOLVED in 0.000411 seconds ! 0046_0003_023.msk SOLVED in 0.000587 seconds ! 0047_0003_023.msk SOLVED in 0.000552 seconds ! 0048_0001_023.msk SOLVED in 0.000530 seconds ! 0049_0001_023.msk SOLVED in 0.005856 seconds ! 0050_0003_023.msk SOLVED in 0.000540 seconds ! 0051_0001_023.msk SOLVED in 0.000593 seconds ! 0052_0003_023.msk SOLVED in 0.000648 seconds ! 0053_0001_023.msk SOLVED in 0.000623 seconds ! 0054_0003_023.msk SOLVED in 0.000577 seconds ! 0055_0000_023.msk SOLVED in 0.000639 seconds ! 0056_0003_023.msk SOLVED in 0.000575 seconds ! 0057_0003_023.msk SOLVED in 0.000508 seconds ! 0058_0000_023.msk SOLVED in 0.018383 seconds ! 0059_0001_023.msk SOLVED in 0.000566 seconds ! 0060_0001_023.msk SOLVED in 0.000529 seconds ! 0061_0000_023.msk SOLVED in 0.000502 seconds ! 0062_0003_023.msk SOLVED in 0.000512 seconds ! 0063_0003_023.msk SOLVED in 0.000542 seconds ! 0064_0001_023.msk SOLVED in 0.000540 seconds ! 0065_0001_023.msk SOLVED in 0.000585 seconds ! 0066_0000_023.msk SOLVED in 0.000567 seconds ! 0067_0000_023.msk SOLVED in 0.000418 seconds ! 0068_0003_023.msk SOLVED in 0.000623 seconds ! Files Processed: 69, Total time: 0.886725, Average Time: 0.012851

I just discovered 2 new rules, but I did not have time to implement both rules to my code, so the above speeds is with my previous rules + 1.

So... I STILL have room to make it faster :D

Today I spent the whole day re-writing my code for the new rule, and I am DEAD tired, tomorow I'll apply the last rule, and I'm done !

Re: [VB] Sudoku Solver

I'm terribly sorry CVMichael: I've now made mine a hybrid as well.

Code:

0000_0001_022.msk: SOLVED in 0,000040 seconds! 0001_0001_022.msk: SOLVED in 0,001698 seconds! 0002_0003_022.msk: SOLVED in 0,000033 seconds! 0003_0003_022.msk: SOLVED in 0,000593 seconds! 0004_0001_022.msk: SOLVED in 0,000788 seconds! 0005_0003_022.msk: SOLVED in 0,000485 seconds! 0006_0003_023.msk: SOLVED in 0,000056 seconds! 0007_0001_023.msk: SOLVED in 0,000029 seconds! 0008_0003_023.msk: SOLVED in 0,000536 seconds! 0009_0001_023.msk: SOLVED in 0,000027 seconds! 0010_0003_023.msk: SOLVED in 0,000030 seconds! 0011_0001_023.msk: SOLVED in 0,000070 seconds! 0012_0001_023.msk: SOLVED in 0,000049 seconds! 0013_0003_023.msk: SOLVED in 0,000097 seconds! 0014_0001_023.msk: SOLVED in 0,001112 seconds! 0015_0003_023.msk: SOLVED in 0,000032 seconds! 0016_0003_023.msk: SOLVED in 0,015465 seconds! 0017_0003_023.msk: SOLVED in 0,005215 seconds! 0018_0001_023.msk: SOLVED in 0,000042 seconds! 0019_0001_023.msk: SOLVED in 0,000035 seconds! 0020_0001_023.msk: SOLVED in 0,000406 seconds! 0021_0000_023.msk: SOLVED in 0,000022 seconds! 0022_0003_023.msk: SOLVED in 0,002905 seconds! 0023_0003_023.msk: SOLVED in 0,000442 seconds! 0024_0001_023.msk: SOLVED in 0,001157 seconds! 0025_0003_023.msk: SOLVED in 0,002247 seconds! 0026_0001_023.msk: SOLVED in 0,000024 seconds! 0027_0001_023.msk: SOLVED in 0,000047 seconds! 0028_0000_023.msk: SOLVED in 0,000036 seconds! 0029_0003_023.msk: SOLVED in 0,000718 seconds! 0030_0003_023.msk: SOLVED in 0,005340 seconds! 0031_0003_023.msk: SOLVED in 0,000056 seconds! 0032_0003_023.msk: SOLVED in 0,000039 seconds! 0033_0003_023.msk: SOLVED in 0,000094 seconds! 0034_0001_023.msk: SOLVED in 0,000026 seconds! 0035_0003_023.msk: SOLVED in 0,000050 seconds! 0036_0001_023.msk: SOLVED in 0,001028 seconds! 0037_0003_023.msk: SOLVED in 0,000024 seconds! 0038_0001_023.msk: SOLVED in 0,000072 seconds! 0039_0003_023.msk: SOLVED in 0,004370 seconds! 0040_0003_023.msk: SOLVED in 0,000045 seconds! 0041_0000_023.msk: SOLVED in 0,000022 seconds! 0042_0003_023.msk: SOLVED in 0,000082 seconds! 0043_0000_023.msk: SOLVED in 0,000022 seconds! 0044_0001_023.msk: SOLVED in 0,000048 seconds! 0045_0000_023.msk: SOLVED in 0,000022 seconds! 0046_0003_023.msk: SOLVED in 0,001506 seconds! 0047_0003_023.msk: SOLVED in 0,000074 seconds! 0048_0001_023.msk: SOLVED in 0,000057 seconds! 0049_0001_023.msk: SOLVED in 0,005988 seconds! 0050_0003_023.msk: SOLVED in 0,000058 seconds! 0051_0001_023.msk: SOLVED in 0,000023 seconds! 0052_0003_023.msk: SOLVED in 0,000285 seconds! 0053_0001_023.msk: SOLVED in 0,000039 seconds! 0054_0003_023.msk: SOLVED in 0,000050 seconds! 0055_0000_023.msk: SOLVED in 0,000022 seconds! 0056_0003_023.msk: SOLVED in 0,001449 seconds! 0057_0003_023.msk: SOLVED in 0,000039 seconds! 0058_0000_023.msk: SOLVED in 0,000022 seconds! 0059_0001_023.msk: SOLVED in 0,000025 seconds! 0060_0001_023.msk: SOLVED in 0,000035 seconds! 0061_0000_023.msk: SOLVED in 0,000022 seconds! 0062_0003_023.msk: SOLVED in 0,000039 seconds! 0063_0003_023.msk: SOLVED in 0,000076 seconds! 0064_0001_023.msk: SOLVED in 0,000595 seconds! 0065_0001_023.msk: SOLVED in 0,000072 seconds! 0066_0000_023.msk: SOLVED in 0,000022 seconds! 0067_0000_023.msk: SOLVED in 0,000022 seconds! 0068_0003_023.msk: SOLVED in 0,000076 seconds! Total time: 0,056372 seconds

I still have plenty of room to make it faster: each bit of human logic I add will drop down the time it takes to figure out the hardest ones.

Btw, I think we should multiply our timing results by 1000, so that we'd be comparing milliseconds instead of seconds: having that many zeroes makes it hard to compare. Anyways: my code is 15 times faster at the moment :) (of course depends a bit as we don't have identical machines: I have 1800 MHz Athlon XP-M 2200+).

Edit This one is the worst case I have found this far:

Code:

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

It takes 0,2 seconds alone (four times longer than doing all of NotLKH's samples!).

Re: [VB] Sudoku Solver

Quote:

Originally Posted by Merri

I'm terribly sorry CVMichael: I've now made mine a hybrid as well.

[
Edit This one is the worst case I have found this far:

Code:

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

It takes 0,2 seconds alone (four times longer than doing all of NotLKH's samples!).

I'm not surprised!! That is not a true Sudoku puzzle. It has absolutely no logical move. You can only do this by intelligent guesswork (iteration if you prefer :bigyello: ) and is totally impractical unless using a computor. (I am not saying that it is not derived from a legitimate Sudoku grid). Where did you get it from?

Don't forget that if your solver is based on NotLKH's system, you will automatically solve puzzles generated by him very quickly, but you will be much slower on puzzles generated by other methods.

Re: [VB] Sudoku Solver

I have no idea what method is used by NotLKH; I gather different kind of sudokus all over the web and test on all of them :) Btw, there is a logical move in every sudoku. If the puzzle is empty, you just add a number and keep adding up until you've solved it. That is a logical move, if the goal is to fill the sudoku with valid values.

Oh, and my improved algorithm can now handle it in 21 ms instead of 200 ms. However, there are new "worst cases". Neither of them is NotLKH's. The longest it takes is now at 140 ms. Still way to go down.

Re: [VB] Sudoku Solver

Quote:

if the goal is to fill the sudoku with valid values

Nope, the goal is to fill it with the correct values I'm afraid. It's not possible to have a blank one to start, it must have enough information to lead to the solution, which can be reached by logic alone.

Re: [VB] Sudoku Solver

Hmmm,
I was wondering,
Would anybody mind it if this weekend I get my generator to start building msk patterns with 1 - 4 holes?

What I have in mind would be, build a valid MSK pattern which, thru technique alone, leads to 1 valid pattern. Then from this MSK Pattern, For each combination of 1 thru 4 revealed cells, Mask them, then see if solving thru technique & iteration leads to a single solution, until I've found the right set of 1-4 cells that can be masked yet still reach a single final SOL.

ie.. Build MSK patterns similar to what Merri provided.

:wave:

Re: [VB] Sudoku Solver

Quote:

Originally Posted by Merri

I have no idea what method is used by NotLKH; I gather different kind of sudokus all over the web and test on all of them :) Btw, there is a logical move in every sudoku. If the puzzle is empty, you just add a number and keep adding up until you've solved it. That is a logical move, if the goal is to fill the sudoku with valid values.

A logical move is one which can be computed directly from the information given as being the ONLY number for that slot. Unfortunately, early computor technical terms included the word "Logic" to describe the internal manner in which a computor addresses a problem or calculation. "Logical" does not have such an interpretation and still has it's age old meaning, i.e. that you can precisely reason out each step. The puzzle you last submitted does not have even one such step. It does, however, have a unique solution.

Re: [VB] Sudoku Solver

Quote:

Originally Posted by taxes

A logical move is one which can be computed directly from the information given as being the ONLY number for that slot. Unfortunately, early computor technical terms included the word "Logic" to describe the internal manner in which a computor addresses a problem or calculation. "Logical" does not have such an interpretation and still has it's age old meaning, i.e. that you can precisely reason out each step. The puzzle you last submitted does not have even one such step. It does, however, have a unique solution.

Hmmm,
I'll take that as an objection?
:wave:
-Lou

Re: [VB] Sudoku Solver

Quote:

Originally Posted by Something Else

Hmmm,
I'll take that as an objection?
:wave:
-Lou

Objection to what????

I think that the contest should observe the normal Sudhoku rules in that test puzzles must have a unique solution reached by logical deduction. Within that limitation there are still many variations of approaching any one puzzle and the speed of a solution will depend on the ability of the programme to select the quickest. The advantage of the computer over a human is that it does not suffer from lack of concentration and numerical dislexia. The number of times I have had to choose from two numbers and reasoned out one but written the other is legion :sick:

Re: [VB] Sudoku Solver

Quote:

Originally Posted by taxes

Objection to what????

To What I suggested I was going to do in this post # 108:
http://www.vbforums.com/showpost.php...&postcount=108

It was going to be my final phase of development.

-Lou

Re: [VB] Sudoku Solver

Quote:

Originally Posted by Something Else

To What I suggested I was going to do in this post # 108:
http://www.vbforums.com/showpost.php...&postcount=108

It was going to be my final phase of development.

-Lou

OH. I thought that you were suggesting you were going to produce a Super Sudhoku with 9 miniblocks of 3 rows and 4 columns! This is done in some newspapers.

No, I was just hoping that puzzles requiring solely iteration would not be included. Anyway, PLEASE don't deviate from the 3 * 3 format as I have just struggled to get it down to 10 ms :ehh:

Re: [VB] Sudoku Solver

I can't get my solver faster :cry:

I wander if I should still compete... I definitelly cannot make it faster than Merri's solver, so what's the point ?

Re: [VB] Sudoku Solver

Of course you can make it faster :) Just keep trying ;)

Re: [VB] Sudoku Solver

Also bear in mind that you have different machines with different software running (some software slows benchmarks down noticably) - they will both be tested on the same machines.

Re: [VB] Sudoku Solver

Quote:

Originally Posted by CVMichael

I can't get my solver faster :cry:

I wander if I should still compete... I definitelly cannot make it faster than Merri's solver, so what's the point ?

Just keep going. I don't think that merri's speeds are genuinely the times taken - unless he is using a computor he acquired from the future running at 0 degrees kelvin to achieve superconductivity. I say that 'cos I reckon it takes 10 milliseconds just to update the visible grid and until you do that you have not solved the puzzle, 'cos that requires you to complete the grid. :wave:

Ok I know, merri is going to prove me wrong now :sick:

1 Attachment(s)

Re: [VB] Sudoku Solver

Er... updating grid is not included in the benchmark. Atleast it should not be. There is no point what-so-ever to include displaying of the results in the benchmark. I hated it when it was done in the Prime Numbers contest and I'll start shouting about it again if it will be included. Of course I can optimize the displaying of the results, but it then wouldn't have anything to do with benchmarking the speed of the sudoku algorithm.

I don't understand why people want to mess two very different things with each other... atleast this time the contest description clearly says: "The winner will be determined by the number of sudokus solved, then by the lowest time taken to complete them." - it is very possible to solve sudokus in the memory without displaying them. Humm... there it is! "Show the results (will not be timed, show as you like)". Though, I think loading the file shouldn't be included in timing. Maybe I'll optimize that as well... the contest description requires additions though.

I do store the results into a string array, but that isn't included in the benchmarking. This is what my benchmarking loop looks like:

Code:

strBench = "Benchmarking..." For A = 0 To lstFiles.ListCount - 1 If lstFiles.Selected(A) Then OpenSudoku lstFiles.List(A) Q.StartTime SolveSudoku Q.StopTime strBench = strBench & vbCrLf & Format$(Q.RetTime * 1000, "0.000000") & " ms:" & vbTab & FixFilename(lstFiles.List(A)) lngBench = lngBench + Q.RetTime strTemp = vbNullString D = 0 For C = 0 To 8 strTemp = strTemp & vbCrLf For B = 0 To 8 strTemp = strTemp & CStr(SudokuBoard(D + B)) Next B D = D + 9 Next C Solutions(A) = Mid$(strTemp, 3) lngCount = lngCount + 1 DoEvents End If Next A

It isn't even optimized, I'd normally use a byte array to create the string. Anyways... I have attached the executable and a few example sudokus so you can test it yourself.

CVMichael: remember, my solver doesn't solve everything fast. Perfect goal would be to solve every single sudoku under 10 ms. I've also been pretty lazy in coding the logic, so it might be my doom. Even though I can do the easy ones very fast, the harder ones are slow.

Re: [VB] Sudoku Solver

Showing the results won't be counted since we haven't set a standard way of showing the results. Showing the results is up to you how you do it, although it's preferable you have a sub that shows the results so we can check that the results are actually correct.

Re: [VB] Sudoku Solver

Hmmmmmmm!

I'm going to try that approach in my next examination. "Mr. invigilator. I have answered all the questions correctly within the time allowed, but it's all in my mind. I didn't have time to write out the answers. I'll do that if you give me more time."