Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

hardest 16*16
Goto page Previous  1, 2
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Puzzles
View previous topic :: View next topic  
Author Message
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Tue Nov 29, 2005 11:14 am    Post subject: Reply with quote

timings for top44

Code:

correlation-coefficient*100        top44
 1)  2)  3)  4)  5)  6)  7)  8) |   my   sigma    name
----------------------------+---------------------------
 98  28  47  15  51  45  38  -14 |  .342  .139   1) satz     
 28  96  28  17  50  47  33  -11 |  .263  .064   2) satzoo   
 47  28  99  58  17  48  59   17 |  .280  .068   3) guenter1
 15  17  58  99  14  41  60  -03 |  .079  .077   4) guenter2
 51  50  17  14  99  49  30  -13 |  1.37  1.23   5) rubylips
 45  47  48  41  49  99  84   05 |  .979  .706   6) alain1   
 12  11  43  14  16  19  99   37 |  .071  .036   7) alain2
-14 -11  17 -03 -13  05  05   99 |  .113  .163   8) gsf     






top44, hard 16*16 sudokus, average times
per puzzle in seconds to find the solution

correlations                                  exp.  dev.  program
 99  28  47  15  52  45  38  12 -14  13  -2  .342  .138    sat16               
 28  99  29  17  50  48  33  11 -11  16  25  .263  .063    szo16               
 47  29  99  58  17  48  59  43  17  40  22  .284  .072    gua16               
 15  17  58  99  14  41  60  14  -3  24  30  .079  .076    gub16               
 52  50  17  14  99  50  30  16 -14  21  16  1.369  1.23   rub16               
 45  48  48  41  50  99  84  19   5  28  14  .979  .705    ala16               
 38  33  59  60  30  84  99  23   5  24  10  .074  .048    alb16               
 12  11  43  14  16  19  23  99  37  66   8  .076  .039    alc16               
-14 -11  17  -3 -14   5   5  37  99  30 -11  .113  .162    gsf16               
 13  16  40  24  21  28  24  66  30  99  28  .024  .013    gsg16               
 -2  25  22  30  16  14  10   8 -11  28  99  .091  .078    xyz16               
----------------------------------------------------------------
sat szo gua gub rub ala alb alc gsf gsg xyz


+99 +24 +50 +22 +32 +40 +42 +14 -19 +19  +7  .117  .038    satz new

this table is being edited=updated, good to see some progress here !
still the old (slow) encoding for SATZ,SATZOO





latest (2.Dec.11:15 GMT)

Code:


sag szo gub rub ald gsg xyz  exp.  dev.     name                               
----------------------------------------------------------------------         
 99  24  22  32  44  19   7  .117  .038     satz (short encoding)
 24  99  17  50  44  16  25  .263  .063     satzoo (long)
 22  17  99  14  51  24  30  .079  .076     guenter
 32  50  14  99  45  21  16  1.369  1.23    rubylips
 44  44  51  45  99  24   7  .058  .038     alain
 19  16  24  21  24  99  28  .024  .013     gsf
  7  25  30  16   7  28  99  .091  .078     xyzzy
----------------------------------------------------------------------         
sag szo gub rub ald gsg xyz  exp.  dev.     name                               
 24  29  26  29  35  22  18                                                     





my=exp.: expectation value, average seconds per puzzle (2.6GHz)
sigma=dev.: deviation
timings are for finding the solution only.
complete search timings are divided by 2

my actual version is at
http://magictour.free.fr/sudqwh.exe
source code attached to the executable as usual.
It's also pretty fast for QWHs, but not for 25*25 sudokus



please report errors to sterten@aol.com so I can just
edit and correct the table


-Guenter.


Last edited by dukuso on Fri Dec 02, 2005 11:31 am; edited 19 times in total
Back to top
View user's profile Send private message Send e-mail Visit poster's website
frisch

Joined: 16 Nov 2005
Posts: 55
:
Location: Paris, France

Items
PostPosted: Tue Nov 29, 2005 5:33 pm    Post subject: Reply with quote

Just for the prosperity Wink, the current timings with my solver are:

Code:

