The New Sudoku Players' Forum

by **barkholt** » Sun Feb 12, 2006 3:29 am

Hello everybody

I have been reading about some of the different methods people apply when solving sudoku puzzles, and just like everybody else I have been dabling with implementing a computer solver for fun.

Anyway, I was wondering if anyone knew if there is any research out there (some older post on this board?) which has attempted to place the methods in a hierarchy according to strength, to get a better idea about the order in which to apply them.

Kind regards,
Michael

by **Wolfgang** » Sun Feb 12, 2006 10:32 pm

Its a matter of taste, two good ones are

Nick70's:

singles
box-line exclusion
hidden pair
naked pair
x-wing
turbot fish
naked triplet
swordfish
hidden triplet
xy-chain
jellyfish
forcing chain
multi forcing chain
forcing tree

MadOverlord's (susser):

Pinned Squares
Simple Naked Sets
Simple Hidden Sets
Intersection removal
Remote Naked Pairs
Comprehensive Naked Sets
Comprehensive Hidden Sets
BUG Removal
Unique Rectangles and Loops
Simple X-Wing
Swordfish
Jellyfish
Squirmbag
XY-Wing
XYZ-Wing
Simple Forcing Loops
Simple Forcing Chains
Comprehensive Forcing Chains
Fishy Cycles
Nishio
Trebor's Tables
Bowman Bingo
(For my taste, turbot fish/simple coloring should be done as easy nishio earlier)

You see that there are also different names for the same techniques.

by **AndrewStuart** » Mon Feb 20, 2006 8:07 pm

Singles
Naked Pairs,
Hidden Pairs,
Intersection Removal,
Naked Triples,
Hidden Triples,
Hidden Quads,
Naked Quads,
Unique Rectangle,
Y-Wing,
X-Wing,
Y-Wing Chain,
Sword-Fish,
Remote Pair Chain,
XY-Chain,
BUG,
Guardian/Turbot

is my prefered order but its arbitary at the last 7. (I need to update my naming conventions which is a chore). My experience is that few routes are unique

by **Mike Barker** » Tue Feb 28, 2006 6:23 am

I would suggest that the order which one uses techniques to advance a puzzle depends on how likely the technique is to be effective. As a first cut, I've started to program up many of the techniques discussed on the site, including:

I still hope to include Unique loops, BUG/BUG-lite, AUR and AUL. I may also include multi-colouring, but I would expect X-cycles to cover both simple and multi-colouring. With my solver if I run simple colouring after X-cycles I get no further reductions for Top1465 which suggests this may be the case. The idea is that I don't necessarily care to solve the puzzle (if that's the issue I can just run suexk and get the answer in milliseconds), but to know if I've done all that this human can do.

Back to the question of hierarchy. If I run my solver and order the results based on the number of puzzles which a technique advances (maybe next time I record the actual number of times a technique is used), I get the following order for Top1465 where the number of puzzles is shown in parenthesis. The numbers in braces are the order for 1000 randomly generated puzzles using suexg.

1) [3] Hidden single (1420)
2) [4] Locked line/block (1396)
3) [1] Naked single (1060)
4) [2] Naked pair (933)
5) [5] Locked block/block (671)
6) [7] Naked triple (599)
7) [13] Hidden Pair (548)
8) [18] Grouped type 1 colouring (306)
9) [6] Generalized WXYZ-wing (304)
9) [8] ALS-xz rule with at least 2 cells per ALS (304)
11) [12] ALS-xz rule with at least 3 cells per ALS (283)
12) [10] X-wing Fillet-o-fish (277)
13) [17] ALS-xz rule with at least 4 cells per ALS (257)
14) [11] Generalized VWXYZ-wing (237)
15) [15] Swordfish Fillet-o-fish (179)
16) [20] Grouped Turbot Fish (126)
17) [22] Hidden Triple (122)
18) [9] XY-wing (114)
19) [19] Turbot Fish (113)
20) [23] Grouped type 3 colouring (105)
21) [14] Generalized XYZ-wing (97)
22) [16] X-wing (78)
23) Type 1 Unique Rectangles (49)
24) Type 4/4B Unique Rectangles (46)
25) Swordfish (33)
26) [21] 4-node XY-chain (22)
27) SueDeCoq (19)
28) Type 2/2B Unique Rectangles (19)
etc.

This looks like an advertisement for ALS, grouping and fillets. Probably the most significant differences between the Top1465 and random draws are X, XY, and XYZ-wings being more prevalent and coloring less so. Two notable underachievers: no ungrouped Type 3 colouring advancements were found and only 4 XY-ring advancements. I probably still have bugs in my code and I only actually solve 622 of the 1465 puzzles. Has anyone seen similar results?

