The New Sudoku Players' Forum

[DonM]

...All I see in Phil's forcing chain is a candidate with two chains/streams leading to contradicting conclusions on another candidate.

Code: Select all

(6)r3c7 - (6=2)r3c4 - (2=4)r2c5 - (4=9)r8c5 - r8c2
(6)r3c7 - (6=2)r1c9 - (2=6)r1c2 - (6=9)r8c2
therefore r3c7 <> 6; stte


If he had just one chain/stream for 6r3c7 leading to a contradiction, then I would consider it bifurcation -- with the implication that 9r3c7 must be true. For example:

Code: Select all

(6*)r3c7 - (6=2)r3c4 - (2=4)r2c5 - (4=9)r8c5 - (9=6)r8c2 - (6=2)r1c2 - (*62)r1c9; contradiction


_

I suppose, somewhere very early back in the day, the term 'bifurcation' as applied to sudoku was given a more narrow, specific definition. This was particularly true in 2005 when there were relatively few techniques for what were then considered more difficult puzzles so you had Nishio, Ariadne's Thread and so on. But bifurcation eventually became a broader, more generic term, applying to any form of 'forking'. For instance, one bifurcation definition now given is as general as: By solving with the assumption of a value, any conflicts invalidates that guess.

For several years at the UK Forum, there was one section used by the 'bifurcators' and they used various forms of 'forking'. As I see it, in the solution used by pjb, 6r3c7 is assumed and one path is followed to r8c2, then starting again with 6r3c7 another path is followed to r8c2 ie. forking ergo bifurcation.

[David P Bird]

What follows is an extract of some work in progress of mine about AICs and patterns:

Acceptability Issues

Everyone accepts that bifurcation is the process of following different branches in the solution process but beyond that there are differences of opinion about what following measures are taken. Where one branch is eliminated because it produces a contradiction it can be classed as guessing, whereas if both branches still appear viable and further forks are followed it becomes a network, 'brute force' approach.

To demonstrate than an AIC doesn't amount to bifurcation, take the case where an AIC starts with a strong-only link from a UR pattern. Here at least one of the two disrupting nodes must be true but possibly both are. Candidates that can't be true regardless of which case it is can then be eliminated, but no guess has been made. However, as previously noted, most strong links are conjugate which can make it appear as an unacceptable piece of bifurcation, but in following the AIC protocol there is no need to make any assumption whatsoever.

Next consider when a strongly linked candidate in a chain produces separate chain segments that both start with weak links as shown here:

Code: Select all

      /(c=d) – (e=f) -         (p) \
(a=b)                               = (r) – (x=y)   
      \(g=h) – (i=j) – (k=l) – (q) /

In this case (pqr) are candidates in the same cell (a kraken node that has three possible truth states). If (b) is true, both (p) and (q) will be false and so (r) must be true. If (r) is false, either (p) or (q) must be true, and whichever one it is, reading the corresponding segment backwards shows (b) must also be false. Hence (b) and (r) are equivalent and will be true and false together, and in turn (a) and (y) can't both be false together.

It's clear that the chain has forked (or bifurcated) into two branches of different lengths that happen to converge later on. To track these different paths, one must be suspended while the other is explored and the chain ceases to be a pure AIC – it's the thin end of a wedge indicating a network approach is being used. Effectively it explores multiple cases and so ceases to be an AIC.

The only way a pure AIC can bifurcate is within a recognised pattern that provides a derived inference. Here the concept is that the pattern involved is easily recognised (without needing to track any logic) and occurs frequently enough to make it worth remembering. Although many simple patterns such as wings are just short AIC segments, some such as the deadly ones, need deeper analysis to prove.

- - -

Of course this then raises the question about which patterns are generally considered acceptable, but that's another topic!

[eleven]

After all is said and done
Gotta move while it's still fun
Let me walk before they make me run
Keith Richards

[blue]

_

Bifurcation

A limited form of Trial & Error where only constraints with 2 remaining candidates are considered.

When there are only 2 candidates left for a constraint, one of them must be true and the other must be false. In bifurcation, both branches of the fork are tried by placing the candidate in its cell and solving the puzzle from that point forward. When a contradiction is found, the remaining candidate can be placed.

Bifurcation has a bad reputation in the Sudoku community because it relies on backtracking and looks similar to guessing. Many advanced solving techniques were introduced to reduce the need for bifurcation.

This is just a guess, but I imagine that AICs are one of the "advanced solving techniques" referred to in the section in blue.

"Kraken cells" with simple AIC's linking candidates in the cell to the elimination target, are probably a better example. They can be presented in that format, with Kraken cell options on the left, and an elimination target in on the right. On the other hand, a presentation like that, can be flipped left to right, to show that assuming that the candidate to be eliminated is true, leads to a conflict in which no digit can be placed in the Kraken cell. I think that DonM (in the end), would be suggesting that one view is deserving of the the "bifurication" label, and the other isn't -- even though both presentations seem to involve some kind of "forking", and they use virtually the same diagram.

Also, I think that the focus on "forking" here, has been a little bit misguided ... including in DonM's 2nd post. I got caught up in it myself, for a while. In the end, it seems that the only "fork" that's relevant, in the more refined definition of bifurication that Don presented, is the one in which the options are "the elimination target is true" and "the elimination target is false". Interestingly enough (!), in that "fork", one branch has absolutely nothing to do with justifying the elimination.

Regards,
Blue.

[DonM]

Also, I think that the focus on "forking" here, has been a little bit misguided ... including in DonM's 2nd post. I got caught up in it myself, for a while. In the end, it seems that the only "fork" that's relevant, in the more refined definition of bifurication that Don presented, is the one in which the options are "the elimination target is true" and "the elimination target is false". Interestingly enough (!), in that "fork", one branch has absolutely nothing to do with justifying the elimination.

I'm not following. How can the elimination be justified without the information from both branches?

[blue]

I'm not following. How can the elimination be justified without the information from both branches?

One branch leads to a conflict/contradiction, and justifies the elimination.
The other branch is a step along the way to a solution (assuming one exists).

The one that leads to conflict, is likely to have downstream branches of its own.
Depending on the complexity, it could have both forks and and merges.

Did I misread your intent ?

[DonM]

I'm not following. How can the elimination be justified without the information from both branches?

One branch leads to a conflict/contradiction, and justifies the elimination.
The other branch is a step along the way to a solution (assuming one exists).

The one that leads to conflict, is likely to have downstream branches of its own.
Depending on the complexity, it could have both forks and and merges.

Did I misread your intent ?

I think so. I only mentioned that definition of bifurcation as an indication of how broad the term 'bifurcation' has become as opposed to the narrower one given by Daj. I did not intend it as a definition that I was putting forward to make any other point.

My only point was that, by present standards, the method used by pjb whereby you start with an assumption of a value in a given cell, follow 2 different paths from it to a target cell and get a conflict is forking/bifurcation.

[Luke]

While interesting, I see the bifurcation discussion as secondary to what is really going on here. It's brutally simple to me.

In a relatively easy puzzle, if one looks at a cell with only two candidates and then assumes the false value is true, it won't take very long to run into a snag.

I've never seen anyone take down a hard puzzle with this process, so why would we be interested in seeing it done to a fun little daily?

[David P Bird]

Knock-about football without any off-side rule is fine for those that enjoy it. However steadfastly refusing to try to understand its reasons and workings can lead to some nonsensical discussions when shooting from the lip. (Mexico v Cameroon)