The New Sudoku Players' Forum

[RodHagglund]

‘The dog did nothing in the night-time.’
‘That was the curious incident,’ remarked Sherlock Holmes.
-Conan Doyle, Silver Blaze

I have just spent several weeks attacking the eleven sudokus published by Mr. Mepham on the sudoku.org.uk website and identified as being “unsolvable” without bifurcation, with the hopes that interested players would devise non-bifurcative techiques to solve them. One of the techniques I found to attack the puzzles uses a peculiar property of closed loops of pairs of candidate cells for a number. If the number of cells in the loop is even - that is there are four, six, etc., in the loop - then it is quite possible for all the pairs in the loop to be conjugates - pairs of cells for the candidate that are the only possible locations for that number in the column, row or box they share. An X-wing, for example, is a closed loop of four cells linked in conjugate pairs, while the rarer "Swordfish" is a closed loop of six cells in conjugate pairings.

Strangely enough, this is not possible for a closed loop of five paired cells - sometimes referred to as a "Turbot Fish" - or for any longer loop of an odd number of cells. The reason is that if all the pairings were conjugate, there would be no way to place a number in any of the looped cells without generating an immediate contradiction that would make a valid solution impossible. And we can draw an important inference from what the loop doesn’t do: there must always be one or more other cells for the candidate number that prevent some pairing or pairings from being conjugate by sharing the same column, row or box jointly occupied by the pair. I refer to these as “guardian” cells. Now, logically, it can be concluded that at least one (maybe more) of these “guardians” cells must really contain the candidate number (or the loop would no longer be silent: it would in fact rip the sudoku to shreds).

That means that if there is only one guardian cell the candidate number can immediately be installed in that cell, and if more than one guardian cell is identified, the candidate number can be erased from any cells that are “seen” by all the guardians.

I call this technique the “Broken Wing” - both because the five-cell version looks like an X-wing with one arm twisted, and because the conclusion depends on the fact that the perfect conjugate loop must be broken at one or more places. Unlike colouring, which also loves pairings, the technique is non-bifurcative - you do not trace possible effects of possible placements along the loop, but rather you identify the loop’s existence, note the guardians and (hopefully) either immediately install a candidate or remove one or more. The shape is as easy to identify and use as the X-wing, and from its prevalence in Mr. Mepham’s “unsolvables” [three of them can be solved outright using this approach] I suspect it can be used to short-circuit a number of daily newspaper puzzles.

Here are a few examples of the technique in practice. [I apologize for the graphics. For a far better graphic presentation, I’d invite you to check the several threads on the “unsolvables” in the “Eureka” section of the discussions forum at sudoku.org.uk. All but the very first postings are supported by JPEG graphics]

The first is Mr. Mepham’s “unsolvable" number six at the point where standard techniques run out and a resort to bifurcation seems necessary. It is as “spectacular” a version of the "Broken Wing" technique in practice as there can be, since there is only one “guardian” cell preventing a perfect loop.

The five candidate cells for the number 7 forming a loop are marked with an X. There is only one “guardian” cell (marked with a G) preventing an impossibly-perfect conjugate pairing, at r2c1. Accordingly a 7 may immediately be installed there. As can be seen, there is no bifurcation in this approach, as we need not guess at all about the cells in the loop - we’re looking elsewhere. And even there we’re not guessing - we’re looking for one-step inevitabilities.

17 X |..2..|..9..||...6...|.17X.|..5..||..3..|..8..|..4
178G|..3..|.78.||..17..|...9...|..4..||..6..|..2..|..5
...5...|..6....4..||...8...|...3...|..2..||..7..|..1..|..9
- - - - - - - - - - - - - - - - - - - - - - - - - - - - -
...3...|..4..|..5..||...9...|...6...|..8..||..2..|..7..|..1
...6...|..7..|..2..||...3...|...4...|..1..||..9..|..5..|..8
...9...|..8..|..1..||...2...|...5...|..7..||..4..|..3..|..6
..48..|..5..|..6..||...4...|...2...|..3..||.18.|..9..|..7
- - - - - - - - - - - - - - - - - - - - - - - - - - - - -
47X..|..1..|..3..||.47X.|...8...|..9..||..5..|..6..|..2
...2...|..9..|.78.||...5...|.17X.|..6..||.18.|..4..|..3