Puzzle  1:  time:    151 ms
Puzzle  2:  time:    169 ms
Puzzle  3:  time:    162 ms
Puzzle  4:  time:    292 ms
Puzzle  5:  time:    250 ms
Puzzle  6:  time:    159 ms
Puzzle  7:  time:    131 ms
Puzzle  8:  time:    108 ms
Puzzle  9:  time:    101 ms
Puzzle 10:  time:    494 ms
Puzzle 11:  time:    202 ms
Puzzle 12:  time:    385 ms
Puzzle 13:  time:    140 ms
Puzzle 14:  time:     46 ms
Puzzle 15:  time:    228 ms
Puzzle 16:  time:    169 ms
Puzzle 17:  time:    191 ms
Puzzle 18:  time:    189 ms
Puzzle 19:  time:     49 ms
Puzzle 20:  time:     34 ms
Puzzle 21:  time:    118 ms
Puzzle 22:  time:    112 ms
Puzzle 23:  time:    105 ms
Puzzle 24:  time:    238 ms
Puzzle 25:  time:    100 ms
Puzzle 26:  time:     94 ms
Puzzle 27:  time:     25 ms
Puzzle 28:  time:     88 ms
Puzzle 29:  time:     86 ms
Puzzle 30:  time:    187 ms
Puzzle 31:  time:     76 ms
Puzzle 32:  time:     99 ms
Puzzle 33:  time:     92 ms
Puzzle 34:  time:     88 ms
Puzzle 35:  time:    119 ms
Puzzle 36:  time:     61 ms
Puzzle 37:  time:    173 ms
Puzzle 38:  time:     93 ms
Puzzle 39:  time:     96 ms
Puzzle 40:  time:     46 ms
Puzzle 41:  time:     96 ms
Puzzle 42:  time:     99 ms
Puzzle 43:  time:     90 ms
Puzzle 44:  time:     65 ms



And for finding the solution only:

Code:

Puzzle  1:  time:    113 ms
Puzzle  2:  time:    122 ms
Puzzle  3:  time:    133 ms
Puzzle  4:  time:    106 ms
Puzzle  5:  time:     63 ms
Puzzle  6:  time:    150 ms
Puzzle  7:  time:    113 ms
Puzzle  8:  time:    106 ms
Puzzle  9:  time:     57 ms
Puzzle 10:  time:     56 ms
Puzzle 11:  time:     52 ms
Puzzle 12:  time:     25 ms
Puzzle 13:  time:    140 ms
Puzzle 14:  time:     48 ms
Puzzle 15:  time:    115 ms
Puzzle 16:  time:     78 ms
Puzzle 17:  time:    128 ms
Puzzle 18:  time:     12 ms
Puzzle 19:  time:     16 ms
Puzzle 20:  time:     27 ms
Puzzle 21:  time:     69 ms
Puzzle 22:  time:     45 ms
Puzzle 23:  time:     77 ms
Puzzle 24:  time:    131 ms
Puzzle 25:  time:     34 ms
Puzzle 26:  time:     64 ms
Puzzle 27:  time:     23 ms
Puzzle 28:  time:     71 ms
Puzzle 29:  time:     79 ms
Puzzle 30:  time:    109 ms
Puzzle 31:  time:     37 ms
Puzzle 32:  time:     66 ms
Puzzle 33:  time:     54 ms
Puzzle 34:  time:     44 ms
Puzzle 35:  time:     34 ms
Puzzle 36:  time:     55 ms
Puzzle 37:  time:     49 ms
Puzzle 38:  time:     65 ms
Puzzle 39:  time:     95 ms
Puzzle 40:  time:     38 ms
Puzzle 41:  time:     55 ms
Puzzle 42:  time:     87 ms
Puzzle 43:  time:     42 ms
Puzzle 44:  time:     38 ms
[/code]
Back to top
View user's profile Send private message Send e-mail Visit poster's website
frisch

Joined: 16 Nov 2005
Posts: 55
:
Location: Paris, France

Items
PostPosted: Wed Nov 30, 2005 5:56 am    Post subject: Reply with quote

``complete search timings are divided by 2''

I should explain why this is not true for my solver in many cases. It's not that my solver is oriented toward finding a solution. No heuristic for that.

