The New Sudoku Players' Forum

[Addlan]

I wonder if anyone can solve the Sudoku below. It will be interesting to see how long it will take people to solve the puzzle. I submit it 3.00pm 15, July, 2005, british time.

...|.2.|.8.
1.9|..5|3..
7..|..4|1.5
-----------
...|64.|5..
9..|...|..8
..3|.92|...
-----------
..2|...|..1
..1|4..|2.3
.6.|.5.|...

Hint, you may need "try and error" scheme at a point.

[scrose]

Note that there are two ways to make this puzzle easier. Highlight the text below to reveal the clues.

• Make the puzzle symmetrical by placing a 5 at r7c1 and a 3 at r7c4.
• Or place a 8 at r9c7.

[Addlan]

Wow, you are very quick and make a good suggestion. Amazing!!!

[scrose]

I haven't yet managed to solve it without guessing. I've been trying to apply the forcing chains technique but no success thus far.

[Addlan]

All right. See if you can come up with a solution without guessing. Personally I don't like guessing as well.

[Addlan]

[Nick70]

It can be solved using double forcing chains.

[Addlan]

Wow, Double forcing chain? what is it? Could you give me an example?

It seems very hard to generate a Sudoku matrix which can only be solved by "try and error". Hope programmers can hurry up and generate superb Sudoku matrixes.

[Nick70]

A double forcing chain is two sequences of implications that, starting from the only two possible numbers that can be placed in a cell, or the only two places in a unit where a number can be, both end assigning the same value to a cell.

Example (from the problem above):

Code: Select all

iteration #18 (41 cells left to go)
matrix state:
456   3     45     | 1     2     79     | 479   8     467   
1     48    9      | 78    678   5      | 3     467   2     
7     2     68     | 389   368   4      | 1     69    5     
-------------------+--------------------+-------------------
2     1     78     | 6     4     78     | 5     3     9     
9     457   4567   | 357   1     37     | 467   2     8     
4568  4578  3      | 578   9     2      | 47    1     467   
-------------------+--------------------+-------------------
458   45789 2      | 3789  378   36789  | 4678  4567  1     
58    5789  1      | 4     78    6789   | 2     567   3     
3     6     478    | 2     5     1      | 4789  479   47   
Found a double forcing chain:
(3,8)=6 => (8,8)<>6 => (8,6)=6 => (8,6)<>9 => (8,2)=9
(3,8)=9 => (1,7)<>9 => (1,6)=9 => (8,6)<>9 => (8,2)=9
  - Put 9 in (8,2)

[Anette]

I'm comparing to my grid so far, and have the same firm numbers in there but have not managed to eliminate as many candidatges as you have. How did you eliminate m6 from R1C6? And from several other places?

[Addlan]

Using X-wing. Basically two rows and two columns got to have two numbers of each digit, so on so forth. If you look at r1c1, r1c9, r6c1 and r6c9, they all got digit '6' and nowhere else in the two columns, which indicates nowhere else should the two rows have digit '6'. Please refer to http://www.angusj.com/sudoku/hints.php. Why not try the software Simple Sudoku to solve it?

[fizx1]

635127984
149865372
728934165
217648539
956713428
483592716
572389641
891476253
364251897

[simes]

A double forcing chain is two sequences of implications that, starting from the only two possible numbers that can be placed in a cell...

Then what's a single forcing chain? To my way of thinking a forcing chain results in a placement from considering either combination in some particular cell. Otherwise the placement is just not forced. Now I know that technique as a "forcing chain". But why double?

[Nick70]

Then what's a single forcing chain? To my way of thinking a forcing chain results in a placement from considering either combination in some particular cell. Otherwise the placement is just not forced. Now I know that technique as a "forcing chain". But why double?

Well, to me a "forcing chain" means:

If this happens then this happens then this happens then this happens then this happens.

Which is only one of the two implication chains that you need to prove that a cell contains a specific number.


You can place a number with a single forcing chain by finding a contradiction:

(1,1)<>1 => (1,4)=1 => .... => (1,1)=1

so you have proven that (1,1)=1

I haven't studied this thoroughly yet because I concentrated on double forcing chains. But of course, a single forcing chain should be considered simpler than double forcing chains?

[Nick70]

I haven't studied this thoroughly yet because I concentrated on double forcing chains. But of course, a single forcing chain should be considered simpler than double forcing chains?

Well well. All work and no play makes Jack a dull boy.

Let's look again at the double forcing chain above.

Code: Select all

(3,8)=6 => (8,8)<>6 => (8,6)=6 => (8,6)<>9 => (8,2)=9
(3,8)=9 => (1,7)<>9 => (1,6)=9 => (8,6)<>9 => (8,2)=9

There is a very simple thing that I overlooked.

If A => B, then (not B) => (not A).

So we can reverse one of the two chains above, e.g. the first one:

Code: Select all

(8,2)<>9 => (8,6)=9 => (8,6)<>6 => (8,8)=6 => (3,8)<>6

And of course, since the first terms of the two chains are conjugate, after the reversal we can join the two chains together:

Code: Select all

(8,2)<>9 => (8,6)=9 => (8,6)<>6 => (8,8)=6 => (3,8)<>6 =>(3,8)=9 => (1,7)<>9 => (1,6)=9 => (8,6)<>9 => (8,2)=9

This applies to all "double" forcing chains. So every double forcing chain is just a single forcing chain in disguise.

What about the opposite? Is it true as well that every single forcing chain can be split into a double forcing chain?

Yes, it is. Let's look at a sample single forcing chain, e.g.:

Code: Select all

(9,4)=3 => (3,4)<>3 => (3,9)=3 => (2,7)<>3 => (9,7)=3 => (9,4)<>3

All we need to split it is a pair of conjugate possibilities. Note that there is no guarantee that the two possibilities in the middle of the chain ((3,9)=3 and (2,7)=3) are conjugate, because the first one is true, and two possibilities are conjugate only if one being false implies the other being true. But we don't have to split the chain in the middle. We can pick the second and third possibilities, which are conjugates, obtaining this double chain:

Code: Select all

(3,4)=3 => (9,4)<>3
(3,9)=3 => (2,7)<>3 => (9,7)=3 => (9,4)<>3

Actually, I didn't say the whole truth. I could have split it in the middle anyway:

Code: Select all

(3,9)<>3 => (3,4)=3 => (9,4)<>3
(2,7)<>3 => (9,7)=3 => (9,4)<>3

The two first terms are not conjugate, so there is no guarantee that one of them is true, but we don't care! Because the chains start with them being false, and we can be sure that at least one of them will be false - maybe even both of them.

So a single forcing chain or a double forcing chain are just two ways to see the same thing.
The double chain is probably more pleasing to the eye, however the single chain is probably more formally appropriate.