Advanced methods and approaches for solving Sudoku puzzles
R8C1<>6 =>R1C1=6 => R3C9=6

R8C1 = 6 => R8C456789 <> 6 => either R7C7 or R9C7 = 6 => R1C7 <>6 => R3C9=6

There.

Stuartn

Last edited by stuartn on Wed Aug 10, 2005 8:41 am, edited 1 time in total.
stuartn

Posts: 211
Joined: 18 June 2005

stuartn wrote:R8C1<>6 =>R1C1=6 => R3C9=6
R8C1 = 6 => R8C456789 <> 6 => either R7C7 or R9C7 = 6 => R1C7 <>6 => R3C9=6

R8C1<>6 =>R1C1=6 ?
... => either R7C7 or R9C7 = 6 => ...
this was the question: is that a forcing chain?
Wolfgang

Posts: 208
Joined: 22 June 2005

Wolfgang wrote:oops, i didnt enter the 6 in the 5 other boxes:

Right then. This cannot be proven by simple forcing chains.
Nick70

Posts: 156
Joined: 16 June 2005

R8C1<>6 =>R1C1=6 ?
... => either R7C7 or R9C7 = 6 => ...
this was the question: is that a forcing chain?

Yes it is. (At the risk of stating the 'bleedin' obvious' (Cleesism) -as the only 6's in box9 are in R7 it discounts the 6 in R1C7.. and any other in the column.

Who said a forcing chain MUST be of directly linked cells? - R8C7 is linked to a Column - rather than a single cell. This IS a chain and it DOES force the six in R3C9 - or is this too inelegant? Rant over

stuartn

Last edited by stuartn on Wed Aug 10, 2005 8:40 am, edited 1 time in total.
stuartn

Posts: 211
Joined: 18 June 2005

After my thoughts have eaten, I propose this notation for discussion:

Code: Select all
` 6  6  6 | 6  6  6 | 6  .  .  .  .  6 | 6  6  6 | .  .  .  .  .  6 | 6  6  6 | .  .  6 ---------+---------+---------  6  6  6 | 6  6  6 | 6  6  6  6  6  6 | 6  6  6 | 6  6  6  6  6  6 | 6  6  6 | 6  6  6 ---------+---------+---------  .  .  . | 6  6  6 | 6 .  .  6  .  . | 6  6  6 | 6  6  6  .  .  6 | 6  6  6 | 6  .  . `

[x&y] is the intersection of units x and y.

[R9&C3]=6 => [B1&C3]<>6 => [B1&R1]=6 => [B3&R1]<>6 => [R3&C9]=6
[R8&C1]=6 => [B9&R8]<>6 => [B9&C7]=6 => [B3&C7]<>6 => [R3&C9]=6
Nick70

Posts: 156
Joined: 16 June 2005

Marvellous. Clarity reigns supreme.

stuartn

stuartn

Posts: 211
Joined: 18 June 2005

stuartn wrote:Clarity reigns supreme.

Not yet, but I think the idea shows promise.
Nick70

Posts: 156
Joined: 16 June 2005

Wolfgang wrote:
Bunnybuck wrote:There is also another trick to colouring, whereby you start case1 with one of the pair of candidate in a unit, finish the chain, and start case2 with a candidate of a different pair of which has NOT been used.

... when from (n in A) follows that (n in B), it does not follow from (n not in A), that (n not in B). I.e. if it is possible that (n not in A) and (n in B), you cannot conclude anything further.

I was just pondering over this issue again today, when i observed that while Wolfgang's statement is true, my colouring 'trick' contains hidden characteristics which makes it true as well.
Code: Select all
` .  .  . | .  .  . | .  .  .  2  . +2 |(2) . (2)| .  .  .  . [2] . | 2  .  2 | .  .  . ---------+---------+---------  . -2  . | . +2  . | .  .  . .  .  . | .  .  . | .  .  .  +2 .  . | . -2  . | .  .  . ---------+---------+---------  . [2] . | 2  .  2 | .  .  .  2  .  2 | 2  .  . |+2  .  .  . +2  . | .  .  . |-2  .  . `

For the first chain, i mentioned:
2 in r8c7 => 2 in r9c2 => 2 in r6c1

However, we also know that
(1) 2 NOT in r8c7 <=> 2 in r9c7
(2) 2 in r6c1 <=> 2 NOT in r4c2
** Note the <=> sign means that they work both ways.

Hence if we were to complete the entire logic chain with (2) included, it would be as follow:
2 in r8c7 => 2 in r9c2 => 2 in r6c1 => 2 NOT in r4c2
Simplifying it: 2 in r8c7 => 2 NOT in r4c2

Now, combining the contrapositive of the simplified equation, ie. 2 in r4c2 => 2 NOT in r8c7 together with (1), we will have:
2 in r4c2 => 2 in r9c7

In mathematical terms, if we have a1 => b1 => c1 and
(1) NOT a1 <=> a2
(2) c1 <=> NOT c2
Then with (2), a1 => NOT c2 and combining its contrapositive, c2 => NOT a1 together with (1) , we will have:
c2 => a2

Hence we can see that with the subtle characteristic of (1) and (2), my trick actually works, which also explains why i have never bumped into any problem when using this technique for over 2 months, even before the term 'colouring' was coined.
Code: Select all
` .  .  . | .  .  . | .  .  .  .  .  2 | .  .  . | .  .  .  .  .  . | .  .  2 | .  .  . ---------+---------+---------  .  .  . | .  2  . | .  .  . .  .  . | .  .  . | .  .  .   2 .  . | .  .  . | .  .  . ---------+---------+---------  .  2  . | .  .  . | .  .  .  .  .  . | 2  .  . | .  .  .  .  .  . | .  .  . | 2 .  . `
So your sample with the 2's also is not correct. Eg it is possible that 2 is in r7c2 (which you eliminated)

Your pattern DOES seem possible, however there MUST be some clues as a result of the position of 2s in block(1,3) and block(2,3), which will eliminate the possibility of this pattern.
Last edited by Bunnybuck on Wed Aug 10, 2005 9:51 am, edited 2 times in total.
Bunnybuck

Posts: 15
Joined: 13 June 2005

This looks very Boolean. Is '&' the only operand that might be useful? - Could NOT and OR have a use?

Nick 70 wrote:

[x&y] is the intersection of units x and y.

[R9&C3]=6 => [B1&C3]<>6 => [B1&R1]=6 => [B3&R1]<>6 => [R3&C9]=6
[R8&C1]=6 => [B9&R8]<>6 => [B9&C7]=6 => [B3&C7]<>6 => [R3&C9]=6
[/quote]
stuartn

Posts: 211
Joined: 18 June 2005

Bunnybuck wrote:Hence if we were to complete the entire logic chain with (2) included, it would be as follow:
2 in r8c7 => 2 in r9c2 => 2 in r6c1 => 2 NOT in r4c2

Uh? I thought the only reason you could possible place a 2 in r6c1 was because of r4c2.

r8c7=2 => r9c7<>2 => r9c2=2 => r4c2<>2 => r6c1=2

Bunnybuck wrote:Now if we combine the contrapositive of the simplified equation, ie. 2 in r4c2 => 2 NOT in r8c7 together with (1), we will have:
2 in r4c2 => 2 in r8c7

Surely you mean 2 in r4c2 => 2 NOT in r8c7
Nick70

Posts: 156
Joined: 16 June 2005

Looking again at an earlier example...

Code: Select all
`. . . | 3 . . | . 3 . . . . | . . . | . . . . . . | . 3 . | . 3 3 ------+-------+------ 3 . . | . 3 . | . 3 . 3 . . | . . 3 | . . 3 3 . 3 | . 3 . | . . . ------+-------+------ . . 3 | . . 3 | . . . 3 . 3 | 3 . . | . . . . . . | . . . | . . . `

B6R5=3 => B5R5<>3 => B5C5=3 => B2C5<>3
B6C8=3 => B3C8<>3 => B3R3=3 => B2R3<>3 ===> R3C5<>3

B5C5=3 => B2C5<>3 => B2R1=3 => B3R1<>3
B5R5=3 => B6R5<>3 => B6C8=3 => B3C8<>3 ===> R1C8<>3
Last edited by Nick70 on Thu Nov 24, 2005 9:05 am, edited 2 times in total.
Nick70

Posts: 156
Joined: 16 June 2005

Nick70 wrote:Surely you mean 2 in r4c2 => 2 NOT in r8c7

Yep i meant 2 in r4c2 => 2 NOT in r8c7, hence 2 in r4c2 => 2 in r9c7. I've punched myself and corrected the error. Thanks for the observation.
Bunnybuck

Posts: 15
Joined: 13 June 2005

Bunnybuck wrote:2 in r8c7 => 2 in r9c2 ...

(sigh) no
true is:
r8c7=2 => r6c1 = 2 <=> r4c2 <> 2
r4c2=2 => r9c7=2 <=> r8c7<>2
not true is:
r8c7=2 => r9c2=2
r6c1=2 => r9c2=2

Your pattern DOES seem possible, however there MUST be some clues as a result of the position of 2s in block(1,3) and block(2,3), which will eliminate the possibility of this pattern.

No, this is possible (from the 2-canditates):
Code: Select all
` .  .  . | .  .  . | .  .  2  .  .  2 | .  .  . | .  .  .  .  .  . | .  .  2 | .  .  . ---------+---------+---------  .  .  . | .  2  . | .  .  . .  .  . | .  .  . | .  2  .   2 .  . | .  .  . | .  .  . ---------+---------+---------  .  2  . | .  .  . | .  .  .  .  .  . | 2  .  . | .  .  .  .  .  . | .  .  . | 2 .  . `

Edit: (but you can eliminate r2c4 and r2c6) - Edit2: oh no, same mistake
Wolfgang

Posts: 208
Joined: 22 June 2005

Nick70 wrote:B6R5=3 => B5R5<>3 => B5C6=3 => B2C6<>3

i like the notation, but i am still confused, what a forcing chain is and what not. Do you have a notation that makes use of pairs also ? Something for
r3c9=7 => r3c1={8,9}
with r1c2={8.9}
-> r2c1<>9
i could not find a good definition for (simple, double, multiple ..) forcing chains.
Questions:
Are some "auxiliary logical steps" allowed?
Must one node follow directly from the preceding alone or maybe from all steps before (eg when you have A{1.2}B{1,3}C{1,2,3}, how do you call a forcing chain A=1->B=3->C=2)?
Wolfgang

Posts: 208
Joined: 22 June 2005

Wolfgang wrote:i like the notation, but i am still confused, what a forcing chain is and what not. Do you have a notation that makes use of pairs also ? Something for
r3c9=7 => r3c1={8,9}
with r1c2={8.9}
-> r2c1<>9

Not yet.

Wolfgang wrote:i could not find a good definition for (simple, double, multiple ..) forcing chains.

I don't think I have seen one.

To me,

simple forcing chain: a chain of alternating true and false possibles, where each implication derives exclusively from the last step, not from the previous ones.

double forcing chain: two simple forcing chains, each one starting in one of two possibles, at least one of which must be true.

multiple forcing chain: like a double forcing chain but with more than two chains.

The box/line intersection chain I have introduced above is something new which I had never seen before and which doesn't fall in the above categories.

Wolfgang wrote:Are some "auxiliary logical steps" allowed?

Not for simple forcing chains.

Wolfgang wrote:Must one node follow directly from the preceding alone or maybe from all steps before (eg when you have A{1.2}B{1,3}C{1,2,3}, how do you call a forcing chain A=1->B=3->C=2)?

I have not studied that kind of chains yet. I don't consider them simple forcing chains.
Nick70

Posts: 156
Joined: 16 June 2005

PreviousNext