The New Sudoku Players' Forum

[Jeff]

I start this new thread to demonstate, through solving of the puzzle posted by txlef, how double implication forcing chains can be identified by means of a bilocation/bivalue plot (b/b plot).

Stuck. Need some advice on how to proceed without t&e please:

Code: Select all

 *-----------*
 |.5.|..1|6..|
 |3.6|..2|...|
 |..9|3..|2.4|
 |---+---+---|
 |..4|53.|182|
 |...|8.4|...|
 |8.5|12.|4..|
 |---+---+---|
 |6.1|..5|3..|
 |...|6..|9.1|
 |..7|21.|.46|
 *-----------*

To solve this grid, a total of 4 simple nice loops are required and they were identified by means of a bilocation/bivalue plot. The following diagrams only show relevant links related to each simple nice loop being discussed. All other links in the b/b plot were omitted for clarity.

Using Angus' simple sudoku solver till no more hint is available, the original grid was reduced to:


Chain 1: [r6c8]=6=[r5c8]-6-[r5c5]=6=[r3c5]=5=[r3c8]-5-[r2c9]=5=[r5c9]-5-[r5c7]-7-[r6c8] => r6c8<>7

This double implication chain is shown as a simple nice loop in the following diagram. It implies r6c8<>7. There are 3 other chains in this grid. You may like to construct the entire b/b plot and identify them as an exercise.


Chain 2: [r9c2]=3=[r9c6]-3-[r8c6]-8-[r8c3]=8=[r1c3]=2=[r1c1]=4=[r1c8]=5=[r8c8]-5-[r9c7]-8-[r9c2] => r9c2<>8

This double implication chain is shown as a simple nice loop in the following diagram. It implies r9c2<>8. There is one other chain in this grid. You may like to construct the entire b/b plot and identify it as an exercise.


Chain 3: [r3c6]=6=[r3c5]=5=[r3c8]-5-[r8c8]=5=[r9c7]=8=[r9c6]-8-[r3c6] => r3c6<>8

This double implication chain is shown as a simple nice loop in the following diagram. It implies r3c6<>8.


Chain 4: [r9c6]=8=[r9c7]=5=[r8c8]-5-[r3c8]=5=[r3c5]=8=[r3c2]-8-[r1c3]=8=[r8c3]-8-[r8c6]=8=[r9c6] => r9c6=8

This double implication chain is shown as a simple nice loop in the following diagram. It implies r9c6=8. There is one other continuous chain in this grid, which would enable 3 candidates to be removed. You may like to construct the entire b/b plot and identify it as an exercise.


Notes:
Solid line on diagram => link with strong inference, also indicated as '=x=' in nice loop notation.
Broken line on diagram => link with weak inference, also indicated as '-x-' in nice loop notation.
The node must be bivalue between 2 consecutive broken lines.

My sincere gratitude to Angus who has been sharing his excellent Simple Sudoku solver, which has taken a lot of painstaking hard work out of sudoku, enabling me to concentrate in applying more advanced techniques to difficult puzzles.

[emm]

I have to confess to having had a small secret obsession with this puzzle since txlef posted it and have been waiting for 1$ to defend his forcing chains but he seems to have nodded off somewhere so .... with some trepidation in view of the grids posted above .... does this work too?

r9c1=5=>r9c7=8=>r7c9=7=>r7c8=2=>r8c8=5=>r3c2=8=>r1c3=2=> r5c3 = 3

r9c1=9 => r4c1=7 => r3c1=1 => r5c1=2 => r5c3 =3


r4c1=7 => r5c1=2 => r5c2=1 => r1c1=4 => r8c1=5 => r9c1=9 => r9c7=5 => r5c7=7 => r2c7=8 => r2c2=7 => r3c2=8

r4c1=9 => r9c1=5 =>r9c7=8 => r7c9=7 => r7c8=2 => r8c8=5 => r3c5=5 =>r3c2=8


=> r1c3 =2 => r8c3=8 => naked triple column 6 => r8c6=3 => r9c6=8 => r9c7=5 => r9c1=9

and from there it falls apart as 'stuartn' said it would.

PS : Is that the difference between 'elegant' and 'not elegant'?

[Jeff]

.... does this work too?
r1c9=5=>r9c7=8=>r7c9=7=>r7c8=2=>r8c8=5=>r3c2=8=>r1c3=2=> r5c3 = 3

