looking for tip please

Advanced methods and approaches for solving Sudoku puzzles

Postby Nick67 » Sat Sep 10, 2005 11:39 am

Jeff wrote:Nick67

What is the relationship of the 3s in r5c6 and r8c3?


I don't see it ... is there a chain?
Can you please point it out? Thanks much.
Nick67
 
Posts: 113
Joined: 24 August 2007

Postby Jeff » Sat Sep 10, 2005 4:30 pm

Nick67 wrote:
Code: Select all
7     58    1    |     2     3     9    |    6     4    58

6     38    2    |     1     4     5    |    389   89   7

35    4     9    |     8     6     7    |    23    1    25

----------------------------------------------------------
4     123  38    |     369   5    136   |    289   7    289
      BB                          A
9     235  357   |     37    8    34    |    24    6    1
      A                           AB         BA   
18    6    78    |     79    2    14    |    489   5    3
AB                                BA         B
----------------------------------------------------------
35    9    356   |     36    1    8     |    7     2    4

128  13    368   |     4     7    236   |    5     389  89
B    AB
28   7     4     |     5     9    23    |    1     38   6


I beg your pardon. I meant to ask about the relationship of the 3s in r5c6 and r8c2?
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Nick67 » Sat Sep 10, 2005 5:11 pm

Jeff wrote:
Nick67 wrote:
Code: Select all
7     58    1    |     2     3     9    |    6     4    58

6     38    2    |     1     4     5    |    389   89   7

35    4     9    |     8     6     7    |    23    1    25

----------------------------------------------------------
4     123  38    |     369   5    136   |    289   7    289
      BB                          A
9     235  357   |     37    8    34    |    24    6    1
      A                           AB         BA   
18    6    78    |     79    2    14    |    489   5    3
AB                                BA         B
----------------------------------------------------------
35    9    356   |     36    1    8     |    7     2    4

128  13    368   |     4     7    236   |    5     389  89
B    AB
28   7     4     |     5     9    23    |    1     38   6


I beg your pardon. I meant to ask about the relationship of the 3s in r5c6 and r8c2?


r6c1=1 --> r6c6=4 --> r5c6 = 3
r6c1=1 --> r8c1 <> 1 --> r8c2 =1 --> r8c2 <> 3

Similarly,

r6c1<>1 eventually implies that r5c6 <> 3
r6c1<>1 eventually implies that r8c2 = 3

So, those two 3s get "opposite" colors.

BTW, I wonder if this approach is equivalent
to chaining approaches? I don't know the
chaining approaches well enough to say.
Nick67
 
Posts: 113
Joined: 24 August 2007

Postby MikeF » Sat Sep 10, 2005 6:16 pm

Jeff wrote:MikeF

Actually, xy-wing, xy-chain, xyz-wing and xyz-chains are much easier to spot than x-wing, swordfish, turbot fish and colours (some people may disagree), techniques I am sure you would consider logical. This is because the formers don't require any filtering and are therefore most suitable for direct pencil/rubber on newspaper application. It all comes down to practice as to how many of these patterns you could spot in a puzzle.

As to forcing chains, it can be T&E, but then again can be not T&E at all. It hinges on whether you have a system to identify these chains. Forcing chain itself is not T&E, but usually the process of finding these chains can be T&E. Using a bilocation/bivalue combination plot, coupled with a set of proven rules, I can identify forcing chains without T&E. It is a time consuming process, but in return you would enjoy full satisfaction for being able to solve the puzzle logically.


Jeff: I know about XY-wing (from www.simes.clara.co.uk site) but am not familiar with xy-chain, xyz-wing and xyz-chains. Can point me please to an explanation of these?

Also, am interested in your "bilocation/bivalue combination plot, coupled with a set of proven rules." If I ever get to a point where I master the xy- chain and other strategies mentioned above, would love to hear about these. Tnx.

Mike
MikeF
 
Posts: 11
Joined: 07 September 2005

Postby Jeff » Sat Sep 10, 2005 7:48 pm

Nick67 wrote:BTW, I wonder if this approach is equivalent to chaining approaches?

Thank you, Nick67. Nick70 described the technique as Advanced Colouring and it is indeed very powerful. It is a kind of chain which I would rate one above the pure bilocation chain. Being more powerful, it has more constraints too. Apart from the requirement that all links must be conjugates, bivalue nodes are also required when a number is carried forward to another, except for the node where the contradition takes place. The number of links for each number is also significant.

For easy reference, I list your advanced colour chain as follows:

[4,2:1A]=[4,6:1B]=[6,6:1A:4B]=[5,6:4A]=[5,7:4B:2A]=[5,2:2B]=[4,2:2A] => A is false => B is true.

where '=' stands for conjugate link, and in the first node: '4,2' means r4c2, '1' is the number and 'A' is the colour.

