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   

top95 catalog of methods

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

Joined: 05 Oct 2005
Posts: 187
:
Location: St. Olaf College

Items
PostPosted: Fri Nov 25, 2005 2:18 pm    Post subject: top95 catalog of methods Reply with quote

I've created a catalog of the methods used for solving the top95 puzzles.
Here is the summary.
Details, including links for each puzzle that load them directly into Sudoku Assistant, may be found at http://www.stolaf.edu/people/hansonr/sudoku/top95-methods.htm

Methods used (in order of necessity):

cross-hatch scanning (looking for singles; required)
range checking (locked candidates)
row/cell/block subset elimination
W: grid (weak cycle) analysis (X-wings, Swordfish, etc.)
M: 3D Medusa chain analysis -- strong+weak
P: hypothesis and disproof (trial and error)

Uniqueness and magic cells weren't tested.


Code:

methods puzzles
------  -------
basic      25
   M       21
   MP      25
  W         2
  WM        6
  WMP      16
--------------
Total      95


puz  meth  #W   #M   #P  #steps
-------------------------------
 1                         28
 2                         34
 3                         32
 4   M          1          51
 5   M          2          49
 6                         29
 7   MP         5    6     50
 8   M          4          50
 9   MP         6    8     55
10   M          4          52
11   MP         3    3     43
12   MP        10    3     31
13   M          3          32
14  WMP    1    5    1     46
15                         34
16   MP         2    2     43
17   M          4          26
18                         39
19   MP         2    6     32
20   MP         9    2     34
21                         49
22   MP         2    1     30
23                         30
24   M          3          31
25   M          1          25
26                         28
27                         32
28   MP         5    2     39
29   M          7          26
30                         42
31  WMP    1    4    5     36
32   M          3          33
33                         26
34                         39
35  WMP    2   20    6     56
36                         25
37                         30
38  WM     1    1          25
39  WMP    2    8    3     29
40   MP         8    2     39
41   M          2          51
42                         41
43  WMP    1    1    5     34
44                         23
45  WMP    2   32   21     82
46   MP         1    2     35
47   M          4          39
48   MP        16    5     43
49                         34
50   MP        19   10     58
51  WMP    1    3    1     38
52  WM     1   10          49
53  WM     1    2          24
54  WMP    2    9    8     43
55   M          6          26
56   MP         9   12     51
57                         25
58  WMP    1   10   13     52
59  WMP    2    6   10     45
60  WMP    1   14   24     67
61  WMP    1    6    7     41
62                         35
63  W      1               26
64  WMP    2   11    9     55
65   MP        10    4     41
66  WMP    1   11    6     47
67                         41
68   MP         3    1     45
69  WMP    4   12   21     63
70   M          5          34
71  WM     1    1          41
72   M          2          25
73                         41
74   M          1          41
75   MP         7   33     72
76   M          2          45
77  WM     1    1          26
78                         22
79                         42
80   M          1          42
81   MP         8    1     27
82   M          6          32
83   MP         3    2     46
84                         29
85  WM     2   13          37
86   MP        13    3     43
87   M          4          28
88   MP        17    1     50
89   MP        13    3     47
90   MP         3    3     35
91   MP         9    1     35
92   MP        17    1     61
93  WMP    1   12   15     64
94   M          8          33
95  W      1               36

 


Source:

This table was generated as follows:

1. started Sudoku Assistant http://www.stolaf.edu/people/hansonr/sudoku/
2. clicked on "numeric block input"
3. selected "all95", http://magictour.free.fr/top95
4. carried out "automatic run"
5. clicked on "show run log"
6. moved that information into Microsoft Excel
7. played around with it
8. created a pivot table

---Added later to this post:

The original table I had here had some flaws -- I've replaced it with
a better table. Also, at http://www.stolaf.edu/people/hansonr/sudoku/top95-analysis.htm
you will find a detailed discussion of how the top95 puzzles "crack" in terms of X-cycles (coloring), Y-cycles, and 3D Medusa analysis.

I'd have to say the #45 is the all-around "hardest Sudoku" winner, wouldn't you say?

Comments appreciated.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr


Last edited by Bob Hanson on Sat Nov 26, 2005 11:37 pm; edited 1 time in total
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: Sat Nov 26, 2005 5:18 am    Post subject: Reply with quote

I can't see much correlation between your rating and mine.
What do you get on random sudokus after filtering the easy ones ?
Seems that you could just as well have taken the 95 last in
my top2365 list and still get the same numbers for that table !?
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Bob Hanson

Joined: 05 Oct 2005
Posts: 187
:
Location: St. Olaf College

Items
PostPosted: Sat Nov 26, 2005 11:49 pm    Post subject: Reply with quote

Interesting. I wasn't thinking about these as "ratings" -- they just define what methods are necessary for completion (within this finite set of methods). It's along the lines of what Glenn Fowler put up at http://www.research.att.com/~gsf/sudoku/ Although, I did pick out #45 there, I guess.

Anyway, I thought this might be useful. It answered the question I had as to whether the 3D Medusa business is worth trying.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr
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: Sun Nov 27, 2005 5:26 am    Post subject: Reply with quote

Bob Hanson wrote:
... It answered the question I had as to whether the 3D Medusa business is worth trying.


and, what is the answer ?
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