The New Sudoku Players' Forum

[Jeff]

I open this thread to address an issue that most new players are interested, ie. How to identify a forcing chain?

To all forcing chain expects, could you please post the methods that you are using to identify forcing chains in a grid. If the solver is a computer program, could you tell us the procedures that your program has adopted to look for forcing chains? Personally, I don't know what brute force is and I don't want to know. So, no one should criticise any methods and there is strictly no room here for discussion of trial and error, bifurcation or guessing and stuff like that.

Thanks in anticipation

Here is my method (you may have to refer to the terminology and definition for forcing chains in the other thread):

I identify forcing chains by hand with the help of Angus' solver, called Simple Sudoku. I use a technique called bilocation/bivalue plot. With Simple Sudoku, I solve the grid up to xy-wings and then using the 'Copy Image' function to paste the graphical image of the grid onto an excel spreadsheet. Using the 'Filtering' function in Simple Sudoku, I filter out each candidate in turn to identify conjugate nodes on the copied image. Using the 'Drawing' functions in excel, I draw "strong links" (solid line), each with a label, for conjugate nodes of all 9 digits. I then use the 'Bivalue' function in Simple Sudoku to highlight all bivalue nodes and draw "links" (broken line), each with a label, between these nodes and also connect them to strong links where possible. Of course, there is nothing wrong to draw all these links by hand onto a print-out grid.

Following a set of nice loop propagation rules of valid link label sequence, I perform a pattern recognition process to find if there are any nice loops and during the process I draw additional "links" as necessary. It is similar to the identification of a swordfish or an xy-chain, except that I have all these links to follow. Once a nice loop is identified, a deduction or a bunch of deductions can be concluded corresponding to specific nice loop characteristic. I then express this nice loop in a nice loop notation for record. Each nice loop represents a forcing chain or a forcing net and the same process repeats.

Some easy grids may be solved by one or 2 nice loops. With difficult grids, if a grid still cannot be solved after the first round, the grid will be updated and a second round of identification will be performed.

[CathyW]

Thanks Jeff - I look forward to reading the responses. I've still not got to grips with forcing chains even though I've been doing Sudoku puzzles since they were first published in The Times.

[tso]