As you can see, nodes 6,6 and 5,7 are bivalue.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Jeff » Sat Sep 10, 2005 8:08 pm

MikeF
xyz-wing: refer here and here.
xyz-chain: refer here and here.
xy-chains: refer here, here and here.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby MikeF » Sun Sep 11, 2005 2:36 am

many thanks Jeff. will study those.

Mike
MikeF
 
Posts: 11
Joined: 07 September 2005

Postby Jeff » Wed Sep 14, 2005 6:27 am

Jeff wrote:
Nick67 wrote:BTW, I wonder if this approach is equivalent to chaining approaches?

Thank you, Nick67. Nick70 described the technique as Advanced Colouring and it is indeed very powerful. It is a kind of chain which I would rate one above the pure bilocation chain. Being more powerful, it has more constraints too. Apart from the requirement that all links must be conjugates, bivalue nodes are also required when a number is carried forward to another, except for the node where the contradition takes place. The number of links for each number is also significant.

For easy reference, I list your advanced colour chain as follows:

[4,2:1A]=[4,6:1B]=[6,6:1A:4B]=[5,6:4A]=[5,7:4B:2A]=[5,2:2B]=[4,2:2A] => A is false => B is true.

where '=' stands for conjugate link, and in the first node: '4,2' means r4c2, '1' is the number and 'A' is the colour.

As you can see, nodes 6,6 and 5,7 are bivalue.

I have given a bit more thought on the advanced colourng technique and can now confidently say that it is equivalent to the double implication forcing chain technique. Double implication forcing chain propagate by means of a combination of bilocation links and bivalue links, which are equivalent to the conjugate cells and bivalue node (where one number is carried forward to the next) in advanced colouring respectively. The chains corresponding with your example are listed below for comparison.

r4c6=1 => r4c2<>1
r4c6<>1 => r6c6=1 => r5c6=4 => r5c7=2 => r5c2<>2 => r4c2=2 =>r4c2<>1
Therefore r4c2<>1

r4c6=<>1 => r4c2=1 => r4c2<>2
r4c6=1 => r6c6=4 => r5c6<>4 => r5c7=4 => r5c2=2 => r4c2<>2
Therefore r4c2<>2
Last edited by Jeff on Wed Sep 14, 2005 4:08 am, edited 1 time in total.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Nick67 » Wed Sep 14, 2005 7:40 am

Jeff,

Thanks very much for making the connection between
the 2 techniques, and your many other insights in this thread.

1 minor question about your post.
Let me first bring back the puzzle for ease of reference:

Code: Select all
7     58    1    |     2     3     9    |    6     4    58
6     38    2    |     1     4     5    |    389   89   7
35    4     9    |     8     6     7    |    23    1    25
----------------------------------------------------------
4     123  38    |     369   5    136   |    289   7    289
9     235  357   |     37    8    34    |    24    6    1
18    6    78    |     79    2    14    |    489   5    3
----------------------------------------------------------
35    9    356   |     36    1    8     |    7     2    4
128  13    368   |     4     7    236   |    5     389  89
28   7     4     |     5     9    23    |    1     38   6



You gave the following 4 chains:

1: r4c6=1 => r4c2<>1
2: r4c6<>1 => r6c6=1 => r5c6=4 => r5c7=2 => r5c2<>2 => r4c2=2 =>r4c2<>1

3: r4c6=<>1 => r4c2=1 => r4c2<>2
4: r4c6=1 => r6c6=4 => r5c6<>4 => r5c7=4 => r5c2=2 => r4c2<>2 =>r4c2<>1