It would be nice to know which techniques actually crack the puzzle (ie only beginning techniques are required following use of the technique(s)) - something for the future.

by **Myth Jellies** » Tue Feb 28, 2006 8:44 am

Interesting to compare these numbers with the predicted prevalence ratios of 4:1 for x-wing filets versus x-wings, and between 6:1 and 9:1 for swordfish filets versus swordfish. If multiple incidents per puzzle were taken into account, these might be even closer to predicted values.

by **tarek** » Tue Feb 28, 2006 10:13 am

hi Mike Barker,

I was just curious, I myself use Box-Box interaction after Box-line interaction (like yourself) however, because of that I haven't come accross a puzzle that required Box-Box interaction after passing Box-line interaction........

Using finned fishes (filet-o-fish), do you actually need simple colouring ??!!!

I still have some issues with contradiction elimination in some of colouring's subtypes, but are there any examples where you would need it where finned fishes would not ???

Tarek

by **ronk** » Tue Feb 28, 2006 11:57 am

tarek wrote:I myself use Box-Box interaction after Box-line interaction

Using Angus Johnson's hints, I translate both his "locked candidates 1" and "locked candidates 2" to "box-line interaction". (Actually, one of them seems more like line-box.)

I'm not aware of any other locks, so what is "box-box interaction"?

TIA, Ron

by **tarek** » Tue Feb 28, 2006 1:10 pm

I think the best way to explain is through this link on simes's site:

http://www.simes.clara.co.uk/programs/sudokutechnique4.htm

all the examples given for that technique can be solved using the regular Box-line or line-Box interactions:

Code: Select all: . . . | . . 3 | 9 4 8 3 . 9 | . . 8 | 5 . . . . 4 | . . . | . . 2 -------+-------+------ 5 . . | 9 . . | . . . . . 7 | . 1 . | 6 . . . . . | . . 7 | . . 1 -------+-------+------ 6 . . | . . . | 1 . . . . 8 | 7 . . | 2 . 9 1 7 5 | 3 . . | . . . . 7 . | . . . | 1 . . . 8 6 | 7 3 . | . . . 2 9 . | 6 . . | . . . -------+-------+------ 7 . 3 | . 1 . | . . 2 . . . | 5 . 4 | . . . 5 . . | . 2 . | 8 . 4 -------+-------+------ . . . | . . 3 | . 8 1 . . . | . 6 5 | 7 9 . . . 1 | . . . | . 4 . . 2 . | . . . | . 8 . . . 8 | . 9 . | . . 7 3 . . | . . 1 | . 2 . -------+-------+------ 2 . 5 | 1 7 . | . . 4 . . . | 8 . 2 | . . . 9 . . | . 5 6 | 1 . 2 -------+-------+------ . 9 . | 7 . . | . . 5 1 . . | . 6 . | 7 . . . 4 . | . . . | . 3 . 4 . 6 | . 5 . | 1 2 . . . . | 4 . . | . . 8 . 9 2 | . . . | . 7 . -------+-------+------ . 2 . | . 8 . | . . . 7 . . | 1 . 3 | . . 6 . . . | . 9 . | . 4 . -------+-------+------ . 1 . | . . . | 5 6 . 2 . . | . . 5 | . . . . 4 5 | . 1 . | 3 . 2

so, from a programmer's point of view, it seems redundant, however it may be interesting for manual pencil & eraser solvers.

That is why I'm interested in seeing one of Mike Barker's 671 puzzles requiring Locked Block-Block interactions, as he places that technique after the usual Box-line interaction.

Tarek

by **Mike Barker** » Tue Feb 28, 2006 3:01 pm

Puzzle 8 of top1465 requires box/box after box/line

Code: Select all: 7.5.....2 ...4.1... 3........ .1.6..4.. 2...5.... .......9. ...37.... .8....6.. .9.....8.

which proceeds to

Code: Select all: +------------+-------------------+----------------------+ | 7 46 5 | 89 3689 369 | 1389 1346 2 | | 89 26 89 | 4 236 1 | 357 3567 3567 | | 3 246 1 | 25789 2689 25679 | 89 46 4689 | +------------+-------------------+----------------------+ | 589 1 89 | 6 238 237 | 4 2357 3578 | | 2 37 46 | 1789 5 3479 | 1378 1367 13678 | | 58 37 46 | 1278 12348 2347 | 123578 9 135678 | +------------+-------------------+----------------------+ | 6 5 2 | 3 7 8 | 19 14 149 | | 14 8 37 | 1259 1249 2459 | 6 123457 13457 | | 14 9 37 | 125 1246 2456 | 12357 8 13457 | +------------+-------------------+----------------------+