r1c9=9 => r1c4=7 => r1c3=1 => r5c1=2 => r5c3 =3 .......

There is always more than one solution to a problem. However, I am having trouble following your first chain, leave alone the second one. I have a few questions for you:

Is r1c9 meant to be r9c1?
How does the chain propagate from r8c8 to r3c2?
Is r1c4 meant to be r4c1?
Is r1c3 meant to be r3c1?
Could you list the two grids at which these chains were forced?

Unless the grids are listed, the second chain is hard to interpret.

[emm]

1. Original grid - (you thought I put txlef's extra 7 in didn't you!)

*5* **1 6**
3*6 **2 ***
**9 3** 2*4

**4 53* 182
*** 8*4 ***
8*5 12* 4**

6*1 **5 3**
*** 6** 9*1
**7 21* *46

2. Is r1c9 meant to be r9c1. Yes!

3. How does the chain propagate from r8c8 to r3c2? The grid has a naked pair 17 in row 3 c18 => r3c2=8

4. Is r1c4 meant to be r4c1? Yes!!

5. Is r1c3 meant to be r3c1? Yes!!!

6. Could you list the two grids at which these chains were forced?

[247] 5 [28] [479] [4789] 1 6 [379] [3789]
3 [1478] 6 [479] [45789] 2 [578] [1579] [5789]
[17] [178] 9 3 [5678] [678] 2 [157] 4

[79] [679] 4 5 3 [679] 1 8 2
[1279] [123679] [23] 8 [679] 4 [57] [35679] [3579]
8 [3679] 5 1 2 [679] 4 [3679] [379]

6 [2489] 1 [479] [4789] 5 3 [27] [78]
[245] [2348] [238] 6 [478] [378] 9 [257] 1
[59] [389] 7 2 1 [389] [58] 4 6

The second grid : As r5c3 =3 => r5c3 <> 2 => a triple & a naked pr in box 4

[247] 5 [28] [479] [4789] 1 6 [379] [3789]
3 [1478] 6 [479] [45789] 2 [578] [1579] [5789]
[17] [178] 9 3 [5678] [678] 2 [157] 4

[79] [679] 4 5 3 [679] 1 8 2
[12] [12] 3 8 [679] 4 [57] [35679] [3579]
8 [679] 5 1 2 [679] 4 [3679] [379]

6 [2489] 1 [479] [4789] 5 3 [27] [78]
[245] [2348] [238] 6 [478] [378] 9 [257] 1
[59] [389] 7 2 1 [389] [58] 4 6

Sorry about the errors transposing - it was getting late - I have edited them on the original (just for the sake of anyone who might try to follow my line of thinking!)

Perhaps I should have posted this under txlefs original topic or even the re-run of the original topic - Big Brother might like to move it to leave Jeff's thesis in splendid isolation.

[r.e.s.]

em,

The part that goes
r9c1=5=>r9c7=8=>r7c9=7=>r7c8=2=>r8c8=5=>r3c2=8=>r1c3=2=> r5c3 = 3
can be shortened to
(9,1)=5 => (9,7)<>5 => (8,8)=5 => ... etc.

but the part that goes
r9c1=9 => r4c1=7 => r3c1=1 => r5c1=2
involves a "net" rather than a chain -- diagrammatically something like

Code: Select all

     ---(3,1)
   /         \
  |           |
  |          /
  |     (4,1)
  |   /      \
  |  |        |
   \  \       |
     ---(5,1) |
             \|
              |
             /
        (9,1)


A smaller deductive net with "key" cell (9,7), involving about half as many cells, is as follows. The original candidate grid is

Code: Select all

{247}    {5}      {28}     {479}    {4789}   {1}      {6}      {379}    {3789}   
{3}      {1478}   {6}      {479}    {45789}  {2}      {578}    {1579}   {5789}   
{17}     {178}    {9}      {3}      {5678}   {678}    {2}      {157}    {4}     
{79}     {679}    {4}      {5}      {3}      {679}    {1}      {8}      {2}     
{1279}   {123679} {23}     {8}      {679}    {4}      {57}     {35679}  {3579}   
{8}      {3679}   {5}      {1}      {2}      {679}    {4}      {3679}   {379}   
{6}      {2489}   {1}      {479}    {4789}   {5}      {3}      {27}     {78}     
{245}    {2348}   {238}    {6}      {478}    {378}    {9}      {257}    {1}     
{59}     {389}    {7}      {2}      {1}      {389}    {58}     {4}      {6}     