A second example is perhaps more typical of the “Broken Wing” reasoning process is in Mr. Mepham’s “unsolvable” number three, below. The pattern of five candidate cells, coincidentally again for the number 7, is once more marked with X’s. This time there are two “guardian” cells at r2c1 and r9c9. We don’t know which of the two is “real” it could be that both are, but since both of them “see” the cells at r2c9, that cell may be eliminated as a 7, and that in turn means we can install a 7 at r1c7. That in itself doesn’t solve the puzzle, but it’s still a good illustration of the action of the “Broken Wing” technique and the ease with which it can be applied, at least for rings of 5 cells.

.279X.|...3...|..29..||..8..|..5..|..4..||.79X.|...1...|...6
.578G.|578X|...1...||..6..|..2..|..9..||...4...|...3...|578T
....4....|...6...|.579.||..3..|..7..|..1..||.589.|...59..|...2
- - -- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
...56...|...4...|...7...||..2..|..9..|..3..||..56..|...8... |...1
25689|.589.|2589||.45.|..1..|..7..||...3...|4569|..59
...59...|...1...|...3...||.45.|..8..|..6..||...2...|4579|.579
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
....1....|.589.|.589.||..7..|..3..|..2..||5689|.569.|...4
...57...|...2...|...6...||..9..|..4..|..8..||...1...|..57..|...3
....3....|789X|...4...||..1..|..6..|..5..||789X|...2...|789G

The pattern is extremely distinctive for five cells, since it always involves four boxes in a rectangle, three of them containing a single cell of the loop and the fourth holding a non-aligned pair. Finding the guardians is a matter of inspection from there; whether they yield any useful information depends on their number and location. Usually, two or three of the pairings must be conjugate for the guardians to eliminate a candidate cell, but that seems to happen surprisingly often.

There are numerous other examples of this “Broken Wing” technique for five cells in the eleven “unsolvable” puzzles posed by Mr. Mepham, and at least two for seven cells. Judging by that sample, I’d suggest that it will turn up in many other puzzles if it is looked for, and may be particularly useful if you’re trying to avoid “colouring” or “forcing chains”.

You must excuse me now: I have to go listen for the dog.

Rod Hagglund

[Jeff]

................ and may be particularly useful if you’re trying to avoid “colouring” or “forcing chains”.

Welcome RodHagglund, Is this an alternative way to deduce candidates using the turbot fish patterns? It isn't clear whether any of the 5 sides have to be conjugates.

Thanks in anticipation

[Carcul]

Hi RodHagglund.

