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   

comparing the solvers

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
dukuso

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

Items
PostPosted: Tue Aug 30, 2005 7:43 am    Post subject: comparing the solvers Reply with quote

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.
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 -> Solving sudoku All times are GMT
Page 1 of 1

 
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