so, on the one hand,
(1,3)=8 => (3,2)<>8 (call this A) => (3,1)=(3,2)={17} => (3,8)=5 => (8,8)<>5 => (9,7)=5,
and on the other hand,
(1,3)<>8 => (8,3)=8 => (8,6)<>8 => (3,6)=8 OR (9,6)=8,
but (3,6)=8 => A => (9,7)=5,
and (9,6)=8 => (9,7)<>8 => (9,7)=5.

[emm]

Thanks for that helpful reply r.e.s. - I realised my route was long and tortuous, I just didn’t think of looking for negatives. Next time.

Do you have any idea before you start how to pick the key cells? I basically have to bash out every possibility with absolutely no idea which ones are likely to work – and unless I can improve on that, I think that chains and I have not much hope of a future together!

[Jeff]

.... does this work too?.......

r9c1=5=>r9c7=8=>r7c9=7=>r7c8=2=>r8c8=5=>r3c2=8=>r1c3=2=> r5c3 = 3
r9c1=9 => r4c1=7 => r3c1=1 => r5c1=2 => r5c3 =3

r4c1=7 => r5c1=2 => r5c2=1 => r1c1=4 => r8c1=5 => r9c1=9 => r9c7=5 => r5c7=7 => r2c7=8 => r2c2=7 => r3c2=8
r4c1=9 => r9c1=5 =>r9c7=8 => r7c9=7 => r7c8=2 => r8c8=5 => r3c5=5 =>r3c2=8.......

PS : Is that the difference between 'elegant' and 'not elegant'?

Well done, this certainly works despite a small coordinate error in the second forcing net which involve quite a number of cells.

Difficult to comment on elegant-ness as I have no idea how your forcing nets were identified. To me, every technique is good as long as no trial and error was required in identifying the networks. It doesn't matter how long the chains are, how long it takes to find each chain and how many chains it takes to complete the grid.

The idea of this thread is not just to show how the grid is solved with double implication forcing chains, but to give some advices on how to identify these chains without bifurcation so that the same technique can be applied to other grids. With very difficult grids, I'll be satisfied to use the technique just to find a few chains to remove just a few candidates even if that doesn't lead to a complete solution.

With chain identification using bilocation/bivalue plot, each cell can only be implied by the immediate previous cell and each cell can only be used once in the loop. I noticed that some cells in your forcing nets are implied by other previous cells and some cells were used in both implications. This is why I called yours forcing nets rather than chains.

Keep up the good work.

[emm]

Difficult to comment on elegant-ness as I have no idea how your forcing nets were identified. To me, every technique is good as long as no trial and error was required in identifying the networks.

Jeff, you weren't sitting round waiting for me to post my reply before quickly posting this were you? It does look suspiciously like you were waiting to let me shoot myself in the foot before you answered! Well, to tell the truth when I first looked at your grids I didn't understand - but now I see that that's exactly where I should've gone in the first place, so back there I go.

Thanks for everything

[Jeff]

Jeff, you weren't sitting round waiting for me to post my reply before quickly posting this were you? It does look suspiciously like you were waiting to let me shoot myself in the foot before you answered!

No, why would I do that. It was just coincidental. My wife was on the computer all day so I couldn't get to it earlier.

[emm]

Yeah right!

[r.e.s.]

Do you have any idea before you start how to pick the key cells? I basically have to bash out every possibility with absolutely no idea which ones are likely to work – and unless I can improve on that, I think that chains and I have not much hope of a future together!

