How do you know where to start a forcing chain?

Advanced methods and approaches for solving Sudoku puzzles

How do you know where to start a forcing chain?

Postby CathyW » Thu Oct 27, 2005 4:30 pm

This is a generated puzzle from Sadman Software.

Code: Select all
+---+---+---+
|..2|6.3|.79|
|8..|2..|.3.|
|4..|.8.|2..|
+---+---+---+
|...|7..|3.8|
|...|...|...|
|9.5|..8|...|
+---+---+---+
|..8|.7.|..1|
|.5.|..2|..3|
|62.|8.5|7..|
+---+---+---+

I progressed to here fairly easily but apparently it needs a forcing chain to complete. How do you know where to start - presumably one of the pairs - or doesn't it matter?

Code: Select all
+---+---+---+
|512|643|879|
|8..|2..|43.|
|43.|.8.|21.|
+---+---+---+
|...|7..|358|
|.83|..4|967|
|975|368|142|
+---+---+---+
|3.8|.76|521|
|75.|..2|683|
|621|835|794|
+---+---+---+
CathyW
 
Posts: 316
Joined: 20 June 2005

Postby emm » Thu Oct 27, 2005 6:44 pm

Next step on Sudoku Susser is the XY wing 59,19,15 which is like a short forcing chain and then starts a chain from r2c2. First cab off the rank?

Here's a link to a previous discussion about how to start chains. http://forum.enjoysudoku.com/viewtopic.php?p=10012#p10012
emm
 
Posts: 987
Joined: 02 July 2005

Postby CathyW » Thu Oct 27, 2005 9:27 pm

Thanks Em - think I'll have to study that thread and the technique generally a bit further to work out 'logical' starting points.

The XY wing was a much easier chain to follow than the one suggested by the Sadman Software as the next step which was given as either candidate from r4,c1 gives 7 in r3,c6. OK with 1 (which turned out to be the correct number) but I couldn't follow the chain from trying to place 2 in that cell without getting an obvious error in box 2. Must have gone wrong somewhere - perhaps I'll have to try printing them out and physically drawing the chain as I can't seem to hold many numbers in my head:!:
CathyW
 
Posts: 316
Joined: 20 June 2005

Postby tso » Thu Oct 27, 2005 9:34 pm

It's often a good idea to look for xy-wings before looking for longer chains -- though longer ones will sometimes become obvious during the process.

One simple systematic way to look for xy-wings:

Examine only 2-candidate cells. Look for the FIRST 2 cells that share EXACTLY one candidate in the same group (row, column or box).

In this case, that would be r2c29 -- [69][56].

Now look for a third cell containing the two candidates NOT in common in the first ([59] in this case) that is in the same group with exactly ONE of the first two cells. If one cannot be found (it cannot in this case), move on to the next pair of cells sharing one candidate.

In this example, eventually you will find the two cells r35c4 [59][15]. R4c6 [19] is in the same box as r5c4. Bingo! This is an xy-wing! Either r3c4 or r4c6 MUST be a 9 -- in either case, r4c4 and r3c6 must NOT be a 9.

[EDIT: The last sentence in this paragraph should be: "Either r3c4 or r4c6 MUST be a 9 -- in either case, r46c4 and r123c6 must NOT be a 9." Changes in bold.


This process will find all four cell xy-type forcing chains or show that none exist. It is only slightly more difficult than looking for triples -- maybe easier, as you can ignore cells with more than 2-candidates.


There are several ways to look for longer chains. Which method is best/easist depends on the puzzle.
Last edited by tso on Fri Oct 28, 2005 11:13 am, edited 3 times in total.
tso
 
Posts: 798
Joined: 22 June 2005

Postby stuartn » Fri Oct 28, 2005 10:41 am

A very clear description tso -

stuartn:)
stuartn
 
Posts: 211
Joined: 18 June 2005

Postby CathyW » Fri Oct 28, 2005 3:05 pm

Thank you Tso - that is really helpful:)
CathyW
 
Posts: 316
Joined: 20 June 2005

Postby QBasicMac » Fri Oct 28, 2005 4:31 pm

tso wrote:in either case, r46c4 and r123c6 must NOT be a 9.


Hey, nice notation!

I presume r123c6 is short for r1c6, r2c6 and r3c6.

Haven't noticed that notation before.

Anyway, right!, great explanation with exact cells and values specified, rather than vague hints!

Mac
QBasicMac
 
Posts: 441
Joined: 13 July 2005

Postby QBasicMac » Fri Oct 28, 2005 4:33 pm

Hi, Cathy

Your title:
How do you know where to start a forcing chain?

My guess is that it doesn't matter. Start anywhere and go both ways until you can't go further.

I stand by to be corrected.

Mac
QBasicMac
 
Posts: 441
Joined: 13 July 2005


Return to Advanced solving techniques