SudokuWiki
SudokuWiki.org
Strategies for Popular Number Puzzles

Digit Forcing Chains

This is the start of a family of strategies called Forcing Chains. As the name implies they are made from chains - or formally - Alternating Inference Chains which are simple ON - OFF- ON - OFF consequences. Chains can start with an ON or an OFF. When a candidate X it turned 'on' it immediately turns 'off' all other candidates it can see. When a candidate is in the 'off' state it might turn on another candidate if there is only one left in the unit it can see.

In the strategy Forcing Chains we look at the consequences of a candidate being first ON and then OFF, or a group of candidates in a cell being ON (Cell Forcing Chains) or a number being ON in all instances in a unit (Unit Forcing Chains). If the consequences of the chains are identical - that another candidate is always ON or always OFF - then we have a contradiction.


Family of Digit Forcing Chains
Family of Digit Forcing Chains
Before we look at specific examples, its worth going over the different types of attack in this family. In this diagram the starting cell is on the left - and an 8 is chosen. It is attacking either another digit (first two rows), a cell (middle two rows) or a unit (last two rows). In each attack the ends of the two chains are either ON or OFF.

If the two ends of the chain meet on the same digit, the we can remove that digit if the ends are OFF, or it's the solution to that cell if the chain ends are both ON.

Likewise, we can attack a whole cell by finding two ON or OFF digits. If OFF, then the last remaining candidate is the solution - but this only works if there are 3 candidates in the whole cell. If ON, then we know that one of those two ON cells is the solution, so any other candidates can be removed.

And finally, the unit attack, based on the same number appearing three or more times in that unit. You will see the pattern now. If we can find two numbers that the chain ends say must be ON, then one of them is the solution and the rest of that number X can be removed from the unit. If there are three numbers left and we identify two numbers that are off, then the last candidate is the solution.

Figure 1: Digit Forcing Chain
Figure 1: Digit Forcing Chain : Load Example or : From the Start
In this article we have a very tough Sudoku which contains a neat series of Digit Forcing Chains showing several different consequences. The first is given in Figure 1.

The 'digit' in this strategy is a single candidate - in this case the 5 in J9. We are looking at the consequences of this 5 being ON or OFF. Following the blue chain where 5 is OFF we get to the cell E1 where the consequence of 5 being OFF is to turn 6 ON. This chain is (the blue chain):
-5[J9]+5[H9]-5[H5]+5[E5]-5[E4]+8[E4]
-8[B4]+8[B1]-6[B1]+6[E1]


Now, if the 5 in J9 were ON we can trace another shorter chain to E9 were we also find the a 6 can be turned ON. The chain for this is (the purple chain):
+5[J9]-2[J9]+2[C9]-6[C9]+6[E9]
So whether J9 is 5 or not, we know 6 will appear in row E in E1 or E9, so the other 6s in E2 and E8 can be removed.
Figure 2: Second Digit Forcing Chain
Figure 2: Second Digit Forcing Chain : Load Example or : From the Start

In the very next step we are obliged to find another Digit Forcing Chain this time centered on 8 in E4. Like the first example it finds that either way the 8 in E2 will give us a 5 either on H5 (the blue chain) or a 5 on H9. This either/or situation establishes 5 in one of those two cells so the remaining 5 in H2 can be removed.
The blue chain is:
-8[E4]+5[E4]-5[E5]+5[H5]
The purple chain +8[E4]-8[B4]+8[B1]-6[B1]+6[E1]
-6[E9]+4{E9|A9}-4[H9]+5[H9]
contains an awkward ALS on
{E9|A9} - not easy to spot. The chain goes into the cell E9 and turns OFF the 6 which leaves just a Naked Pair of 4/9 in A9 and H9. That in turn removes the 4 in H9 giving us the second fixed 5 in H9.

Digit to Unit attack

Figure 3: Third Digit Forcing Chain
Figure 3: Third Digit Forcing Chain
Lastly in this Sudoku we find one of the more common types of Digit Forcing Chain, one that fixes a digit in another cell. E6 is the start cell 8 is the digit we are flipping ON or OFF. If OFF we take the blue chain around the board to H2 where 1 gets turned ON. This chain is:
-8[E6]+8[E4]-8[B4]+8[B1]-6[B1]
+6[B2]-6[D2]+4[D2]-4[H2]+1[H2]

The consequence of 8 in E6 being ON also shows that 1 in H2 must be ON as well. The second, purple chain is +8[E6]-3[E6]+3[H6]-1[H6]+1[H2].
So, whether E6 is 8 or not the chains imply H2 must be 1 and that opens up the puzzle to the end game.


Second Example

Digit Forcing Chains aim at a Unit
Digit Forcing Chains aim at a Unit : Load Example or : From the Start
Careful traversing of two chains might result in the chain ends resting on the same digit in the same row, column or box. The example here starts on G9 and winds it's way round to the 1s on row D. If the 5 in G9 is ON we get a result of 1 on D7. If the 5 in G9 is OFF we get a 1 on D1. Therefore, there cannot be any other 1s on that row. Three other 1s eliminated is a bit hit at this stage of the puzzle. The solver will return:

DIGIT FORCING CHAIN: because of G9, 1s in Row 4 are fixed on [D1,D7]
-5[G9]+5[F9]-5[F1]+5[C1]
  -4[C1]+4[B1]-1[B1]+1[D1]
+5[G9]-5[G7]+2[G7]-2[D7]+1[D7]
we can remove 1 from D2
we can remove 1 from D8
we can remove 1 from D9
Second Digit to Unit Forcing Chain
Second Digit to Unit Forcing Chain : Load Example or : From the Start

But it doesn't end there. The very next step uses the new chain link made available by clearing those 1s away. With two 1s on row D we get a new conjugate pair and can extend the longer chain by one more link. This allows us to fix the 2s in column 7, giving us an elimination of 2 in H7.

DIGIT FORCING CHAIN: because of G9, 2s in Col 7 are fixed on [D7,G7]
-5[G9]+5[F9]-5[F1]+5[C1]-4[C1]
  +4[B1]-1[B1]+1[D1]-1[D7]+2[D7]
+5[G9]-5[G7]+2[G7]
we can remove 2 from H7



Comments

Comments
Talk

... by: Buzz

Saturday 30-Jan-2016
DFC strategy is great-- but why not use Digit Forcing Nets--

Is it cheating? It is easy and solves many late stage puzzles--almost makes using it boring!

I turn on a single digit in a bivalve cell with a single color-- and go through the forced consequences --using green as on and pink as off

If the digit you chose to start with is "wrong" --in no time you will start seeing impossibilities--mostly NISHIO TYPES-- and what you know is that the other digit is the correct solution--

On the other hand-- if you randomly chose the "correct" digit as a solution-- then no contradictions occur and all of those colors are correct throughout the entire puzzle--solves in no time flat!

Why not publish this method--cheating, guessing,
REPLY TO THIS POST

... by: Buzz

Thursday 21-Jan-2016
Solver fantastic--love it--BUT--would be really nice if the solver would let puzzlers label individual candidates with at least two colors--four would be great--especially for chaining strategies!

Any chances you can make thus happen? And after color chosen --printable!

For example: I would like to be able to choose a candidate and then have the solver show me all of the possible DFCs for that candidate at that time in the puzzle-- possible?

When I do this by hand there are usually several to many DFC solutions--but it takes forever!

Possible in the future?
Buzz
Andrew Stuart writes:
Yes I need to do something like this - [Del]
Add to this Thread

... by: Buzz

Sunday 4-Jan-2015
To John Landre
I agree JL with your comment on DFC

My problem is the same--you have to find find the chains thru trial and error---because "recognition" of a technique within a puzzle is everything---and knowing which "digit" will provide that "useful" scenario by just looking is not productive for me---sooooo

----I took one extreme puzzle---performed all of the basics with the Solver ----but with all of the non-basic techniques off--- and when the Solver states "can go no further"--I then chose a bi-value cell to perform DFC----I pick a digit from that cell in the puzzle---and underline it once with a green sharpy--that SINGLE green underline indicates the ON situation for that digit ---then I go thru the entire puzzle ---with that green sharpy and underline each ON consequence with a SINGLE green line---and each OFF consequence with a DOUBLE green line---

--and when that green "NET" is done---I go back to the original cell and digit---and perform the same routine with a red sharpy pen----this will produce the OFF NET consequences---and again---I do this again as far as it takes me---

What I have seen is that very often--- several to many candidates can be turned OFF---because the red and green NETs so constructed---clearly show that regardless of whether your chosen digit is ON or OFF ---several to many candidates will be OFF --doubly underlined with both colors--and as per the rules--- these digits can be removed!

And---- further--- several to many are turned ON by both colors---and--again--asper the rules-- these digits are valid solutions!

I have solved many extreme puzzles using this NET FORCING method---bottom line--the digit you choose rarely matters---you generally get eliminations and solutions enough to move you through the puzzle quite easily! (Though your comment about choosing an original digit that has widespread interactions within the puzzle --obviously is the optimal choice for the broadest results)!

Buzz



REPLY TO THIS POST

... by: Dale E. Kloss

Saturday 19-Oct-2013
What does the solver do when testing a digit in a Digit Forcing Chain and a contradiction is discovered at the end of the chain (for example, the chain end forces two 5's in a unit ). Does the solver mark the Forcing Digit as "it can't be the assumed value" ?

Then the same question for the other Forcing chains ? Thanks, Dale Kloss
Andrew Stuart writes:
To the question "it can't be the assumed value", no, is the answer. The original digit will either be ON or OFF - one of those two states by necessity. Digit Forcing Chains (and other Forcing chains) can't tell us anything about the originating candidate(s). But because of their simple binary nature we have two possible 'futures' that branch off. One of those futures will be true and if we can determine that the consequence of those 'futures' are the same then we can make eliminations at the end of those two branches.

With Nishio it *IS* the originating candidate that is effected, because we are pretty much reversing Digit Forcing Chains, but that's just Nishio.
- [Del]
Add to this Thread

... by: michael dunipace

Wednesday 19-Sep-2012
Extension to comment of 16 Sep 12:
Digit Forcing Chains page:
Digit to Unit Attack section:
4th paragraph beginning as follows:

an awkward ALS on {E9|A9} - not easy to spot. The chain goes into the cell E9 and turns OFF the 6 which leaves just a Naked Pair of 4/9 in A9 and H9. .....(etc.).

Notice the "H9" at the end of the above excerpt? Should it not be "E9"?

Best Regards,
MD
REPLY TO THIS POST

... by: Michael Dunipace

Sunday 16-Sep-2012
I believe there is an error on this page as follows:
Digit Forcing Chains page:
Digit to Unit Attack section:
4th paragraph beginning as follows:
In the very next step we are obliged to find another Digit Forcing Chain this time centered on 8
in E4. Like the first example it finds that either way the 8 in E2 .....(etc.).

Notice the "E2" at the end of the above excerpt? Should it not be "E4"?
Thank you for your Sudoku Strategy examples. They are quite valuable for testing my own
solver (implementing all strategies up to AICs so far).

Best Regards
Michael Dunipace
REPLY TO THIS POST

... by: Thinkist

Monday 23-Apr-2012
Actually, never mind my previous comment. Digit Forcing Chains (as well as Dual Cell and Dual Unit Forcing Chains) are a strict subset of AICs.

Your first, second, fourth and fifth examples are the same as AICs Rule 1: Alternating Nice Loops with off-chain eliminations. Your third example is the same as AICs Rule 2.

Now if a candidate is ON or OFF...

...and another candidate elsewhere is ON, this is the same as AICs Rule 2.
...and another candidate elsewhere is OFF, this is the same as AICs Rule 3.
...and two other candidates elsewhere are ON in the same cell or unit, this is the same as AICs Rule 1, with a weak link between the two ON candidates.
...and two candidates elsewhere are OFF, no valid conclusion can be made.

In general, a candidate will be ON because of a strong link and OFF because of a weak one.

All in all, the scope of AICs really needs to be improved, and Digit Forcing Chains made obsolete (but keep the documentation).

REPLY TO THIS POST

... by: Mike Leonard

Friday 16-Dec-2011
If I load the puzzle of Figure 1, into the solver it reaches the point where 1 is remove from G3 by digit forcing chains. I do not understand why AIC did not find and remove it
Andrew Stuart writes:
Sometimes two chains are required where one is not enough. That is the case unless my one-chain AIC is missing a trick or is too restrictive in it's search and detection. But even if it is I find it helpful to break these two different approaches into different strategies. - [Del]
Anton Delprado replies:Wednesday 8-Feb-2012
@Mike There is a lot of overlap with digit forcing chains and AICs. In fact I would argue that the interest in Digit Forcing Chains is to get to the more interesting Cell and Group forcing Chains or Forcing Chains with three or more chains.

Let's look at Digit Forcing Chains. If you check whether a cell is ON in one direction and OFF in another you are sending a weak link in one direction and a strong in the other. A candidate being ON in both directions means type 2 AIC. OFF in both directions is type 3. Two candidates both ON in a cell is type 1. Two candidates both ON and same value in a group is type 1.

I might be missing the logic here but looking at your diagram at the top. My interpretation is that the blue and purple represent ON and OFF chains for the initial digit 8. If that is the case then I disagree with two OFF candidates in a cell meaning the third value is correct. All you know is if the original cell is ON then one is incorrect and if the original is OFF then the other is incorrect not that both are always incorrect.
Thinkist replies:Friday 30-Mar-2012
@Anton, I fully agree that the meaning of two OFF candidates out of three implies that the third is correct, and is in fact flawed logic to assume so.

The only unique case of DFC I can see resembles XY chains, where two candidates at the ends end up ON, eliminating the others in the same cell or unit. The other two cases are the same as AICs. Perhaps this strategy should be renamed.

Add to this Thread

... by: Lee

Thursday 30-Dec-2010
I have to agree with John, I don't see this as a very 'human' strategy.

There is nothing on this site which details the rules/patterns to look for to identify this strategy _without_ having to perform any kind of mental trial an error.

This leads me to argue that this 'strategy' is identified as a result of making an initial assumption rather than as a pattern that a person can identify to prevent the need to make that assumption.
Andrew Stuart writes:
It does require a lot of initial searching and mapping of available chains, but once the ideas are grasped, the concept seems fairly simple. One should map chain links initially - as this is required for any strategy in the chaining family.

Whether or not these are 'human' strategies in terms of paper and pencil is not really the issue. For the hardest puzzles these types of chains are absolutely necessary if an entirely logical solve path is to be identified. Perhaps they will be implemented purely by people developing such solvers and only of interest to them, but this site is dedicated to all strategies, computers or human. - [Del]
Add to this Thread

... by: John K. Landre

Thursday 26-Aug-2010
How do you find these chains?
It seems to me that, as with almost all extreme strategies, it is quicker to just start by assuming one of a possible pair is a certain value and then running the consequences until it either solves the puzzle or it runs into a contradiction. Of course, doing this sometimes does not have enough consequences to come to a conclusion with. So it helps to start this process by looking for a pair that 'runs' the puzzle, that is, that has as many connections to other pairs as possible.
REPLY TO THIS POST
Article created on 17-March-2010. Views: 126828
This page was last modified on 20-May-2013.
All text is copyright and for personal use only but may be reproduced with the permission of the author.
Copyright Andrew Stuart @ Syndicated Puzzles, Privacy, 2007-2024
Playwire