Contest 6 - Sudoku solver

Re: Contest 6 - Sudoku solver - Discussion

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

Re: Contest 6 - Sudoku solver - Discussion

Just curious people...what's your solution for this one?

Code:

6....2... .4.....3. ...89..2. ..5...389 ....3.5.. 9....1... 42.68.7.. ..71..89. .........

Re: Contest 6 - Sudoku solver - Discussion

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

VB Code:

'/// <summary>
    '/// Returns the time that has passed since the Reset() method was called.
    '/// </summary>
    '/// <remarks>The time is returned in tenths-of-a-millisecond. 
    '/// If the Peek method returns '10000', it means the interval took exactely
    '/// one second.</remarks>
    '/// <returns>A long that contains the time that has passed since the
    '/// Reset() method was called.</returns>
    '/// <exception cref="NotSupportedException">The system does not 
    '/// have a high-resolution performance counter.</exception>
    Public Function Peek() As Long
        Return CType((((GetValue() - StartTime) / CType(Frequency, Double)) * 10000), Long)
    End Function

Like the comments indicate, this will give you an accuracy up to 1/10 of a msec. The cast to long incurs rounding and it should be a cast to double.

VB Code:

Public Function Peek() As Double
        Return CType((((GetValue() - StartTime) / CType(Frequency, Double)) * 10000), Double)
    End Function

Any arguments?

Re: Contest 6 - Sudoku solver - Discussion

Quote:

Originally Posted by ntg

Just curious people...what's your solution for this one?

Code:

6....2... .4.....3. ...89..2. ..5...389 ....3.5.. 9....1... 42.68.7.. ..71..89. .........

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

689342175
542716938
173895624
215467389
764938512
938251467
421689753
357124896
896573241

Time 203.59 Milliseconds

Re: Contest 6 - Sudoku solver - Discussion

It's not a question of timing...what's wrong with this solution?

Code:

693452178 842716935 751893624 165247389 274938561 983561247 429685713 537124896 816379452

Re: Contest 6 - Sudoku solver - Discussion

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

Re: Contest 6 - Sudoku solver - Discussion

Quote:

Originally Posted by ntg

It's not a question of timing...what's wrong with this solution?

Code:

693452178 842716935 751893624 165247389 274938561 983561247 429685713 537124896 816379452

693452178
842716935
751893624
165247389
274938561
983561247
429685713
537124896
816379452

The 8 is 2 times in the first vertical line

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

Re: Contest 6 - Sudoku solver - Discussion

Quote:

Originally Posted by CVMichael

693452178
842716935
751893624
165247389
274938561
983561247
429685713
537124896
816379452

:blush:

Re: Contest 6 - Sudoku solver - Discussion

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

That's the first thing I did :)

Re: Contest 6 - Sudoku solver - Discussion

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

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

Re: Contest 6 - Sudoku solver - Discussion

ntg, you gave me a briliant idea :)

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

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

Re: Contest 6 - Sudoku solver - Discussion

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

Re: Contest 6 - Sudoku solver - Discussion

Quote:

Originally Posted by ntg

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

That's good to know.... I was turning red... :D

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

Re: Contest 6 - Sudoku solver - Discussion

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

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

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

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

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

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

1 Attachment(s)

Re: Contest 6 - Sudoku solver - Discussion

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

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

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

:wave:
-Thanks
-Lou

Re: Contest 6 - Sudoku solver - Discussion

Here is something I did quickly:

Total time for 518 files: 632,245998 milliseconds

Code:

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

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

Re: Contest 6 - Sudoku solver - Discussion

Code:

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

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

1 Attachment(s)

Re: Contest 6 - Sudoku solver - Discussion

Can I play too? :lol:

Re: Contest 6 - Sudoku solver - Discussion

Thanks Merri!

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

:wave:
-Lou

Re: Contest 6 - Sudoku solver - Discussion

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

Re: Contest 6 - Sudoku solver - Discussion

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

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

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

Re: Contest 6 - Sudoku solver - Discussion

Quote:

Originally Posted by NotLKH

NTG,
Do you have any kind of rating sequence in your filenames?
:wave:
-Lou

Ehm....no. Actually, these were taken from the web. :p

Re: Contest 6 - Sudoku solver - Discussion

Quote:

Originally Posted by Brick1

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

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

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

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

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

Re: Contest 6 - Sudoku solver - Discussion

Quote:

Originally Posted by ntg

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

VB Code:

'/// <summary>
    '/// Returns the time that has passed since the Reset() method was called.
    '/// </summary>
    '/// <remarks>The time is returned in tenths-of-a-millisecond. 
    '/// If the Peek method returns '10000', it means the interval took exactely
    '/// one second.</remarks>
    '/// <returns>A long that contains the time that has passed since the
    '/// Reset() method was called.</returns>
    '/// <exception cref="NotSupportedException">The system does not 
    '/// have a high-resolution performance counter.</exception>
    Public Function Peek() As Long
        Return CType((((GetValue() - StartTime) / CType(Frequency, Double)) * 10000), Long)
    End Function

Like the comments indicate, this will give you an accuracy up to 1/10 of a msec. The cast to long incurs rounding and it should be a cast to double.

VB Code:

Public Function Peek() As Double
        Return CType((((GetValue() - StartTime) / CType(Frequency, Double)) * 10000), Double)
    End Function

Any arguments?

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

Re: Contest 6 - Sudoku solver - Discussion

Quote:

Originally Posted by NotLKH

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

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

Quote:

Originally Posted by Brick1

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

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

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

Re: Contest 6 - Sudoku solver - Discussion

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

Re: Contest 6 - Sudoku solver - Discussion

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

Re: Contest 6 - Sudoku solver - Discussion

Quote:

Originally Posted by Merri

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

Sorry!

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

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

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

-Lou

Re: Contest 6 - Sudoku solver - Discussion

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

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

Re: Contest 6 - Sudoku solver - Discussion

Quote:

Originally Posted by Merri

In the contest test sudokus there should be a variety of different kinds of sudokus: very easy, easy, medium, hard and very hard.

That sounds exactly right, that should give every algo a fair chance. My code for example won't solve very easy problems fast but it works better for more difficult puzzles and I'd hate to see only easy-medium puzzles being used for timing.

Re: Contest 6 - Sudoku solver - Discussion

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

Apparantly these are two different problems, though.

Re: Contest 6 - Sudoku solver - Discussion

Quote:

Originally Posted by Merri

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

I just used Round(objTimer.RetTime, 15). I figured it out a few minutes after I posted because I widened my textbox and saw that the E stuff was there.

Re: Contest 6 - Sudoku solver - Discussion

Ok I have 3 questions:

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

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

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

Re: Contest 6 - Sudoku solver - Discussion

1) 0.001

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

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

Re: Contest 6 - Sudoku solver - Discussion

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

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

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

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

:wave:
-Lou

Re: Contest 6 - Sudoku solver - Discussion

Quote:

Originally Posted by si_the_geek

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

I hope we can clear this up before submission time. :thumb:

Re: Contest 6 - Sudoku solver - Discussion

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

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

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

Re: Contest 6 - Sudoku solver - Discussion

Quote:

Originally Posted by eyeRmonkey

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

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

Re: Contest 6 - Sudoku solver - Discussion

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

Re: Contest 6 - Sudoku solver - Discussion

Exactly ;)