Printable View
Shortest time so far = 873ms
Longest = 2040 ms
There is a big bug in my code though so it might mess all of this up when I fix it :(
Can you start generating a few puzzles for us so we can test our apps? maybe start a contest support thread with nothing but puzzles in it?
I don't know what other approaches are available but I'm trying to mimic the human brain's own throuh processes during the solving process. I think it can be done very quickly if the puzzle can be strongly represented inside the computer.
I predict the recursive and iterative approaches to be, by far, the slowest (by a few orders of magnitude).
Its interesting just how difficult this is, given the seemingly very simple puzzle rules.
Yes, but in a day or two.Quote:
Originally Posted by wossname
I'm under some cruch time, at the moment.
Gotta:
#1: finish developing the job generation process for a new customer product, and
#2: break my mom out of the hospital as soon as #1 is done.
So, I'm kinda tied up today.
So, tomorrow or friday.
:wave:
Ok. I sincerely hope the judges will be using .Net Framework 2005 (v2.0) for this because that's what I've got at home. If not then I'll have to write my entry at work :(
Humm... my algorithm solves a basic sudoku in ~0,004 seconds under the IDE and ~0,0001 seconds compiled. Of course this code isn't very wise. I hope I'm able to code some good rules for the harder puzzles.
To ease your mind: I've never solved a sudoku myself :)
Hi,
NotLKH, I managed that one in just over 10mins. So a bit harder than the other one :) .
I can recommend trying these puzzles by hand, for anybody who's interested. There are a couple of methods that you'll spot by doing them manually which if included in coding will speed things up no end.
I'd make my own solver, but with so many luminaries entering this contest I'm overawed.
zaza
I'll believe that when I see it :D
What would be a better approach: To start with a grid and work by elimination or the other way round? I'm using the elimination approach right now...
I'm using logical deduction. However this is proving hard to code, My initial approach is quite a loose system and if it works, I'll tighten it up and optimise it for speed later.
I can't see that any iterative approach can be faster. But then again, who am I to say?
Here are some patterns in the format requested by the contest.
The lines terminate with vbcrlf.
If a number is not masked, it is the number.
If it IS masked, then it is a decimal point.
They are a smattering of 22 and 23 exposed cells.
They are at the Various levels of "difficulty", ie... 0000, 0001, and 0003.
BTW, should I also attach the solutions?
:wave:
-Lou
Might be a good idea. If you have them that is. So people don't have to do them all by hand. But only if you have them that is..:)
PS: And you are able to make more for the contest right? So these don't have to be used for the contest?
- ØØ -
Ok, I'll attach the solutions here for those.
BTW, My generator has been making them with the numbers 0 thru 8, tab deliminated, and those that I attached were converted to the 1 thru 9, decimal for masked position format, with a sub I just whipped together.
I inspected a couple, and they seem to be properly converted, but if they aren't, please get bak to me. In an hour or two, I'll build a reader, and test each one. If I screwed up, I'll fix them, and repost.
BTBTW, Yes, I'll be making more new ones for the contest, that should be even more difficult, and hopefully, My progie will be able to generate patterns with Numbers revealed < 22. I also hope I can make them with Visual Patterns, such as the revealed cells form smilie faces, or other symetrical patterns.
:wave:
-Lou
PS: If you can, maybe you could open a new thread for these test patterns in the contest area?
I can't do that...but I will contact someone that might do it for me.
Thanks for everything you have done.
- ØØ -
"Tab deliminated" :lol: You invent that format yourself Lou? :D
My program is getting complicated now, I have 9 classes and 1 interface so far. Its getting out of hand. :eek:
Don't think you should be using classes there. IINM, instantiating them should cause your time taken to solve to increase? UIA. :(
IINM, UIA????
What?
you can't get me to tell you how my program works before the contest finishes.
"Verily, I wath not borne yefterdaye" - William Shakespear
This is my result, how does it look ?
Code:File name Time taken
0000_0001_022.msk 2.71909399947331
0001_0001_022.msk 3.71132311550857
0002_0003_022.msk 3.49031870885219
0003_0003_022.msk 31.7336726734635
0004_0001_022.msk 2.42342045822204
0005_0003_022.msk 4.09064906010559
0006_0003_023.msk 2.15500244535571E-02
0007_0001_023.msk 1.2505083581004
0008_0003_023.msk 1.03720573174657
0009_0001_023.msk 16.5584227430621
0010_0003_023.msk 15.5263699133466
0011_0001_023.msk 3.7023805575411
0012_0001_023.msk 6.52451268700701
0013_0003_023.msk 6.38957079618274
0014_0001_023.msk 1.16988286871575
0015_0003_023.msk 3.19137721931706
0016_0003_023.msk 0.256800431385827
0017_0003_023.msk 4.27013421616944
0018_0001_023.msk 8.66439679470298
0019_0001_023.msk 2.58067997441782
0020_0001_023.msk 0.127753658628344
0021_0000_023.msk 0.119299710319401
0022_0003_023.msk 0.147342517838556
0023_0003_023.msk 8.53933460241024
0024_0001_023.msk 12.7805091155337
0025_0003_023.msk 5.99652135485246
0026_0001_023.msk 0.470022306660146
0027_0001_023.msk 0.964925322598849
0028_0000_023.msk 0.122390870672034
0029_0003_023.msk 3.11695027275121
0030_0003_023.msk 28.9548248749106
0031_0003_023.msk 28.298185731663
0032_0003_023.msk 8.44545747212922
0033_0003_023.msk 11.4160296853642
0034_0001_023.msk 2.03757704626111
0035_0003_023.msk 0.440596415986356
0036_0001_023.msk 0.723511972210727
0037_0003_023.msk 0.518182541414293
0038_0001_023.msk 0.274212226778526
0039_0003_023.msk 10.9860151938101
0040_0003_023.msk 2.97657928094002
0041_0000_023.msk 7.80455629710445
0042_0003_023.msk 20.6754762273805
0043_0000_023.msk 0.286548808045847
0044_0001_023.msk 1.32737509248461
0045_0000_023.msk 4.46436900208587
0046_0003_023.msk 14.6780527745382
0047_0003_023.msk 2.25563453594673
0048_0001_023.msk 0.993217180191365
0049_0001_023.msk 1.44367607940509
0050_0003_023.msk 13.9840324442271
0051_0001_023.msk 46.2796064055779
0052_0003_023.msk 0.847475214125378
0053_0001_023.msk 6.52727453611393E-02
0054_0003_023.msk 19.4206162095733
0055_0000_023.msk 3.78575920143461
0056_0003_023.msk 218.038033121402
0057_0003_023.msk 1.09445579925511
0058_0000_023.msk 1.48135816309896
0059_0001_023.msk 0.147877857617597
0060_0001_023.msk 0.294045537957355
0061_0000_023.msk 134.354554757157
0062_0003_023.msk 0.514168767164516
0063_0003_023.msk 3.05458975960272
0064_0001_023.msk 6.08798224295549
0065_0001_023.msk 6.3147506364195
0066_0000_023.msk 2.18249128324743
0067_0000_023.msk 58.7978776519569
0068_0003_023.msk 20.4921087593895
254869317Quote:
Originally Posted by NotLKH
713542896
869371425
972458631
638127954
541693278
187934562
495216783
326785149
Time taken: 1.06426517520869 Seconds
Hmm.
I wasn't able to connect an hour ago, so I've been pinging & tracerting ever since!
Ping and Tracert still fails, but I now find myself able to browse again???
:confused:
Anyways, an hour ago I finished building a routine to load all my msk files, all the sol files, submit the loaded msk array to my solver, build the solved array, and verify that they were valid solutions, while also simultaneously checking them against the sol data.
69 loaded, solved, and verified in under 2 seconds.
Looks like they're good!
:wave:
-Lou
Not Bad at all!Quote:
Originally Posted by CVMichael
Now, how fast can your progie solve it?
:wave:
Ammm.... that was resolved by my program...Quote:
Originally Posted by NotLKH
I don't think any human being can solve that in a second....
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.
- ØØ -
Thanks!
-Lou
Can anyone post their timing results ?
I wanna compare, to know if I should spend time improving my solver or not ?
Quote:
Originally Posted by CVMichael
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!!
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.
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.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)
Edit Commented out a part in the code that caused an invalid answer to be made...
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...
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.
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)
My previous test the highest was 218 seconds, now the same one is 25 seconds, quite a difference !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 !
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...
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. :)
OK, I must have missed a post or something, because you both seem to be working with MSK files.
So what am I missing?
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
I'm too busy to do this :(
I got it to work a little faster, but it still does not even compare with Merri's speeds....
These are my new speeds:
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)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 !
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 ?
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
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...
Quote:
Originally Posted by CVMichael
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.
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:
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....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.
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...
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...
Here it is: the results of my new algorithm that works by doing a lot of very good guesses.
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...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
Update Total time now pushed from 0,67 seconds to 0,43 seconds.
My method works along the lines of:Quote:
Originally Posted by taxes
- 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
Merri, I'm getting close....
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.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
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 !
I'm terribly sorry CVMichael: I've now made mine a hybrid as well.
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.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
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:
It takes 0,2 seconds alone (four times longer than doing all of NotLKH's samples!).Code:wallyb.txt:
..2.9.1.7
.386.....
4........
.....5...
..9.1.3..
...4.....
........4
.....792.
8.6.3.7..
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?Quote:
Originally Posted by Merri
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.
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.
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.Quote:
if the goal is to fill the sudoku with valid values
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:
Quote:
Originally Posted by Merri
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,Quote:
Originally Posted by taxes
I'll take that as an objection?
:wave:
-Lou
Objection to what????Quote:
Originally Posted by Something Else
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:
To What I suggested I was going to do in this post # 108:Quote:
Originally Posted by taxes
http://www.vbforums.com/showpost.php...&postcount=108
It was going to be my final phase of development.
-Lou
Quote:
Originally Posted by Something Else
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:
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 ?
Of course you can make it faster :) Just keep trying ;)
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.
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:Quote:
Originally Posted by CVMichael
Ok I know, merri is going to prove me wrong now :sick:
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:
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.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
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.
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.
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."