Does the 4th chain have an extra implication at the end?
In other words, I don't see how r4c2 <> 2 => r4c2 <> 1.
It seems that you could leave out that last implication,
and your proof would still be correct.
That is, chains 1 and 2 together imply that r4c2 <> 1,
and chains 3 and 4 (w/o that last implication)
together imply that r4c2 <> 2,
and finally we can conclude that r4c2 = 3.
(But I apologize if I'm just not reading your proof correctly ...)
Nick67
 
Posts: 113
Joined: 24 August 2007

Postby Jeff » Wed Sep 14, 2005 8:07 am

Nick67 wrote:You gave the following 4 chains:

1: r4c6=1 => r4c2<>1
2: r4c6<>1 => r6c6=1 => r5c6=4 => r5c7=2 => r5c2<>2 => r4c2=2 =>r4c2<>1

3: r4c6=<>1 => r4c2=1 => r4c2<>2
4: r4c6=1 => r6c6=4 => r5c6<>4 => r5c7=4 => r5c2=2 => r4c2<>2 =>r4c2<>1

Does the 4th chain have an extra implication at the end?

Firstly, there are only 2 chains, not 4 chains; or you may say 2 double implication chains, since each chain forces the same result in two (opposite) directions.

The extra implication at the end is just a cut and paste mistake. The chain should read:

r4c6=<>1 => r4c2=1 => r4c2<>2
r4c6=1 => r6c6=4 => r5c6<>4 => r5c7=4 => r5c2=2 => r4c2<>2
Therefore r4c2<>2

Original post edited.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Jeff » Wed Sep 14, 2005 8:52 am

Nick67 wrote:Thanks very much for making the connection between the 2 techniques

On the same grid, I have identified a closed chain as shown below:

Image

which enables the removal of a 3 in r4c6, a 3 in r8c6 and an 8 in r8c1.
I leave it to you to construct an advanced colour table corresponding to this chain?:D
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Nick67 » Wed Sep 14, 2005 5:04 pm

Thanks for finding that chain, Jeff.
The following color table is based on your diagram.
The logic following the table identifies the
same 3 eliminations that you described.
This result seems to back up your point that
the advanced colouring technique is equivalent
to the double implication forcing chain technique.

Code: Select all
7     58    1    |     2     3     9    |    6     4    58

6     38    2    |     1     4     5    |    389   89   7

35    4     9    |     8     6     7    |    23    1    25

----------------------------------------------------------
4     123  38    |     369   5    136   |    289   7    289
      B                           AGF
9     235  357   |     37    8    34    |    24    6    1
 
18    6    78    |     79    2    14    |    489   5    3
AB
----------------------------------------------------------
35    9    356   |     36    1    8     |    7     2    4

128  13    368   |     4     7    236   |    5     389  89
BCK                               DIE
28   7     4     |     5     9    23    |    1     38   6


from (8,1) and (8,6), we have B -> (not C) -> D
from (8,6) we have D -> (not I)
so ... B -> (not I)

from (4,6) and (8,6) we have A -> (not F) -> E
from (8,6) we have E -> (not I)
so ... A -> (not I)

Thus, (not I) must be true. I must be false.

from (8,6) and (4,6) we have D -> (not E) -> F
from (4,6) we have F -> (not G)
so ... D -> (not G)

from (8,1) and (6,1) we have C -> (not B) -> A
from (4,6) we have A -> (not G)
so ... C -> (not G)

Thus, (not G) must be true. G must be false.

from (8,1) we have B -> (not K)

from (4,6) and (8,6) we have A-> (not F) -> E
from (8,6) and (8,1) we have E -> (not D) -> C
from (8,1) we have C -> (not K)
so ... A -> (not K)

Thus, (not K) must be true. K must be false.

One minor note: The 3 candidate eliminations here
do not quite seem to be enough to solve the puzzle.
But I am guessing that they lead directly to
a further reduction.
Nick67
 
Posts: 113
Joined: 24 August 2007

Postby Jeff » Thu Sep 15, 2005 2:59 am

Nick67 wrote:
Code: Select all
7     58    1    |     2     3     9    |    6     4    58

6     38    2    |     1     4     5    |    389   89   7

35    4     9    |     8     6     7    |    23    1    25

----------------------------------------------------------
4     123  38    |     369   5    136   |    289   7    289
      B                           AGF
9     235  357   |     37    8    34    |    24    6    1
 
18    6    78    |     79    2    14    |    489   5    3
AB
----------------------------------------------------------
35    9    356   |     36    1    8     |    7     2    4

128  13    368   |     4     7    236   |    5     389  89
BCK                               DIE
28   7     4     |     5     9    23    |    1     38   6

Nice work! Few questions to clear my mind.

Is it essential to label non-conjugate candidates such as the 3s in r4c6 and r8c6?
Is there a way (or is there a need) to distinguish non-conjugate from conjugate candidates?
Can elimination be observed without outlining the proofs and what will be the process going through your mind?

The reason for the third question is that some people regard this kind of method as bifurcation every time when a proof is presented. However, if the logic can be observed directly from the table, then we only need to prove it once for understanding purpose.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Nick70 » Thu Sep 15, 2005 7:48 am

Jeff wrote:Can elimination be observed without outlining the proofs and what will be the process going through your mind?

Colouring is a purely iterative process. No bifurcation is involved.

Please see this post for a detailed description of the algorithm.

It is actually quite difficult to trace back the steps of the colouring algorithm to isolate the simplest forcing chain.
Nick70
 
Posts: 156
Joined: 16 June 2005

Postby Jeff » Thu Sep 15, 2005 10:50 am

Thanks Nick, excellent technique. Your post describe the computer algorithm for the advanced colouring technique. I am more interested in how this technique can be applied at a manual level. Perhaps you can walk through with us the thinking process of how deductions are to be observed from the table of the previous example.
Jeff
 
Posts: 708
Joined: 01 August 2005

PreviousNext

Return to Advanced solving techniques