The New Sudoku Players' Forum

[apatt]

Hi!
I have an incomplete understanding of the Forcing Chain concept. As far as I can understand it the idea goes something like this (please correct me if I'm wrong):

1) Select a cell with only 2 candidates (any such cell?)
2) Mark current position
3) Pick one candidate as the solved number, follow the chain of forced numbers in other cells caused by this decision.
4) Go back to the marked position, pick the alternative candidate, follow the alternate chain of forced numbers in other cells caused by this decision.
5) Go back to the marked position.

The whole point (as I understand it) is to find a common number on these 2 chains, and this common number is now solved.

What I don't understand is:
1) How far do you follow these chains? Until there are no more forced numbers?
2) How do you know when you have found this number, by comparing the alternate chains?
3) On these chains do you ignore all cells which contain more than 2 candidates?

Thanks.

[Hakosuuji]

Hi,

Although I usually let my computer program do the work , I do have some tips regarding forcing chains:

1. For each value, keep track of:
(a) how many times you filled in the value
(b) how many cells allow that value (after using all other techniques)
2. Check the ratio free cells / remaining to fill

When the ratio is:
2 to 1: filling in one of the values will determine all remaining spots.
(2 to 1) + 1: good candidate, also for trial & error. the surplus spot may cause an easily detectable conflict.
(2 to 1) + 2: still OK, but less reliable
higher: forget it. the chain will probably die very soon

Now you've determined what value to attack, you need to know where to start. Find a cell that allows that value + one other value, preferably a value that also has a good ratio. When the original ratio is exactly 2 to 1, it does not matter where you start, since you will be able to fill in all remaining values anyhow.

Work on a value-by-value basis:
1. Do the effects for the value you entered;
2. Do the effects for the complementary value;
3. Now try the other value and do the effects for both values
4. Compare results

When that does not yield a result, do effects for other affected values, and check again.
Still stuck? Try another candidate.

Another useful ratio is the number of other candidates sharing possible locations for a value. The closer that ratio approximates 2 to 1, the stronger the forcing chain will be. Using a computer program to keep track of these ratios is recommended.

[tso]

Hi!
I have an incomplete understanding of the Forcing Chain concept.

"Forcing Chains" includes more than one type of pattern. It is important to note that the patterns and the methods to *find* the patterns are two different things.

One type of forcing chain has more recently been renamed the xy-chain. This is the type of chain that uses exclusively cells that have only two candidates each, though the cell in which the exclusion is made may have any number of candidates. The simplest possible (in a standard Sudoku) is:

(I)

Code: Select all

[12][13]
[23][34]


Either possibility in [12] excludes the 3 from [34].

Assuming these four cells are r34c34, the forcing chains could be written:

r3c3=1 => r3c4=3 => r4c4=4
r3c3=2 => r4c3=3 => r4c4=4
Therefore, r4c4=4

A slightly different possiblity:

(II)

Code: Select all

[12][13]
[23][34567]


r3c3=1 => r3c4=3 => r4c4<>3
r3c3=2 => r4c3=3 => r4c4<>3
Therefore, r4c4<>3