The point is that I do quite a lot of non-backtracking
reasonning (forward propagation [a.k.a singles?] + 1-look-ahead) before branching. So, a grid which is cracked e.g. only because of chaining before starting to backtrack
will take the same time to find one solution or to check unicity.
(I don't display the display in the middle of the chaining process even if it is found.)
Back to top
View user's profile Send private message Send e-mail Visit poster's website
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Wed Nov 30, 2005 6:23 am    Post subject: Reply with quote

frisch wrote:
``complete search timings are divided by 2''

I should explain why this is not true for my solver in many cases. It's not that my solver is oriented toward finding a solution. No heuristic for that.

The point is that I do quite a lot of non-backtracking
reasonning (forward propagation [a.k.a singles?] + 1-look-ahead) before branching. So, a grid which is cracked e.g. only because of chaining before starting to backtrack
will take the same time to find one solution or to check unicity.
(I don't display the display in the middle of the chaining process even if it is found.)



the total timing of your 2nd set is still almost exactly half of that
for your first set, although the correlations changed.
I left the correlations for your 1st (complete) search in the
vertical and only updated the horizontal (I might change this later)
Back to top
View user's profile Send private message Send e-mail Visit poster's website
gsf

Joined: 18 Aug 2005
Posts: 411
:
Location: NJ USA

Items
PostPosted: Wed Nov 30, 2005 7:17 pm    Post subject: Reply with quote

dukuso wrote:
timings for top44

I forgot to propagate the forward check successes back to the current level.
Doing so made a difference (2.8Ghz p4):
Code:

   0.095986       32 1
   0.089986       30 2
   0.058991       16 3
   0.107984       36 4
   0.019997        2 5
   0.077988       23 6
   0.033995       10 7
   0.060990       13 8
   0.033995       10 9
   0.042994       13 10
   0.041993       15 11
   0.012998        3 12
   0.104984       31 13
   0.016998        6 14
   0.020997        4 15
   0.055991       19 16
   0.059991       26 17
   0.051992       18 18
   0.011998        1 19
   0.016998        4 20
   0.038994       14 21
   0.029995        6 22
   0.045993       12 23
   0.092986       17 24
   0.025996        6 25
   0.038994       12 26
   0.016998        1 27
   0.012998        1 28
   0.042993        9 29
   0.089986       24 30
   0.080988       31 31
   0.057991       17 32
   0.048993       11 33
   0.042993       12 34
   0.021997        4 35
   0.037994       13 36
   0.034995        8 37
   0.032995       12 38
   0.039994       13 39
   0.038994       13 40
   0.033995       10 41
   0.031995       11 42
   0.027995        5 43
   0.028996        7 44
8/s/GHz GC 5.6 C/n 9714188 puzzles 44 seconds 2.015694 nodes 581
Back to top
View user's profile Send private message Visit poster's website
xyzzy

Joined: 24 Aug 2005
Posts: 80
:

Items
PostPosted: Thu Dec 01, 2005 11:47 pm    Post subject: Reply with quote

Here's my timings for top44 16x16, on a P2-400MHz:
Code:

Time to solve 1426 ms, required 2585 guesses and 74501 applies
Time to solve 47 ms, required 71 guesses and 2379 applies
Time to solve 1313 ms, required 1827 guesses and 56914 applies
Time to solve 1219 ms, required 1794 guesses and 56797 applies
Time to solve 190 ms, required 273 guesses and 7006 applies
Time to solve 25 ms, required 40 guesses and 1257 applies
Time to solve 785 ms, required 1473 guesses and 40191 applies
Time to solve 248 ms, required 381 guesses and 11393 applies
Time to solve 963 ms, required 1546 guesses and 49500 applies
Time to solve 859 ms, required 1474 guesses and 39249 applies
Time to solve 9 ms, required 14 guesses and 369 applies
Time to solve 366 ms, required 590 guesses and 17296 applies
Time to solve 616 ms, required 948 guesses and 27503 applies
Time to solve 341 ms, required 511 guesses and 16590 applies
Time to solve 666 ms, required 1072 guesses and 32996 applies
Time to solve 2563 ms, required 3789 guesses and 102489 applies
Time to solve 269 ms, required 419 guesses and 12145 applies
Time to solve 481 ms, required 765 guesses and 24265 applies
Time to solve 300 ms, required 543 guesses and 15157 applies
Time to solve 842 ms, required 1424 guesses and 40039 applies
Time to solve 639 ms, required 1018 guesses and 31089 applies
Time to solve 985 ms, required 1651 guesses and 47227 applies
Time to solve 909 ms, required 1545 guesses and 45511 applies
Time to solve 677 ms, required 1148 guesses and 30464 applies
Time to solve 668 ms, required 1287 guesses and 39371 applies
Time to solve 329 ms, required 546 guesses and 15988 applies
Time to solve 464 ms, required 647 guesses and 21404 applies
Time to solve 103 ms, required 124 guesses and 4868 applies
Time to solve 579 ms, required 866 guesses and 31508 applies
Time to solve 587 ms, required 868 guesses and 29927 applies
Time to solve 1486 ms, required 2435 guesses and 57169 applies
Time to solve 187 ms, required 316 guesses and 9511 applies
Time to solve 1653 ms, required 2595 guesses and 70362 applies
Time to solve 254 ms, required 425 guesses and 13042 applies
Time to solve 45 ms, required 57 guesses and 2069 applies
Time to solve 214 ms, required 302 guesses and 10338 applies
Time to solve 539 ms, required 814 guesses and 25393 applies
Time to solve 646 ms, required 1069 guesses and 34170 applies
Time to solve 121 ms, required 237 guesses and 7301 applies
Time to solve 528 ms, required 865 guesses and 21583 applies
Time to solve 72 ms, required 109 guesses and 3702 applies
Time to solve 567 ms, required 885 guesses and 28591 applies
Time to solve 71 ms, required 100 guesses and 2881 applies
Time to solve 405 ms, required 644 guesses and 19869 applies
Total time 26.26 sec, 42092 guesses 1231374 nodes (21.32 us/n)
Back to top
View user's profile Send private message Visit poster's website
frisch

Joined: 16 Nov 2005
Posts: 55
:
Location: Paris, France

Items
PostPosted: Fri Dec 02, 2005 10:50 am    Post subject: Reply with quote

I forgot a very simple propagation rule (when a digit can no longer be placed in a region -> failure). This gives the following timings.

To check for all the solutions:

Code:

Puzzle  1:  time:    120 ms
Puzzle  2:  time:    130 ms
Puzzle  3:  time:    141 ms
Puzzle  4:  time:    276 ms
Puzzle  5:  time:    225 ms
Puzzle  6:  time:    108 ms
Puzzle  7:  time:    115 ms
Puzzle  8:  time:    100 ms
Puzzle  9:  time:     78 ms
Puzzle 10:  time:    338 ms
Puzzle 11:  time:    163 ms
Puzzle 12:  time:    303 ms
Puzzle 13:  time:    116 ms
Puzzle 14:  time:     42 ms
Puzzle 15:  time:    194 ms
Puzzle 16:  time:     68 ms
Puzzle 17:  time:    149 ms
Puzzle 18:  time:    133 ms
Puzzle 19:  time:     38 ms
Puzzle 20:  time:     20 ms
Puzzle 21:  time:     83 ms
Puzzle 22:  time:     94 ms
Puzzle 23:  time:     97 ms
Puzzle 24:  time:    124 ms
Puzzle 25:  time:    134 ms
Puzzle 26:  time:     70 ms
Puzzle 27:  time:     21 ms
Puzzle 28:  time:     21 ms
Puzzle 29:  time:     71 ms
Puzzle 30:  time:    175 ms
Puzzle 31:  time:     60 ms
Puzzle 32:  time:     90 ms
Puzzle 33:  time:     82 ms
Puzzle 34:  time:     50 ms
Puzzle 35:  time:     94 ms
Puzzle 36:  time:     52 ms
Puzzle 37:  time:    144 ms
Puzzle 38:  time:     61 ms
Puzzle 39:  time:     44 ms
Puzzle 40:  time:     41 ms
Puzzle 41:  time:     61 ms
Puzzle 42:  time:     88 ms
Puzzle 43:  time:     69 ms
Puzzle 44:  time:     63 ms
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Puzzles All times are GMT
Goto page Previous  1, 2
Page 2 of 2

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron