Strategies for Number Puzzles of all kinds
  Print Version
Solvers
Puzzles
Basic Strategies
Tough Strategies
Diabolical Strategies
Extreme Strategies
Depreciated Strategies
Str8ts
Other
The Logic of Sudoku
  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 canidate is always ON or always OFF - then we have a contradiction.
In this article we have a very tough Sudoku which contains a neat series of Digit Forcing Chains of increasing complexity. The first is given in Figure 1.

The 'digit' in this strategy is a single candidate - in this case the 9 in G2. We are looking at the consequences of this 9 being ON or OFF. If Off, then the only remaining 9 in the column is the one in E2. This would remove the 3 from that cell. Hense
-9[G2]+9[E2]-3[E2] (the blue chain).

Now, to be useful, we need to show that the 3 in E2 would also be removed if 9 in G2 were the solution (and turned ON). This is slightly more complicated but the chain only uses bi-value cells:
+9[G2]-9[G9]+8[G9]-8[A9]+2[A9]
-2[A2]+3[A2]-3[E2] (the purple chain)
9 in G2 forces an 8 in G9, a 2 in A9 and a 3 in A2 - voilà - that removes the 3 in G2.

Whether G2 is 9 or not the chains imply E2 cannot be 3
 Figure 1: Digit Forcing Chain
Figure 1: Digit Forcing Chain: Load Example or : From the Start

G2 also nets us another candiate in E2, the 1. The blue chain is the same - removing the 9 in G2 puts a 9 in E2 so no 1 is allowed.

A very similar purple chain gets us that 1 if 9 is turned ON:
+9[G2]-9[G9]+8[G9]-8[A9]+2[A9]-
2[E9]+1[E9]-1[E2]

So, whether G2 is 9 or not the chains imply E2 cannot be 1



 Figure 2: Second Digit Forcing Chain
Figure 2: Second Digit Forcing Chain

Now we move to somewhere else on the board, the 5 in B2. This is a little more complicated as we have a grouped 'call' in 3 in C5/C6. But follow the chain round:
+5[B2]-5[B4]+2[B4]-2[H4]+3[H4]
-3[A4]+3[C5|C6]-3[C3]
The 5 in B2 means a 2 in B4. That forces a 3 in H4 turning OFF the 3 in A4. The only remaining 3s in box 2 are in C5 and C6. We notionally turn both of them ON and look along the row they are aligned on. If they are 'ON' (collectively) we can conclude 3 must be removed from C3

The other very simple blue chain removes the 3 in C3 because a 5 must go there when we turn the 5 off in B2.
 Figure 3: Third Digit Forcing Chain
Figure 3: Third Digit Forcing Chain

The final Forcing Chain in the sequence goes to G5 and the 7 there. The target is the 1 in G3. The blue chain is long but not hard. Removing 7 takes us round the board to G4 (+7), A4 (-7), A8 (+7), A9 (+8) and G9 (-8) forcing G3 to be 8 and hence not 1.

The second, purple chain contains a nice ALS cell on {1/5} in C3/G3 in the row. If 7 is ON in G5 then 3 will be removed from F3 leaving a Naked Pair of 1 and 5 in C3 and F3 - which of course removes the 1 from G3.

All in all
-7[G5]+7[G4]-7[A4]+7[A8]-8[A8]+
8[A9]-8[G9]+8[G3]-1[G3] and
+7[G5]-7[F5]+3[F5]-3[F3]+1{F3|C3}-1[G3]
Imply that G3 cannot be 1 whether G5 is 7 or not.
 Figure 4: Fourth Digit Forcing Chain
Figure 4: Fourth Digit Forcing Chain
Continue to Cell Forcing Chains or Unit Forcing Chains....

breakline

Comments...

Thursday 26-Aug-2010

... by: John K. Landre

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.

A confirmation email will be sent to you after submitting.

Your Name

Email Address - required for confirmation (it will not be displayed here)

Your comment or question

Enter these lettersarrow
Remember me


Please keep your comments relevant to this article.
Email addresses are never displayed, but they are required to confirm your comments. When you enter your name and email address, you'll be sent a link to confirm your comment. If you want to be remembered, the check box above will store a cookie with your name and email address on your computer.

Line breaks and paragraphs are automatically converted — no need to use <p> or <br> tags.



Article created on 17-March-2010. Views: 2840
This page was last modified on 17-March-2010, at 14:14.
All text is copyright and for personal use only but may be reproduced with the permission of the author.
Copyright Andrew Stuart @ Scanraid Ltd, 2010