|
View previous topic :: View next topic |
Author |
Message |
| dukuso
| Joined: 14 Jul 2005 | Posts: 424 | : | Location: germany | Items |
|
Posted: Tue Nov 29, 2005 11:14 am Post subject: |
|
|
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 |
|
|
| frisch
| Joined: 16 Nov 2005 | Posts: 55 | : | Location: Paris, France | Items |
|
Posted: Tue Nov 29, 2005 5:33 pm Post subject: |
|
|
Just for the prosperity , 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 |
|
|
| frisch
| Joined: 16 Nov 2005 | Posts: 55 | : | Location: Paris, France | Items |
|
Posted: Wed Nov 30, 2005 5:56 am Post subject: |
|
|
``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 |
|
|
| dukuso
| Joined: 14 Jul 2005 | Posts: 424 | : | Location: germany | Items |
|
Posted: Wed Nov 30, 2005 6:23 am Post subject: |
|
|
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 |
|
|
| gsf
| Joined: 18 Aug 2005 | Posts: 411 | : | Location: NJ USA | Items |
|
Posted: Wed Nov 30, 2005 7:17 pm Post subject: |
|
|
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 |
|
|
| xyzzy
| Joined: 24 Aug 2005 | Posts: 80 | : | | Items |
|
Posted: Thu Dec 01, 2005 11:47 pm Post subject: |
|
|
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 |
|
|
| frisch
| Joined: 16 Nov 2005 | Posts: 55 | : | Location: Paris, France | Items |
|
Posted: Fri Dec 02, 2005 10:50 am Post subject: |
|
|
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 |
|
|
|
|
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
|
Powered by phpBB © 2001, 2005 phpBB Group
Igloo Theme Version 1.0 :: Created By: Andrew Charron
|