Looking for Forcing Chains

Advanced methods and approaches for solving Sudoku puzzles

Looking for Forcing Chains

Postby nj3h » Fri Sep 30, 2005 8:40 pm

I would be greatful if some of the members could give some tips on how to make the intial choice in which cell to start with. Is there something you are looking for that makes this choice obvious?

Thanks.
nj3h
 
Posts: 47
Joined: 07 July 2005

Postby Jeff » Fri Sep 30, 2005 9:31 pm

nj3h, I suggest not to identify any cells to start with, because the next step would likely be a bifurcation process.

Instead, plot a bilocation/bivalue graph and identify nice loops as posted here. Every nice loop is a double implication forcing chain.

The result of the destination cell is forced by two implications in opposite directions from any cell on the chain to the destination cell, thus the name double implication.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby tso » Fri Sep 30, 2005 9:48 pm

On the one hand, the question assumes facts not in evidence. Forcing chains are no different than much simpler patterns in this respect. Even if I KNOW there is a naked pair somewhere, I'll have to systematcially search for it.


On the other hand, there are several methods that will help find forcing chains in some contexts. There's a pile of posts explaining various methods already in this forum.

Search for "forcing AND chain", "xy-chain", "binary AND groups", etc.

Read the second part of Eppstien's paper: http://arxiv.org/abs/cs.DS/0507053

Generally, "bivalue" graphs are much easier than "bilocation" graphs. (Many of the forcing chains found and posted in the forum use a little of both in the same chains. I think these are generally harder to find, but more likely to be there.)



Let me add one thing that pertains to xy-chains only. XY chains -- which is another name for bivalue graphs -- connect cells which have exactly 2 candidates. A simple method: when simpler logical steps reach an end, connect all 2 candidate cells that share at least one candidate (and are in the same row, column or box) by a line. Label the line with the candidate (or candidates) shared by the cells connected. Then look for a closed loop that has a single repitition of lables. For example:


These six "bivalue" cells form a loop:

Code: Select all
[12]--------[23]---[34]
 |                  |
 |                  |
 |                  |
[15]---[56]--------[45]



You label the edges:


Code: Select all
         (2)      (3)
  [12]--------[23]---[34]
   |                  |
(1)|                  |(4)
   |                  |
  [15]---[56]--------[45]
      (5)      (5)


The loop has a single repetition -- two consecutive 5's. Without any further thought, you can eliminate the candidate 5 from the cell between the two matching edges!

This is important -- you don't have to "make the intial choice in which cell to start with"! If you want to write down the description after finding the loop, you can start from ANY one of the cells other than the one in which the elimination was made.

In many cases, these lines can be eyeballed -- you don't actually have to put pencil to paper. Just follow them around until you have a loop with a single repeat. Warning -- this does not find ALL chains, just pure XY-chains. If you do draw the lines, in most cases, if there is a chain to be found, you will find it quickly, if there ISN'T one, you will know that quickly as well. So, though the method is "advanced" compared to something like hidden triples in one sense, they're actually easier to find or eliminate.

Note that the elimination can be made even if the [56] cell had more candidates:

Code: Select all
         (2)      (3)
  [12]--------[23]---[34]
   |                  |
(1)|                  |(4)
   |                  |
  [15]---[567]-------[45]
      (5)      (5)


You can still eliminate the candidate 5 from the [567] cell -- but this might be harder to spot as you have to take into account the cells that have more than 2 values.


This method also works with a bilocation graph -- good luck getting that to work. I never have.
tso
 
Posts: 798
Joined: 22 June 2005

Postby nj3h » Sat Oct 01, 2005 1:34 am

Thanks to all that provided information to my question. Something to study this weekend at the in-laws.

All enjoy your weekend.

George
nj3h
 
Posts: 47
Joined: 07 July 2005


Return to Advanced solving techniques