I have no method (except T&E) for spotting keycells -- which I is why I think of the non-chaining deductive nets more as objects of academic interest than as solving-tools. However, some of the smaller non-chaining nets do sometimes "jump out" at me, much as say a naked quad might. (I'll continue to call them "nets", which subsume chains, for lack of a better term.)

With tough sudokus, I do enjoy the game of trying to find the "optimum" keycell-and-net combination -- the one cell whose correct candidate leads to the solution using only naked- & hidden-singles and whose other candidates can be eliminated by the smallest possible nets. (Preferably there is only one incorrect candidate in the keycell, excludable by only one net.) I use software to locate the keycells, and hand-draw the graphs to find the nets. I think cell (9,7) with the net I posted above is optimum for this puzzle.

[Nick67]

Thanks for the excellent post, Jeff. Looks like a powerful technique,
and I'd like to add it to my bag o' tricks.

A total of 4 chains are required and they were identified by means of a comprehensive bilocation/bivalue link graph.

I wonder if I could ask you to briefly describe how to create this graph
(if a brief explanation is possible ...).

[Jeff]

Thanks for the excellent post, Jeff. Looks like a powerful technique, and I'd like to add it to my bag o' tricks.......

I wonder if I could ask you to briefly describe how to create this graph
(if a brief explanation is possible ...).

This technique provides pattern recognition for identification of double implication forcing chains. The only disadvantage is time-consuming. It should only be applied after all other non-T&E techniques have been exhausted.

In brief, lines are to be drawn and labelled for nodes in the same unit as follows:
1) Draw solid line between conjugate nodes.
2) Draw broken line between bivalue nodes sharing same candidate.
3) Draw broken line between ends of 2 solid lines with same label.
4) Draw broken line between the end of a solid-line to a bivalue node with the same label.
5) Identify nice loops. Draw additional broken lines to complete nice loops as required.

Have fun

[Nick67]

Great! Thanks for the quick reply. I'll give it a try ... I've been saving up some hard puzzles.

[Max Beran]

Apolgies for returning to a thread that might have been thought long dead but my progress towards getting to grips with chains has been a long and agonising one (and still nowhere near complete).

Anway I was attempting to solve this puzzle from
http://vanhegan.net/sudoku/index.php?date=2005-10-27&class=6

7..|6..|3.1
.46|...|.9.
2..|.4.|.8.
---+---+---
...|4.3|..8
..4|.6.|1..
5..|8.7|...
---+---+---
.2.|.8.|..3
.7.|...|81.
4.8|..9|..6

and reached this point using the Simple Sudoku subset of techniques.

{7} {589} {59} {6} {259} {258} {3} {4} {1}
{18} {4} {6} {35} {357} {18} {257} {9} {25}
{2} {1359} {1359} {579} {4} {15} {6} {8} {57}
{19} {169} {7} {4} {259} {3} {25} {256} { 8}
{389} {389} {4} {259} {6} {25} {1} {2357} {257}
{5} {36} {2} {8} {1} {7} {49} {36} {49}
{169} {2} {159} {157} {8} {46} {49} {57} {3}
{369} {7} {359} {235} {235} {46} {8} {1} {49}
{4} {135} {8} {135} {357} {9} {257} {25} {6}

I drew the bivalue/bilocation diagram but found no cycles or conflicting
pathways of the Eppstein variety even after augmenting it with weak links to bivalue cells.

So I checked it out with Susser to see if that was just me or if all that was left was tabling and Bowman's Bingo (which lets me off the hook). I was surpised to find Bowman's Bingo came up with an incredibly short and simple double implication chain from r5c2:

a) r5c2=9 => r5c1=8
b) r5c2=9 => r4c1<>9 => r4c1=1 => r2c1 <>1 => r2c1=8
Therefore r5c2<>9.

Having had my attention drawn to this I wanted to see if I could reproduce this using Jeff's pattern recognition method based on the bivalue/bilocation diagram. The most obvious path is the one that replicates the implication chain (converted into a single implication one as per Nick70):

(r5c2)-9-(r4c1)-1-(r2c1)=8=(r5c1)=8=(r5c2)

But this breaks the bivalue/bilocation rulebook (as I understand it) in two places with a weak to strong transition at node r2c1 with different labels, and a repeat of the "8" both sides of r5c1.

Looking at Jeff's example chains 1-3 (chain 4 is a repeating cycle a la Eppstein) they set out from the starting block with a weak link of the value whose exclusion is to be tested and return with a different valued strong link. In the current case one would leave with a -9 from r5c2 to r4c1 and arrive back with a strong 8 picking up r5c1 en route. This means that the cycle has to arrive via r8c1. But I could identify no route leading there from r4c1.

Presumably I am misconstruing Jeff's rules in some way, perhaps by following the combined bivalue/bilocation rules that apply to the Eppstein case too slavishly.

Help needed.