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
  Cell Forcing Chains

Forcing Chains are a powerful extension of chain strategies. Given that a cell or unit contains certain numbers, and that these are the only alternatives, we can show that certain candidates must be eliminated. Specifically we show that *all* of the alternatives must eliminate the target. The chains force the removal as no alternative exists.

Note: to see this strategy in the solver in most cases requires Digit Forcing Chains to be turned off

Dual Cell Forcing Chains

In the first example, we can eliminate 3 in E2 because of the numbers left in A2, the 2 and 3 there. It is uncontroversial that a 3 in A2 removes the 3 in E2. Hence the short chain +3[A2]-3[E2].

The 2 in A2 must now be considered. If A2 really is 2 then A9 will be 8, which forces G8 to be 9. This removes 9 from G2 and the only remaining 9 in column 2 is in E2. Therefore 2 removes 3 from E2.

Since we are arguing from a single cell and the cell has two candidates, this is the simplest Forcing Chain, a Dual Cell Forcing Chain.
Dual Cell Forcing Chain
Dual Cell Forcing Chain: Load Example or : From the Start
Triple Cell Forcing Chains

So if bi-value cells can work this magic, lets go up an order of complexity and test a Triple Cell Forcing Chain. This one starts on D1. The first chain, in blue, is another short one-shot. 3 removes 3 from D7. Forcing chains don't always need a nice first deduction, all three chains could be very long.

The second chain +5[D1]-5[D8]+3[D8]-3[D7] is a little more involved. The 5 in D1 must remove the 3 in D7. 5 will force a 3 in D8 which does the trick.

Now to force 9 in D1 to remove the 3 in D7 we have to use quite a complex chain. It reads +9[D1]-9[H1]+9[H9]-9[E9]
+3{E9|D8}-3[D7]
. The curly brackets is my symbol for an ALS (Almost Locked Set). Documentation forthcoming.
Triple Cell Forcing Chain
Triple Cell Forcing Chain: Load Example or : From the Start
In red, the chain starts with a 9 in D1 (+9). Removing the 9 in H1 means the 9 must be in H1 as its the last in the row. If that is the case we must remove the 9 from E9. E9 is interesting as it forms part of an Almost Locked Set with D8. An ALS is a set of N cells with N+1 candidates. In this case {3,5,9}. But by removing the 9 from E9 we have reduced and Almost Locked Set to a Locked Set. A 2-cell locked set is a Naked Pair. 3 and 5 must exist in D8 and E9 - we just don't know which way round yet. If this is the case then 3 can't exist in D8.

Viola, we have forced 3 from D8 using the contents of D1.
The second triple example is nicely complex one. It's improbable that you might detect it using pen and paper, but I include it to show the reach of the Forcing Chains. We show that the content of J7 can remove the 7 in B2. The blue chain is easy. A 1 one J7 leads to a 7 in B7 and therefore no 7 in B2. Hense +1[J7]-1[B7]+7[B7]-7[B3].

The purple chain, +7[J7]-7[J1]+7[G3|H3]-7[B3] contains an interesting group, symbolised by +7[G3|H3]. All this means is that if J1 is not a 7 then G3 OR H3 must be. If one of those must be 7 we can look along their alignment - the columns, and remove 7s, eg 7 in B2.

The last chain, +9[J7]-9[H7]+9[H3]
-9[C3]+7{C3|A1}-7[B3]
contains an ALS, which I described above. We have a {1,7,9} in two cells A1 and B3. Removing 9 from B3 leaves a locked set of 1/7 in that box. All other 1s and 7s can be removed, namely the 7 in B2.

Complex Triple Cell Forcing Chain
Complex Triple Cell Forcing Chain: Load Example or : From the Start
Quad Cell Forcing Chains

Logic relentlessly obliges us to consider the Quad formation, although I have not and will not look for higher order forcing chains, although they are possible. Quads are pretty rare. I found 6 in a random stock of forty thousand puzzles.
In this example, the cell B9 contains {2,5,6,7}. By a miracle were any one of these the solution (and one must be) we can show that there is no 5 in G2, giving us the solution of 4 in that cell. Although somewhat crowded when overlain, all four chains are simple - no ALS or grouped components.

If there is a 2 in B9 it follows that
+2[B9]-2[G9]+5[G9]-5[G2]
If there is a 5 in B9 it follows that
+5[B9]-5[C7]+5[C2]-5[G2]
If there is a 6 in B9 it follows that
+6[B9]-6[H9]+6[H1]-8[H1]+8[H2]
-1[H2]+1[G2]-5[G2]

If there is a 7 in B9 it follows that
+7[B9]-7[F9]+2[F9]-2[G9]+5[G9]
-5[G2]
.
: Load Example or : From the Start

breakline

Add your comments

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

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 6-March-2010. Views: 2460
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