I generally look for simply xy-type chains first, looking at bivalue cells only by 'eyeball'. I'll mentally say the label of each edge (the shared digit between two cells) until a loop is formed. I don't care how long it is or even if I can remember the path I took, as long as it has a single repetition, I can make the exclusion. In fact, the longer it is, the more satisfying. If the grid has mostly bivalue cells and only a few polyvalue cells, I know to look for the repetition in a group that contains at least one of the polyvalue cells. (If I find a loop that has no repetition, I'll mark it with a pencil before making all the exclusions.) I used to use what I called 'binary groups', but that's basically obsolete.


For chains using a single candidate, I use coloring, though I don't really think of this in terms of chains.

For chains requiring some strong links and NOT restricted to a single digit (What Sudoku Susser calls "comprehensive forcing chains") -- I have no good method and I'll likely miss one even if I *know* it is there.

If I find a chain involving multi-cell nodes, it's usually by accident (or genius depending on your POV).

[JeffInCA]

Jeff wrote:

Using a function in Simple Sudoku, I filter out each candidate and draw "strong links" (solid line), each with a label, for all conjugate nodes. I then highlight all bivalue nodes and draw "links" (broken line), each with a label, between these nodes and connect them to strong links where possible.

Jeff, can you explain how you draw the links using Simple Sudoku? Or do you just print out the grid from SS and draw the chains?

[Jeff]

Jeff, can you explain how you draw the links using Simple Sudoku? Or do you just print out the grid from SS and draw the chains?

Hi Jeff, I have edited my post to include more details on link construction.

[ronk]

I've only recently started identifying forcing chains and, relative to your b/b plotting, it's certainly hit-or-miss, meaning I simply will not see a lot of chains that would lead to a solution. But there are lots of puzzles in this universe, so I just move on. My "method" is certainly not T&E, which I dislike and have never used even as a last resort.

Like you I use Simple Sudoku to spot strong links and strong nodes --- highlighting candidates to help spot strong links (conjugates) and highlighting pairs to help spot strong nodes. But I plot neither on paper nor with a graphics program. (I've actually tried both a few times, and ended up with so much clutter on the grid that it seemed counter-productive.)

Let me illustrate using the Type 3 Almost-Unique-Rectangle (AUR) example Carcul posted here today.

Code: Select all

  45   3    8   | ^2456  1     7   |  9     56    24   
  145  7    9   | ^2456  8    *245 |  1245  356   1234 
  6   ^14   2   | ^45    3     9   |  8     57    147   
----------------+------------------+-------------------
  9    168  135 |  7     26    25  |  125   4     1238 
  48   468  57  |  3     2469  1   |  257   579   278   
  134  2    1357|  459   49    8   |  157   3579  6     
----------------+------------------+-------------------
  2    5    4   |  1     7     3   |  6     8     9     
  138 ^89+1 13  | ^89    5     6   |  47    2     47   
  7   ^89   6   | ^89+24 249  ^24  |  3     1     5     


I have tagged the cells of the chains identified here with '^' and the elimination cell with '*'.

While it's difficult to put a thought process into words, I'll give it a try. I started with Carcul's identification of the AUR (89) in r8c24 and r9c24. According to the uniqueness principle, at least one of the non-AUR candidates must be true. And as you know, similar to BUG grids, if all non-AUR candidates lead to the identical placement(s) and/or elimination(s), then those placements and/or eliminations must be valid. So I mentally AUR-split the candidates as shown with the "AUR + non-AUR" candidate notation shown on the grid above.

Then noting a match between the non-AUR r9c4=24 and bivalue r9c6=24, I scan column column 6 for possible propagation of implications to a common cell, using Simple Sudoku's highlighting feature as described above. It's rather easy to see the implication:

r9c4=4 => r9c6<>4 => r2c6=4 => (r2c6<>2 and r2c6<>5)

Despite the noted match of 24s, implications of r9c6=2 don't "converge" to r2c6 through column 6, so I look elsewhere ... and note that r9c4=2 creates the naked triple r123c4=456 so we have:

r9c4=2 => r123c4=456 => r2c6<>5

This is looking promising so I next check the implications of r8c2=1. This one is easy to spot, mostly because of bivalues, where we have:

(r9c4<>2 and r9c4<>4) => r8c2=1 => r3c2<>1 => r3c1=4 => r3c4<>4 => r3c4=5 => r2c6<>5

Because all three non-AUR candidates lead to the same elimination ... r2c6<>5. I've made this deduction without b/b plotting (printing or imaging the grid and drawing lines) and without (in this case, and usually) writing down the implication chains as I've done here. However, I do use Simple Sudoku's coloring tool to mark the chains.

Without a doubt, I'm using the principles of b/b plotting but, since my method is not a rigorous method, I'll miss a lot of chains ... IOW hit or miss.

Ron

P.S. Carcul's first elimination is different, i.e., r6c1<>4.
P.P.S. The chains overlap at r3c4, but the logic is still OK.

[Jeff]

Anyone like to share a method?

[tarek]

I would find it extremely difficult to spot forcing chains unless the grid has disintegrated into a bivalue grid..........

you can then run through your mind a trail of xy chains that hit the same target, double implication is obviously easier than triple implication chains......

IMO, it would be vary difficult to spot a forcing chain otherwise, unless the chain is very short.

[maria45]

Hi Jeff,

hm, sharing a method: that should be something systematic. In my experience, I only encountered forcing chains which involve more than one box/row/column. Dunno if that must be so, but thats a starting point.

The second point: a forcing chain has always a "starting cell" and a "goal cell". Alternatively, you can look for forcing chains with a mutually exclusive value in two cells like this:

Either b9=6 OR e9=6

The utmost generalization of this is the consideration:

Either xn=a OR xn!=a

In the case of a bivalue starting cell containing the values a and b, if it is != a, then obviously it must b.
In the case of a mutually exclusive value: if the value a is not in cell x, it must be in cell y.

The third point: a forcing chain must converge on a "goal cell". Sometimes, you are lucky to detect a simple contradiction in following the one half of a forcing chain. You could of course stop there and solve the puzzle. Curious, however, as I am, I always wanted to know if the existence of a contradiction at a certain point implies the existence of a forcing chain at the same point. I found this to be true in all puzzles I considered. Of course, this is no proof. I only wanted to know if I can avoid contradictions and solve every nontrivial puzzle by forcing chains.

Well, the fourth point: in the example I posted with tso:

Code: Select all

  1....2......3...4....5...6..7....8....9

a 8....4679...679.2....46..5..3467.369..1
b 2457.245679.679.1....8...3..4567.2569.2467
c 1....2456...3...469..7...49.8....256..246
d 6....3......4...8....2...1..9....7....5
e 57...57.....8...3469.346.49.2....1....36
f 9....1......2...36...5...7..36...4....8
g 247..2467...5...34...9...8..1....236..23467
h 24...2489...19..7....134.6..345..2358.234
k 3....4678...167.5....14..2..467..68...9


the first forcing chain was really easy to find in box 7 (left below), because there are 4 cells containing three mutually exclusive pairs:

hk2=8, h23=9, hk3=1

This is a good point to look for a forcing chain. But now the rule comes: a forcing chain always involves more than one box. Looking further, we find two other mutually exclusive pairs:

k28=8, k8=68

Next point: a forcing chain must involve at least one value at three cells. How else would one reduce the solution space? A forcing chain can only be successful if (at least) one of three possible values can be eliminated.

In the example, we find this to be the case with the 6 at k2, k3 and k8. These are 3 cells, but only two of them can be real alternatives, the third can always be eliminated if the fitting mutually exclusive pairs are involved.

The next to last trick to find the correct starting cell: in most cases, take the "far out" cell, here k8 and "aim" at the other cells involved, in this example k2, k3, h2, h3.

Last trick: dont start at cells like e12 in the example. These are "end points", the roads usually run dead from there, that is: you don't find a forcing chain there, because the "force" runs out, not enough mutually exclusive cells/values from there. Sometimes, I observed in nearly complete bivalue grids, you can also start from these "end points", but there is always a more elegant solution, i.e. a much shorter forcing chain.

Hopefully this is understandable...

Kind regards, Maria

[Jeff]

Hi Maria, Thank you for sharing your method. BTW, I find your forcing chain notations very interesting. Could you tell us where they originate from?

[maria45]

Hi Jeff,

I just read through your thread with the definitions of forcing chains and related terms. In that view, I think I use forcing nets, too.

Origin: developed on my own. Basically, coming from chess, I really like short notations. If the notation is short, its easy to follow in mind. And when I began to do 16x16 sudoku with forcing nets, short notations became somehow mandatory. But I always do the forcing nets in my head without taking notes. The notes only come into play for documentation.

[Carcul]

Hi Maria and Jeff.

I would be interested to know how different is Maria's method from the traditional bilocation/bivalue plot.

Regards, Carcul

[Jeff]

Here is an alternative solution for puzzle #4 (without eliminating the "3" from r2c5):

[r5c9]-3-[r7c9]-9-[r9c7]-3-[r9c5]-2-[r9c6]-5-[r9c1]-9-[r4c1]-1-[r5c3|r6c3]-6,9-[r5c4]=6=[r5c3]-6-[r6c3]-9-[r6c4]=9=[r3c4]=2=[r5c4]-2-[r5c8]-3-[r5c9], => r5c9<>3 which solve the puzzle (paying attention to the X-Wing on "9" that emerges).

Hi Carcul, Would you mind to share your secret in how to identify all these complicated nice loops in details. What would you say to those people who like to solve puzzles manually and logically, but found that the technique for identification of nice loops is too daunting?

[Jeff]

I would be interested to know how different is Maria's method from the traditional bilocation/bivalue plot.

Hi Carcul, Obviously, one significant difference is that Maria doesn't construct any B/B plots. Probably more backtracking is required before a nice loop can be identified.

[Carcul]

Hello Jeff.

Hi Carcul, Would you mind to share your secret in how to identify all these complicated nice loops in details.

I knew that, sooner or later, you would make that request . Let me say first a very important thing: the method that I use should not be important for anybody, because it results with me and may not be good for you or someone else (because of personal taste, etc) - anyone should search for the better method that fits is own personality and taste.
However, if the method I use can be usefull for you or someone else, then I gladily will share it:

1. First, as I have made a blank Sudoku grid in the "Paint" program, when I want to solve a puzzle I print it.

2. Next, using a blue pen, I write the initial numbers in the corresponding cells of the blank grid, as given in the original puzzle.

3. Then, using a pencil, I start to write the (logically deduced) possible candidates in each cell. During this process, when I note that a given candidate "x" can appear in only two cells of a unit (a strong link) I write them isolated in the upper part of the respective cells and make a circle around them, drawing also a very little line in each circle in the direction of the corresponding conjugate node. If in the same cell there are two or more "strong candidates", all of them are drawn in the upper part of the cell with the respective circle and line in each one.

4. Also, during this process, I pay attention to the localization of Almost Locked Sets and how they look like, specially to see if in the ALS there are candidates restrited to one unit or one cell (sometimes I write this information outside the grid); I also pay attention to possible grouped strong links.

5. When I have all the possible candidates in all the undecided cells, and all the strong links marked with the circles, I make a "check up" on the grid:
- to see if there are strong links that I have not seen before (sometimes, when I don't have much time or patience, I use Simple Sudoku to help me on this);
- to see if there are Unique Rectangles;
- to see more ALSs, to see eventual AURs or others Almost Unique Patterns;
- to see the localization of bivalue nodes.

6. Finally, I start the construction in my head of simple relations between the strong links and with the bivalue nodes, looking for the circles that I have drawn in the grid (which are a kind of "simple bilocation/bivalue plot"). If I cannot identify any loop with this, then I start making more complex relations envolving grouped links, ALSs, AURs, etc, always paying attention to cells that allow multiple implications to be made.

I don't actually draw a b/b plot with all the lines and labels because I have tried that in the beginning for two or three times and I have concluded that a complete b/b plot is very confusing to me, as I found extremely hard (and with no fun) to identify loops with it. With the circles, I make a compromise between a confusing spaghetty plot and a complete (and harder) only-brain-construction of loops.

Besides all this, of course that experience and trained eye (and also a little lucky sometimes) plays an important role: for example, nice loops whose deductions result in a new strong link or a new bivalue node can be specially usefull, and I always try to use the inference made by a loop in the following one. I also pay special attention to AURs (and even Almost AURs), because, when present, they normally allow important deductions to be made.

Hope this help.

What would you say to those people who like to solve puzzles manually and logically, but found that the technique for identification of nice loops is too daunting?

I would say that: first, they should have a good knowledge of the nice loop propagation and deduction rules, and also of the remaining techniques (ALSs, Uniqueness, AURs, etc); and second, they should try to find their own (preferred and with some fun) method of identification of nice loops. Because Sudoku is a puzzle, and if we don't have fun with it (if we just act mechanically and boringly in applying sistematically the techniques) then it is not worth.

Regards, Carcul