## Who can solve this...

Advanced methods and approaches for solving Sudoku puzzles

### Who can solve this...

but not by trial&error
+---+---+---+
|142|536|789|
|758|...|..6|
|963|...|25.|
+---+---+---+
|279|685|1..|
|384|192|675|
|516|473|928|
+---+---+---+
|42.|36.|...|
|637|...|..2|
|89.|..4|.6.|
+---+---+---+
wuem

Posts: 3
Joined: 23 August 2005

Karyobin

Posts: 396
Joined: 18 June 2005

R2C5 can't be a 4. The chain bombs out at R3C9 - and it all falls apart after that.

stuartn
Last edited by stuartn on Wed Aug 24, 2005 2:06 pm, edited 1 time in total.
stuartn

Posts: 211
Joined: 18 June 2005

This grid can be solved logically in 2 steps:

1) xyz-wing: r2c6-r8c6-r8c4:19-189-89 => r7c6<>9 => r7c8=9 => r8c8=14

2) xyz-chain: xyz-wing=r8c8-r2c8-r2c7:14-143-43, but when r8c8=4, r4c9=4, therefore elimination footprint is extended to column 9 => r3c9<>4

The rest is simple.
Jeff

Posts: 708
Joined: 01 August 2005

Consider the chains r8c7-4-r8c8 and r8c7-4-r2c7-3-r2c8-3-r4c8~4~r8c8.
When the r8c7 doesn't contain the value 4, one chain states that the r8c8 contains the value 4 while the other says it doesn't - a contradiction.
Therefore, the r8c7 must contain the value 4.
Sue De Coq

Posts: 93
Joined: 01 April 2005

Sue - any chance of re-posting using the same operands as Jeff? It'll make it clearer for all. Ta everso

stuartn
stuartn

Posts: 211
Joined: 18 June 2005

Assume r8c7<>4.

A. r8c7-r8c8:458-149 so r8c7<>4 => r8c8=4
B. r8c7-r2c7-r2c8-r4c8-r8c8:458-34-134-34-149 so r8c7<>4 => r2c7=4 => r2c7<>3 => r2c8=3 => r4c8<>3 => r4c8=4 => r8c8<>4.

A and B are contradictory, so the initial assumption must be false.

I hope that's clearer.
Sue De Coq

Posts: 93
Joined: 01 April 2005

Sue

An example for better expression of double forcing chains is:
Code: Select all
`r8c8=5 => r8c1<>5 r8c8=4 => r8c3=7 => r9c1=5 => r8c1<>5 Therefore, r8c1<>5.`
Jeff

Posts: 708
Joined: 01 August 2005

Using the notation and ideas here, Sue's chain can be written
Code: Select all
`[A,87:4*] <4> [88:4*] <-4> [48:43] <-3> [28:3*] <3> [27:34] <4> [B,87:4*]`
From the end labels of this chain you can quickly read off the relation it enforces, "A=4 or B=4". Since A=B=r8c7, this chain proves r8c7=4.

This can also be expressed logically as a double implication chain starting from anywhere in the middle, or as a contradiction starting from either end of the chain. All such choices are arbitrary, so I really like this way of clearly showing a forcing chain and its effect indepent of any implication chain derived from it.

This puzzle seems to have many forcing chains. Another is
Code: Select all
`[A,28:3*] <-3> [27:34] <-4> [39:4*] <4> [49:43] <3> [48:3*] <-3> [B,28:3*]`
forcing "A<>3 or B<>3". Since A=B=r2c8 this proves r2c8<>3.
Scott H

Posts: 73
Joined: 28 July 2005

Another way -

Assume 3,5 <>4

=> 3,9 = 4 => 4,9 = 3 and 2,7 = 3 and 2,8 <> 3
=> 2,8 = 1 and 4,8 = 3 - which is inconsistent - 4,9 and 4,8 can't both be 3.

How would you write that using the terminology above? (and joining the nodes we get what looks suspiciously like a tadpole - I therefore have the honour of christening this shape... blah blah..)

stuartn

stuartn

Posts: 211
Joined: 18 June 2005

stuartn wrote:Another way -

Assume 3,5 <>4

=> 3,9 = 4 => 4,9 = 3 and 2,7 = 3 and 2,8 <> 3
=> 2,8 = 1 and 4,8 = 3 - which is inconsistent - 4,9 and 4,8 can't both be 3.

How would you write that using the terminology above?

I'd first note 3,5 is peripheral to the reasoning, so the deductions might as well start at 3,9. When you exclude or include a candidate, two or more chains meet there or a chain starts and ends there. Here, 3,9=4 causes your contradiction, so look for chains from 3,9. A contradiction like "both nodes in a row can't be 3" mean there's a 3 or -3 edge in a forcing chain between those nodes. Note that your internal inference 2,8=1 is unneeded, since 2,8<>3 => 4,8=3 already. Throwing out the 2,8=1 red herring, your forcing chain is
Code: Select all
`[A,3,9:4*] <-4> [27:43] <-3> [28:3*] <3> [48:3*] <-3> [49:34] <-4> [A:4*]`
The chain enforces A<>4 or A<>4, i.e. A=r3c9<>4.
Scott H

Posts: 73
Joined: 28 July 2005