| dukuso
| Joined: 14 Jul 2005 | Posts: 424 | : | Location: germany | Items |
|
Posted: Tue Aug 30, 2005 7:43 am Post subject: comparing the solvers |
|
|
correlation coefficients*100 of solving times
for the contest puzzles from :
http://www.vbforums.com/attachment.php?attachmentid=39939
by different solvers:
Code: |
bri mer rae bpd eye kaf xyz duk sat
bri -- 22 05 04 07 20 28 36 18
mer 22 -- 09 03 08 29 36 42 29
rae 05 09 -- 05 01 20 07 12 26
bpd 04 03 05 -- 00 03 03 02 07
eye 07 08 01 00 -- 07 07 07 01
kaf 20 29 20 03 07 -- 23 40 28
xyz 28 36 07 03 07 23 -- 39 20
duk 36 42 12 02 07 40 39 -- 29
sat 18 29 26 07 01 28 20 29 --
sum 143 182 089 030 042 174 167 211 161
relative time needed to solve
easier --> harder puzzles: (average=100)
bri 15 28 42 57 76 89 101 147 150 300
mer 32 51 66 72 87 100 112 126 158 200
rae 25 60 73 54 84 94 116 122 151 215
bpd 72 76 81 80 83 87 89 92 195 148
eye 7 35 92 82 51 75 101 110 205 242
kaf 4 5 13 25 31 47 61 106 195 485
xyz 76 77 82 86 92 98 105 114 124 151
duk 49 51 62 77 84 96 104 129 144 209
sat 57 76 73 86 96 93 104 117 127 176
|
note: these tables say nothing about performance of the
solvers, only how they correlate and whether they
do relatively better on hard or easy instances.
bri : solver from Brick1 for the VB6-contest
mer : solver by Merri for the VB6-contest discussed here
rae : solver from Raetwulf for the VB6-contest
bpd : solver from bpd for the VB6-contest
eye : solver from eyeRmonkey for the VB6-contest
kaf : solver from kaffenils for the VB6-contest
xyz : solver by xyzzy disussed here
duk : solver by dukuso discussed here
sat : "SATZ"-solver by Li , run on SAT-converted sudokus
http://www.laria.u-picardie.fr/~cli/EnglishPage.html
see also the VB6 forum:
http://www.vbforums.com/showthread.php?t=351476&page=10&pp=40
and
http://www.vbforums.com/forumdisplay.php?f=68
... for the source-code of the contest-entries
----------------------------------
Since the correlation of the different programs
is surprisingly low in some cases, it was suggested that this
might be due to different orderings of the sudoku's
rows and columns.
So I tried the contest instances on 10 randomized versions
of my solver, where the 729 placements and the 324 constraints
were all shuffled randomly.
typically I get correlation matrices like this:
Code: |
-- 27 17 30 32 34 29 25 33 31
27 -- 20 34 40 45 34 31 41 40
17 20 -- 23 20 21 17 18 24 24
30 34 23 -- 33 39 28 31 33 35
32 40 20 33 -- 42 36 32 40 42
34 45 21 39 42 -- 37 35 42 38
29 34 17 28 36 37 -- 23 29 37
25 31 18 31 32 35 23 -- 32 32
33 41 24 33 40 42 29 32 -- 42
31 40 24 35 42 38 37 32 42 --
sum:362 416 288 390 420 437 373 363 421 425
but in some rare cases (about 10% probability)
you can also see correlations like this:
-- 28 14 31 23 24 25 17 08 09
28 -- 16 40 33 33 33 28 10 16
14 16 -- 24 14 22 16 10 12 04
31 40 24 -- 38 31 39 25 16 16
23 33 14 38 -- 35 36 29 10 14
24 33 22 31 35 -- 39 25 11 12
25 33 16 39 36 39 -- 24 10 09
17 28 10 25 29 25 24 -- 10 09
08 10 12 16 10 11 10 10 -- 05
09 16 04 16 14 12 09 09 05 --
sum: 282 341 237 363 335 335 334 282 196 199
or even this:
-- 04 06 07 10 20 00 99 01 00
04 -- 05 04 08 14 00 98 00 18
06 05 -- 09 12 17 02 99 00 00
07 04 09 -- 12 14 00 99 01 00
10 08 12 12 -- 24 01 00 10 00
20 14 17 14 24 -- 03 98 01 04
00 00 02 00 01 03 -- 99 00 99
99 98 99 99 00 98 99 -- 99 98
01 00 00 01 10 01 00 99 -- 99
00 18 00 00 00 04 99 98 99 --
sum: 149 154 154 150 182 198 107 93 115 122
|
(99 usually means: negative correlation of -0.01)
yes, I once got this. (out of some hundred trials)
I don't quite know how to interpret it.
This behaviour makes it complicated to define
sudoku-difficulty-levels.
If you want to get your solvers or different versions included
in this statistics, please solve the contest-instances
above and send your 1011 timings to sterten@aol.com
or post them here.
-Guenter. |
|