Depending on the specific situation, these, and longer chains can be found by several evolving methods. One method is to connect all the 2-candidate cells that are in the same row, column or box with lines if they share at least one candidate. (Eppstein would call this a "bi-value graph". See [url=http://arxiv.org/abs/cs.DS/0507053]

Nonrepetitive Paths and Cycles in Graphs with Application to Sudoku[/url]) Label all the lines with the digit (or digits) that the two cells share. Then look for loops that have a single pair of repeated digits. You can excluded the candidate that repeats. In our example above, it would come out like this:

Code: Select all

[12]--1--[13]
 |         |
 2         3
 |         |
[23]--3--[34]


This situation is nearly the same but might be harder to spot with this method:

Code: Select all

[12]--1--[13]
 |         
 2         
 |         
[23]     [34567]


Non-repeating loops can also lead to exclusions in cells outside the chain:

(III)

Code: Select all

[12]--2--[23]------[1234]
 |         |
 1         3
 |         |
[14]--4--[34]


In this case, no exclusion is made within the chain, but you may exclude the "2" from [1234].

Sometimes this method may work very quickly to find chains -- other times you may get a tangle of lines.

Another method is identifying the BINARY GROUPS, which will often require fewer lines to be drawn. These to methods can often be used together to better effect. The threads below contain examples of the Binary Group method:

http://forum.enjoysudoku.com/viewtopic.php?t=1193&postdays=0&postorder=asc&start=15
http://forum.enjoysudoku.com/viewtopic.php?t=1162
http://forum.enjoysudoku.com/viewtopic.php?t=1246
http://forum.enjoysudoku.com/viewtopic.php?p=7100
http://forum.enjoysudoku.com/viewtopic.php?t=1360

Another type of forcing chain uses connections in which each pair of cells are the only two in that row, column or box that contain a specific candidate. The cells are NOT limited to 2 candidates each. Eppstein refers to graphs made with these cells as "bi-location graphs". Chains like these are related to x-wings, swordfish and coloring.


You can also combine the two types of links in a single chain. There will be a greater possibility that a forcing chain will exist if you include both types of links together, that doesn't imply there is an obvious way to find them.

[stuartn]

Here's a nice example from Pauls Outlaw grids..

Code: Select all

..1..6..5
.2....7..
.4.9.....
..8.3.2..
..5..16..
..7...9..
.....5.4.
..3....8.
8..2..3..


Using the basics it becomes this....

Code: Select all

381726495
5291487 [36]  [36]
746953821
 [1469]  [169] 8 [45] 3 [79] 2 [15]  [47]
2 [39] 5 [48]  [79] 16 [37]  [3478]
 [1246]  [136] 7 [458] 629 [15]  [348]
 [69]  [679] 238514 [79]
 [169]  [1679] 3 [46]  [79]  [479] 582
85421 [79] 3 [67]  [679]


R2C8 = 3 =>R5C8 =7 => R5C5 = 9
R2C8 = 6 =>R9C8 =7 => R9C6 = 9 =>R8C5 = 7 => R5C5 = 9

Either route, R5C5 is FORCED to be 9.

For interests sake, I identified the chains by simply running an alpha sorted log of the cell changes when I'd input the 3 and 6 in R2C8. On comparing the two logs, any single cell that is reduced to an identical single value in both logs must be at the end of a forcing chain starting at the cell I changed. It's then just a question of following the route(s) back.

The Excel sheet I use is at http://www.brightonandhove.org/Sudolinks.htm

stuartn

[r.e.s.]

One type of forcing chain has more recently been renamed the xy-chain. This is the type of chain that uses exclusively cells that have only two candidates each, though the cell in which the exclusion is made may have any number of candidates. The simplest possible (in a standard Sudoku) is:

(I)

Code: Select all

[12][13]
[23][34]


Isn't exclusion by a naked pair an even simpler xy-chain? ...

Code: Select all

   [ab]
   / |
[xa] |
   \ |
   [ab]

Instead of a graph with undirected edges whose nodes are cells, it would seem a useful variation to use directed edges whose nodes are individual digits. Consider this example, which I happen to have handy ...

Code: Select all

+-------+-------+-------+
| . . 1 | 9 . . | . . 8 |
| 6 . . | . 8 5 | . 3 . |
| . . 7 | . 6 . | 1 . . |
+-------+-------+-------+
| . 3 4 | . 9 . | . . . |
| . . . | 5 . 4 | . . . |
| . . . | . 1 . | 4 2 . |
+-------+-------+-------+
| . . 5 | . 7 . | 9 . . |
| . 1 . | 8 4 . | . . 7 |
| 7 . . | . . 9 | 2 . . |
+-------+-------+-------+

After a few simple moves, we can draw the following graph, which I've called a "forcing net" for lack of a better term. The graph shows that no '8' in box 7 can be correct unless r5c5 = 3:


[2005/09/19: Edited to show how a forcing net can be drawn to have two uniquely identifiable nodes -- one node is the "starting digit" and the other is the "final digit". The starting digit is the only node with no arrows pointing to it, and the final node is the only node with both types of arrow pointing to it.]

[2007/04/05: Updated link address.]
[2007/05/20: Thanks to Bill Richter for pointing out an error in the above net: the '5' in r1c2 is not properly taken into account. I will leave it as-is, hoping that the intended logic can still be discerned.]

The graph is based on the following two types of implication pattern, one of which is "one to possibly-many" and the other is "possibly-many to one". (The notation is such that "NOT a" means "digit 'a' is incorrect for its cell", etc.)


[2007/04/05/: Updated link address.]

If I'm not mistaken, a forcing chain is a special kind of forcing net; specifically, when all the component patterns are "one-to-one", these graphs can be reduced to the kind with undirected edges (but cannot be so reduced otherwise).

[Jeff]

Nice diagram, r.e.s.

Can you shed more light on:

Why the starting cell r5c5 is chosen?
What trigger the '2' to be picked to start the forcing implications?
What would happen if '3' is chosen instead?
How do I know this particular contradiction and therefore concentrate on the 8s in box 7?
How do I apply this technique to another puzzle; is there a specific pattern to follow?

Thanks in anticipation.

[tso]

One type of forcing chain has more recently been renamed the xy-chain. This is the type of chain that uses exclusively cells that have only two candidates each, though the cell in which the exclusion is made may have any number of candidates. The simplest possible (in a standard Sudoku) is:

(I)

Code: Select all

[12][13]
[23][34]


Isn't exclusion by a naked pair an even simpler xy-chain? ...

Code: Select all

   [ab]
   / |
[xa] |
   \ |
   [ab]

Technically yes, but then "four of a kind" could be rightly called "two pair". I think it is implied that a forcing chain refers to patterns that are not also something more basic. Also, naked pairs, trips, etc. work only when all cells are in the same group (row, column or box). To me, this is one of the lines that separate the levels of complexity of logic.

A shorter xy-chain is possible if diagonal groups are in force:

Code: Select all

 .  .  .  |  .  .  .  |  .  .  . 
 .  .  .  |  .  .  .  |  .  .  . 
 .  .  .  |  .  .  .  |  .  .  . 
 ---------+-----------+--------- 
 .  .  .  |  .  .  .  |  .  .  . 
 .  .  .  |  . ab  .  |  .  .  . 
 .  .  .  |  .  .  .  |  .  .  . 
 ---------+-----------+--------- 
 .  .  .  |  .  .  .  |  .  .  . 
 . ab  .  |  . xa  .  |  .  .  . 
 .  .  .  |  .  .  .  |  .  .  . 


In this case, though the [ab][ab] still form a naked pair -- that pair only acts on the other cells within the diagonal they lie in. The exculsion from [xa] is from by xy-chain.

[r.e.s.]

Nice diagram, r.e.s.

Thanks ... I've edited the picture to illustrate how a forcing net can be drawn to have two uniquely identifiable nodes -- one node is the "starting digit" and the other is the "final digit". The starting digit is the only node with no arrows pointing to it, and the final node is the only node with both types of arrow pointing to it .

Can you shed more light on:

Why the starting cell r5c5 is chosen?
What trigger the '2' to be picked to start the forcing implications?
What would happen if '3' is chosen instead?
How do I know this particular contradiction and therefore concentrate on the 8s in box 7?
How do I apply this technique to another puzzle; is there a specific pattern to follow?

Thanks in anticipation.

I appreciate the smiley. I'll try to give concise answers ...
Since a forcing net is essentially just a graphic representation of a specific contradiction implied by the starting digit (forcing that digit's elimination), these nets allow the systematic elimination of incorrect candidates by examining any or each candidate in the grid as possibly being the starting digit of a forcing net. (This seems to involve the same kind of "search-T&E" involved in examining digits as possibly forming one of an arsenal of basic "solving-patterns".) That, in principle, if not in practice, is how a human could discover the nice starting digit '2' in r5c5. But of course that would be infeasible for a computerless human, and indeed I used software to look for a cell with only two digits such that one of them leads to an easy solution by only simple moves, and the other digit (as determined by hand) leads to a forcing net. And of course there was no looking for a specific final digit, since any would do.

Actually, this suggests a kind of challenge; namely, to find an "optimum cell" such that
(1) one digit leads to the solution using naked- & hidden-singles only, and
(2) all other digits in the cell lead to forcing nets whose combined number of nodes is less than for any other cell satisfying (1).

In a sense the challenge amounts to seeking the "most elegant" set of contradictions inherent in a given sudoku puzzle. (I think the above example is an optimum cell, whose single forcing net has 27 nodes. The worst I've seen so far in other puzzles seemed to require about 50 nodes.)

One thing I'd like to ask those who consider "elimination by contradiction" (e.g. forcing nets) to be unacceptable ... Suppose you've just begun pencilling-in candidates, and the first five cells you complete are as follows:

Code: Select all

          |
   12  23 | 234
       35 |  45
----------+----------


Is there no candidate that you would eliminate (by logic alone) at this stage, given that the blank cells have as-yet-undetermined candidates?

Isn't exclusion by a naked pair an even simpler xy-chain? ...

Code: Select all

   [ab]
   / |
[xa] |
   \ |
   [ab]

[...]I think it is implied that a forcing chain refers to patterns that are not also something more basic.

That usage would be a poor one, imo. If a pattern is a forcing chain, then surely it is correct to call it that, whatever else it might also be.

[Jeff]

One thing I'd like to ask those who consider "elimination by contradiction" (e.g. forcing nets) to be unacceptable ... Suppose you've just begun pencilling-in candidates, and the first five cells you complete are as follows:

Code: Select all

          |
   12  23 | 234
       35 |  45
----------+----------


Is there no candidate that you would eliminate (by logic alone) at this stage, given that the blank cells have as-yet-undetermined candidates?

r.e.s., Thank you for your detailed explanation. To answer your question, elimination by contradiction is totally acceptable and totally logical. Usually, the problem is how to identify such contradiction. With your example, I think the mojority including myself would have to go through a brief T&E process on a few pairs before realising that the 1 can be singled out; and this was done with the related cells isolated also. Imagine these cells are hidden amongst the others. So, what we need is a pattern, pattern that allows us and others to recognise such contradictions, like the x-wing, swordfish, turbot fish, xy-chain and xyz-wing that we have been using. I bet no one will ever question the acceptability of these methods because they all have recognisable patterns. Once these patterns are learnt, (proven and understood). they becomes non-T&E. xyz-wings are very similar to your example. But, because xyz-wings have fixed patterns to follow, they are much easier to be found. Since their logic have been understood, no bifurcation is needed at all.

[r.e.s.]

[...] elimination by contradiction is totally acceptable and totally logical. Usually, the problem is how to identify such contradiction. [...] what we need is a pattern, pattern that allows us and others to recognise such contradictions, like the x-wing, swordfish, turbot fish, xy-chain and xyz-wing that we have been using. [...] Once these patterns are learnt, (proven and understood). they becomes non-T&E. xyz-wings are very similar to your example. But, because xyz-wings have fixed patterns to follow, they are much easier to be found. [...]

It seems to me that the usual "accepted" patterns are just a handful that happen to be especially recognisable -- but there are many that are only a tad less recognisable. E.g., suppose the '234' had instead been '24', i.e.

Code: Select all

          |
   12  23 |  24
       35 |  45
----------+----------

instead of

          |
   12  23 | 234
       35 |  45
----------+----------


It isn't clear to me why the forcing net (a *chain*) contained in the first snippet would be considered an acceptable "target pattern", but not so for the forcing net in the second snippet. With respect to "recognisability" of these two patterns, their difference seems only a matter of (small) degree.

[stuartn]

Jeff wrote:

Once these patterns are learnt, (proven and understood). they become non-T&E

Patterns or rules?... are they the same thing?.. If we know that blocks, columns and rows all have 1 to 9 etc does that make T&E justifiable within the bounds of solving the grid? (based on the above quote)

stuartn (devils advocate for today)

[Jeff]

It isn't clear to me why the forcing net (a *chain*) contained in the first snippet would be considered an acceptable "target pattern", but not so for the forcing net in the second snippet. With respect to "recognisability" of these two patterns, their difference seems only a matter of (small) degree.

I said the elimination by contradiction approach is totally acceptable, not the recognition of the first snippet in question. With recognition of any forcing chains or nets, each individual has different level of acceptability. To remove the slightest doubts, apart from just showing the solution, you need to describe a systematic way of how the solution was found. Simply saying 'it's quite obvious', 'it's all in front of you', 'by experience', 'with practice' or 'if you examine each cell', are not sufficient and usually unsatisfactory. What appears to be one's map could be seen as a bowl of spaghetti for others. For example, the xy-wing and the 3 members of xyz-wings differ only by a small degree, but they weren't discovered all at the same time. Of course it all seems so logical and straight forward once they were described. Double implication forcing chains used to have the same shortcoming in terms of recognition, but now they can be identified via patterns. People find the 'elimination by contradiction' process unacceptable simply because they don't possess abilities like yours to identify them easily. I congratulate you in this respect.

[Jeff]

If we know that blocks, columns and rows all have 1 to 9 etc does that make T&E justifiable within the bounds of solving the grid?

Knowing the structure of the solution doesn't make T&E justifiable. We all know that any grids can be solved by T&E, but is this satisfactory? The question: 'What is the next logical step? is often asked, usually with the definition of his/her 'logical step' omitted. To me, 'logical step' means a step that can fix or remove a candidate without trial and error, and such step can be applied equally without T&E in another grid. If you post a triple implication chain as the next logical step, even with a proof, what make you think that this is logical to the readers without an explanation of how it is identified. This most acceptable means of identification is pattern recognition.

[r.e.s.]

It isn't clear to me why the forcing net (a *chain*) contained in the first snippet would be considered an acceptable "target pattern", but not so for the forcing net in the second snippet. With respect to "recognisability" of these two patterns, their difference seems only a matter of (small) degree.

I said the elimination by contradiction approach is totally acceptable, not the recognition of the first snippet in question. [...]

Actually, you did say that ...

what we need is a pattern, pattern that allows us and others to recognise such contradictions, like the [...] xy-chain [...]

In fact, that's what prompted my reply -- the first snippet contains an xy-chain, and the second contains a net only very slightly harder to recognise. Solely wrt recognisability, surely the patterns in these two snippets are not radically different?

apart from just showing the solution, you need to describe a systematic way of how the solution was found. Simply saying 'it's quite obvious', 'it's all in front of you', 'by experience', 'with practice' or 'if you examine each cell', are not sufficient and usually unsatisfactory.

Well, I've said none of those things except the last -- that in principle, if not in practice, every candidate digit in the grid can be examined as possibly starting a forcing net -- and I remarked that that would not be feasible for a computerless human. Such an algorithm is certainly systematic, even if it is unacceptable on other grounds.

[Jeff]

.....the first snippet contains an xy-chain, and the second contains a net only very slightly harder to recognise. Solely wrt recognisability, surely the patterns in these two snippets are not radically different?

Sorry, I missed the xy-chain in the first snippet. How does it go? The chain I found is as follows:

r3c4=4 => r2c4=23 which forms a naked pair with r2c3 => r2c2=1
r3c4=5 => r3c3=3 => r2c3=2 => r2c2=1

apart from just showing the solution, you need to describe a systematic way of how the solution was found. Simply saying 'it's quite obvious', 'it's all in front of you', 'by experience', 'with practice' or 'if you examine each cell', are not sufficient and usually unsatisfactory.

Well, I've said none of those things ...............

Of course you didn't say any of these things. I listed these reponses that I have read from other posts to clarify the poor acceptability if solutions were to be presented for the 2 snippets without patterns of identification. Apparently, my clarification wasn't clear at all. I beg your pardon.