In your first example (Mr. Mepham’s “unsolvable" number six ), we don't need any loop to solve the puzzle: the BUG principle allows us to put immediatly a "7" at r2c1. But, if we want to use a loop, a Turbot Fish eliminate a "7" from r8c1 and that solve the puzzle.
In your second example (Mr. Mepham’s “unsolvable” number three) we don't need the Broken Wing, the Guardian Cells and all that reasoning to place a "7" in r1c7. The loop

[r1c7]=7=[r9c7]-7-[r8c8]=7=[r8c1]-7-[r1c1]=7=[r1c7]

(which, al least for me, is much more simple to spot) allows immediatly to make r1c7 = 7.
So, can you show us an example where the Broken Wing can be more simple and usefull than already existing techniques?

Regards, Carcul

[Neunmalneun]

wouldn't it be easier to eliminate the 7 in r2c9 by using simple colouring?

[AndrewStuart]

I've implemented RodHagglund's guardians and they work very well. More later, but for the r1c7 number 7 insertion there is an even simpler method than the loop described above. A Y-Wing is present in these three cells:

r1c7 = 79 (A)
r3c8 = 59 (B)
r8c8 = 57 (C)

One of A and C must be a 7, they can both 'see' cell r9c7 and we can remove the 7 there. That leaves one 7 in the column at r1c7.

[AndrewStuart]

OK doubters, here is a challenge Sudoku. For me at least, this requires three seperate guardians at different stages to solve, intermixed with about 13 pointing pair candidate eliminations and 4 hidden pairs candidate eliminations. I use the broken wing/guardian strat as a last resort so in my world its required to solve this one. It starts of:

...2.39..
.5.4.7.8.
....6.4..
18......6
4...1...8
3......12
..8.3....
.4.6.9.3.
..35.2...

The first broken wing is number 1 which is removed from r8c7 - the cyan cell in the illustration. The white cells are the 5 corners of the Broken Wing:


The second one is number 6 in r7c1


And the third later on is number 7 in r6c4

[Jeff]

Hi AndrewStuart, I have visited your sites (nice effort ) and tried to learn the terms used to describe various techniques there. It is usually difficult to understand the terminologies which are not being used in this forum. I think it would be helpful to reference some of these terms here. Please correct me if I am wrong.

remote pair - naked pair linked by an xy-chain.
locked pair - naked pair in the same unit.
complementary pair - 2 cells that always have the same digit.
distance 1 - 1 link-edge of a naked pair
distance 2 - 2 link-edge of a complementary pair
distance 3 - 3 link-edge of a remote pair
y-wing - xy-wing

In your examples, I noticed that all edges are conjugates except for the units where the guardian cells are located. I am wondering why you would prefer to place a candidate in the guardian cell, rather than eliminate a candidate from or fix a candidate in one of the 5 nodes; using simple colouring or turbot fish. In doing so, you have limited yourself to a very special case of simple colouring or turbot.

In your last example:

Simple colouring implies r6c2<>7 and r6c5<>7, therefore the guardian cell r6c4=7.
Turbot fish implies r6c2<>7, r6c5<>7, r7c2=7 and r9c5=7, therefore the guardian cell r6c4=7.

I suggest you should program simple colouring and turbot fish (x-cycle even better) into your solver because they are much more versatile; do feel free to ignore of course.

[RodHagglund]

Wow: a lot of posts since I started this last night. Thank you for the interest.

First to Jeff: Yes, this is the same pattern the Turbot Fish operates from but is uses an entirely different principle as the basis for its conclusions, making it (I hope) as easy to spot and use, and as resistant to claims of bifurcation, as are the X-wing and Swordfish. In the most direct case, with only one guardian, it allows the logic to be collapsed to that of posting the number without any consideration of alternative possibiities. The Turbot Fish logic as I understand it is a subset of colouring and has been seen as a form of bifurcation. I should also add that the Turbot Fish shape only holds for loops of five cells, but the Broken Wing logic applies to larger loops as well, provided the number of cells is odd.

In terms of the conjugate pairs, it is easy to find cases where three of the conjugate pairs are broken up by guardians which yield a result - indeed, a single guardian placed at the "x-wing" point in the box holding the non-aligned pair will make three of the pairings non-conjugate. I can't conceive of a way in which the "Broken Wing" guardians can be configured to directly eliminate a candidate unless at least one of the pairings is conjugate, and I think all the ones I have actually found have at least two conjugate pairs (although if you entertain the thought of colouring or a forcing chain from one or more guardians I can't exclude the possibility that something interesting could be found even with all five pairs "guarded")

To Carcul:
Yes, in the number six example, since we have only one triplet cell left the BUG principle will allow you to figure out that one of the members of that cell can be placed, but of course that will be regarded as a bifurcation by the purists. In any case, this was only one example of the Broken Wing; in the second one I diagrammed you could not use BUG as I understand it. [I should add for those who care about such things that this approach does not rely in any way on the "uniqueness condition".]

And again to both Carcul and Neunmalneun:
In the second case I was not suggesting that colouring won't yield an answer (Carcul 's reasoning was a form of colouring). But in the "game" Mr. Mepham laid out, he was issuing a challenge to players to find solving methods (hopefuly simple ones) that do not resort to "what if" approaches and that might, like the X-wing, be eventually adopted by even the purists.