which has a box/box interaction in the bottom band. Based on the "sadman" definitions (here) the two techniques appear to be different. My guess is that your solver combines both into box/line since they are basically operating off of the same kind of data.

As far as coloring, I did implement the finned x-wing and swordfish prior to x-cycles and coloring, but needed the x-cycle before no color advancements were observed. Included in the x-cycles are fishy cycle versions of the x-wing and swordfish (what I'd call an x-wing with a tail - two elements of the x-wing in the same box, but not the same line - in this case a turbot fish), maybe this is the difference.

Anyone know where can I find a published list of occurances of techniques?

by **ronk** » Tue Feb 28, 2006 3:40 pm

Mike Barker wrote:... which has a box/box interaction in the bottom band. Based on the "sadman" definitions (here) the two techniques appear to be different. My guess is that your solver combines both into box/line since they are basically operating off of the same kind of data.

If you're talking about the grouped x-wings in 1s and 4s in boxes 7 & 8, I see the line-box and box-box techniques as equivalent -- same eliminations for the same grid conditions. IOW candidates ONLY in rows 8 and 9 of boxes 7 & 8 (for the box-box deduction) is equivalent to NO candidates in row 7 of boxes 7 & 8 (for the line-box deduction).

However, I'm not so sure about the "skewed x-wing" shown on the simes site.

Ron

P.S. I posted this last Nov on the Programmers' Forums ...

Code: Select all: block 1 block 2 block 3 row 1 [ ---- x -----] [ ---- x -----] [ ---- x -----] row 2 [ ---- x -----] [ ---- x -----] [ ---- x -----] row 3 [ --- no x ---] [ --- no x ---] [ ---- x -----]

X-wing by boxes finds that blocks 1 and 2 each contain candidates x in both rows 1 and 2 but not row 3. Since each box and each row must contain exactly one x, either b1r1 and b2r2 ... or b1r2 and b2r1 ... contain the true candidates. This allows the safe elimination of candidates x from rows 1 and 2 of block 3.

The well-known Locked Candidates 2 finds candidates x of row 3 only in block 3, and eliminates the same candidates x from rows 1 and 2 of block 3.

Since the latter technique is easier to understand and simpler to program, there is no reason to use x-wing by boxes IMHO.

by **tarek** » Tue Feb 28, 2006 4:46 pm

Looking at the above example, here is how the solver treats it as box-line interaction:

Code: Select all: *--------------------------------------------------------------------------* | 7 46 5 | 89 3689 369 | 1389 1346 2 | | 89 26 89 | 4 236 1 | 357 3567 3567 | | 3 246 1 | 25789 2689 25679 | 89 46 4689 | |------------------------+------------------------+------------------------| | 589 1 89 | 6 238 237 | 4 2357 3578 | | 2 37 46 | 1789 5 3479 | 1378 1367 13678 | | 58 37 46 | 1278 12348 2347 | 123578 9 135678 | |------------------------+------------------------+------------------------| | 6 5 2 | 3 7 8 |*19 *14 *149 | | 14 8 37 | 1259 1249 2459 | 6 123457 13457 | | 14 9 37 | 125 1246 2456 | 12357 8 13457 | *--------------------------------------------------------------------------* Eliminating 1 From r8c8 (Row 7 & Box 9 Box-line interaction) Eliminating 1 From r8c9 (Row 7 & Box 9 Box-line interaction) Eliminating 1 From r9c7 (Row 7 & Box 9 Box-line interaction) Eliminating 1 From r9c9 (Row 7 & Box 9 Box-line interaction) *--------------------------------------------------------------------------* | 7 46 5 | 89 3689 369 | 1389 1346 2 | | 89 26 89 | 4 236 1 | 357 3567 3567 | | 3 246 1 | 25789 2689 25679 | 89 46 4689 | |------------------------+------------------------+------------------------| | 589 1 89 | 6 238 237 | 4 2357 3578 | | 2 37 46 | 1789 5 3479 | 1378 1367 13678 | | 58 37 46 | 1278 12348 2347 | 123578 9 135678 | |------------------------+------------------------+------------------------| | 6 5 2 | 3 7 8 | 19 *14 *149 | | 14 8 37 | 1259 1249 2459 | 6 23457 3457 | | 14 9 37 | 125 1246 2456 | 2357 8 3457 | *--------------------------------------------------------------------------* Eliminating 4 From r8c8 (Row 7 & Box 9 Box-line interaction) Eliminating 4 From r8c9 (Row 7 & Box 9 Box-line interaction) Eliminating 4 From r9c9 (Row 7 & Box 9 Box-line interaction)

The reason why box-box interaction is redundant is that whenever it is present, there will be an interaction between the 3rd line & the 3rd box achieving the same result,

In the above example where a box-box interaction exists between box 7 & 8 (in rows 8&9) there exists a Line box interaction between line 7 & Box 9.

Are there any examples where filet-o-fish failed crack a puzzle & colouring did ???!!!

Tarek

by **Mike Barker** » Tue Feb 28, 2006 6:56 pm

I think we have a difference in terminology. As I understand Sadman's definition a box/line interaction would occur if rows 8 and 9 of the right chute contained no 1's, then 1's could be eliminated from columns 1-6 of row 7. As you've presented it I believe your box/line and my box/box interactions are really the same.

I agree a grouped X-wing, as opposed to a finned X-wing, is never required. a grouped 4-node X-cycle = grouped X-wing = locked candidates 2 = box/box interaction = block/block interaction, etc.

The reason I need x-cycles to avoid colouring eliminations is that I don't evaluate the sashimi fillet since for an X-wing this is equivalent to a grouped turbot fish which is a much more powerful technique. The same is true for a 2-2-2 swordfish (it turns into a 7-node x-cycle). I'm not sure about NxN fish with more nodes. The bottom line is that we agree that simple colouring is not required. I'm not so sure about multi-colouring. Any thoughts?

by **Mike Barker** » Fri Mar 03, 2006 2:17 am

I went ahead and reran my solver with 25000 random puzzles first moving colors after grouped turbot fish (so there are now no color eliminations) and changing it so it records the number of times a technique is used not just the number of puzzles it is used in. The results are pretty much the same (except for coloring), but I do get about a 2:1 ratio for X-wing vs finned X-wing and 6:1 for swordfish. Does anyone know of any other published results for frequency of occurrence? The numbers in parenthesis are the number of usages per 10000 puzzles so 309097 would mean 30.9 usages per puzzles.

by **Havard** » Fri Mar 03, 2006 11:36 am

Hi Mike!

Good work! I find that really interesting!

However, I do have a few questions.

First of all what are the order your solver applies the different technique. For this statistic to make any sense to me, I need to know what order your solver applies the different techniques. The reason for this, is that a lot of your techniques will find the same thing. For example, the Finned X-wing will pick up on a lot of Skyscrapers, which is one of the basic patterns of the Turbot Fish, so depending on which one of these you apply first, you will get different results. It is also quite common that a Naked Triple and a Hidden Pair is the same thing, and Naked Quadruples are quite rare if a hidden triple is issued first. You know all this of course, but it just proves the point about the importance of the order the techniques are applied in. Could you list the same techniques in the order your solver applied them?

Next question is whether these techniques actually solved the puzzles you analyzed. Say if a puzzle, after having applied a lot of different techniques to it, still was unsolved. Would your program discard that puzzle, or would the techniques applied still be counted? Looking through your list I can't quite understand how those techniques can solve every single one of 25000 puzzles. Having done similar experiments myself, I have alwas ended up with quite a few that defied all the techniques you have listed. (tabeling, or looong chains was required...) Granted, your list is very impressive, but it would be noting less than sensational if you actually could crack every single one of the 25000 with it!

Now if there were unsolved puzzles in your 25000, did your solver count applied techniques even if the puzzle did not solve? Now if this was the case it would not quite work for me, because when having to resort to tabeling for example, it does not really matter that much what techniques you have applied prior to that... I guess what I am saying is that I think the techniques needs to solve the puzzle in order to be counted.

(at least when tabeling and similar stuff are not part of your list)

And finally: Some of the result really made me want to have a look at the puzzles! Is it possible for you to post a few of the rare-finds puzzles here? I would love to see the one that needed Jellyfish, and a few samles of Finned Squirmbag and Jellyfish. Heck, any puzzle that has a complex single-candidate pattern like (grouped) Turbot Chains etc is interesting if you can find them!

My interest in this is that I hope to find simpler patterns that will allow the same eliminations...

well again, great work, and I hope to hear from you soon!

havard

by **tarek** » Fri Mar 03, 2006 1:03 pm

This is interesting Mike.........

regarding the Box-line & box-box interactions, the method which I use for box-line reductions is the one used by virtually everybody I know on these boards, which means that it will have box-box in it by default.

As for your results using the techniques you mentioned, as Havard mentioned, it would br interesting to examine closely those puzzles with finned Jellyfishes or squirmbags, or any complex grouped x-cycle technique.

I will give it a try on the weekend (leaving my PC working while I'm away) testing the top 1465

Tarek

The New Sudoku Players' Forum

Method hierachy

Method hierachy