To AndrewStuart:
Thank you for the graphic examples. It has surprised me how often there is only one guardian for the entire pattern that can immediately be placed. I'd have thought that would be much more rare than it appears to be in practice. [Advice on how you met the requirements for posting decent graphics would also be much appreciated!]
Rod

[Jeff]

Hi Rod, Thank you for sharing your thoughts. I hope the following information is helpful.

The Turbot Fish logic as I understand it is a subset of colouring and has been seen as a form of bifurcation.

I supposed your so-called colouring is simple-colouring, consisting of all conjugate pair links. Turbot fish is not a subset of simple-colouring, because turbot fish considers non-conjugate links as well.

Simple colouring and turbot fish are not being seen as a form of bifurcation. They are just as pattern recognition-able as the broken wing.

I should also add that the Turbot Fish shape only holds for loops of five cells, but the Broken Wing logic applies to larger loops as well, provided the number of cells is odd.

It is true that turbot fish holds for loops of five cells only. However, more inclusions and exclusions are possible due to the consideration of non-conjugate links, which I am not clear yet with the broken wing. Refer example in my previous post.

You may like to know that turbot fish is a subset of 'x-cycle' which would cover loops of any length, repetitive or non-repetitve.

[RodHagglund]

Jeff: sorry for any confusion caused because my last posting crossed with one of yours. It was the wee small hours over here.
Just to get any issues of terminology aside:
What I call colouring corresponds with the definition found in the list of solving techniques on the Sad Man software site, and includes colouring (on one number) through both strongly-linked (conjugate) pairs and weakly-linked pairs, all of which, according to that source:
“is known as "simple colouring." There is also "multicolouring" or "supercolouring", a technique that makes deductions by combining the implications from conjugates of all candidates for all cells, although this technique is beyond the ability of most, if not all, human solvers.”
So what I call colouring certainly allows one to walk through non-conjugate links, provided you know what you’re doing. In the “Broken Wing” as far as I can see, although there is no colouring done; the entire process focuses on the non-conjugate pairs and specifically the cells that weaken their linkage.

As to the definition of bifurcation, there appear to me to be three broad schools on the subject. There are the purists who refer to anything requiring a thought process going beyond simple patterns as bifurcation; they seem to outlaw forcing chains, colouring and XY-wings among others. There are the pragmatists who feel that any rational reasoning process that leads to a definite conclusion about the entries in cells is fair game, including uniqueness, forcing chains, etc. but not including pure guesses, which are regarded as the only bifurcation; and there are the I-don’t-cares who want to answer the puzzle and don’t care if they have to guess. I’m in the second group: my remark was merely to the effect that the Turbot Fish approach seems not to meet the narrower view (and those were the rules I’ve been trying to follow with Mr.Mepham’s “unsolvables”)

As to the Turbot fish approach not being colouring, I’ll quote Nick70, who, as far as I know, invented the technique back in July: “It is a special case of coloring, or of double forcing chains, just like x-wing is.”{New Pattern: the Turbot fish, posted July 11, 2005}

As to the Turbot Fish being a pattern recognition: I agree that you can memorize and recognize each individual subpattern of conjugate pairs for the Turbot Fish separately and then argue you are just plugging in the answer, but I’d bet that the casual user merely sees the pattern and then “walks the chain” to get the answer.

I’m not at all suggesting that the “broken wing” approach is more powerful than the sum of Turbot Fish linkage patterns taken as a whole, but I will say that it’s simple, its pattern is a single one (at least at the 5-cell level) and easy to spot and the interaction of the guardians is easy to determine. For the “pencil and paper” crowd - and maybe even for those devising their puzzles - it may be a useful addition to their coterie of techniques.
Rod Hagglund

[Jeff]

Just to get any issues of terminology aside:.....

Rod, I can see your point. I am sorry for the confusion too. To my knowledge, there are 4 different types of colouring and the names overlap. That's why I wasn't sure which one you were referring to.

Type 1: colouring that considers bilocation conjugate pairs only, subset of type 2, 3 and 4.
Type 2: colouring that considers all x-cycles (turbot fish included), subset of type 3 and 4
Type 3: colouring that considers the combination of x-cycles and xy-chains
Type 4: colouring that considers grouped x-cycles.

Simple-colouring has an overlapped meaning for type 1 or anything other than type 3 and 4.
Multi-colouring has an overlapped meaning for type 2 or type 3.
Advanced-colouring means type 3
Super-colouring means type 3
Colouring has an overlapped meaning for type 1, 2, 3 and/or 4.

As you can see, colouring could mean anything and I had to make an assumption from the context. Thanks for the clarification that your so-called colouring is in fact x-cycles which include turbot fishes indeed. Perhaps I should refer type 1 as trivial-colouring in this post to avoid any further confusion.

As to the definition of bifurcation................

Bifurcation is simply a process. It should not be used to catagorise any solving techniques. Take forcing chain as an example. If a forcing chain is identified by testing each possibility in turn, then that is bifurcation. Forcing chains can also be identified without bifurcation too, making use of a bilocation/bivalue plot or advanced colouring table. Bifurcation is inevitable during the development or learning stage of a new technique when a proof has to be structured or understood. But, that's all. In routine puzzle solving, it is up to you to choose whether to bifurcate or not.

I agree that you can memorize and recognize each individual subpattern of conjugate pairs for the Turbot Fish separately and then argue you are just plugging in the answer, but I’d bet that the casual user merely sees the pattern and then “walks the chain” to get the answer.

This statement puzzles me. It sound like that you agree that turbot fishing can be done by pattern recognition, but the majority would choose to bifurcate instead. Why would anyone choose to do it the hard way?

I’m not at all suggesting that the “broken wing” approach is more powerful than the sum of Turbot Fish linkage patterns taken as a whole, but I will say that it’s simple, its pattern is a single one (at least at the 5-cell level) and easy to spot and the interaction of the guardians is easy to determine. For the “pencil and paper” crowd - and maybe even for those devising their puzzles - it may be a useful addition to their coterie of techniques.

Totally agreed. My problem is that trivial-colouring is always an easier technique to apply than turbot fish. Then, why should a turbot fish pattern be identified in order to get a trivial-colouring deduction. Of course, it makes sense when the broken wing is considered as just another simple pattern like the good old x-wing. Have fun.

[RodHagglund]

Jeff: I think actually we see eye to eye. Your last sentence more or less sums up where I'd see the Broken Wing fitting in. As to bifurcation, I'll gladly let the Mephams and Goulds of the world devise and defend their own definitions. Even so, it made a fun challenge to attack Mr. Mepham's eleven on narrow terms.
Cheers,
Rod

[AndrewStuart]

Hi Jeff. regards your comments on my guide
a) thanks!
b) I'm overhauling solvers/graders/docs this week in the light of what I consider to be a greater consensus here, than, for example, my email inbox, in naming things. The intermediate docs state probably have a mixture of terms now which I'll be trying to stamp out.

c) regarding the 'guardian' example, I posted before I took a proper look at Turbo fish - so apologies if you've all seen it before. What got my pants on fire (ie excited) were the extensions of this strat, which I'll try and post later. But I'll do some more reading/testing first.

[RodHagglund]

Another effort at showing interesting results for the guardians strategy. Here's a sudoku I saw recently elsewhere on this site - regret I couldn't locate it again to reference, but below is the image of the point where the guardians wipe out a series of entries for the candidate number 2 and reveal a naked single.



Here the choice of the fourth and fifth points (in box three) to complete the shape can be done in any of four ways, but the result is the same after two passes. The two points chosen here are r2c9 and r3c8. Since all guardians, marked in amber, are in the same box, the number 2 is eliminated from r2c9 and r3c8. The exact same process can now be applied with r3c7 and r1c9. that eliminates all 2's on r3 and c9 in that box, making r6c9 a naked single.

The sudoku is solvable without resort to this approach, but there is to me something simple and elegant in the logic.
Rod

[Jeff]

but below is the image of the point where the guardians wipe out a series of entries for the candidate number 2 and reveal a naked single.

Happy New Year, Rod, I checked the deductions using x-cycle and found that they are not valid. Can you check them again? I could be wrong.