An extremely fiendish Sudoku

Advanced methods and approaches for solving Sudoku puzzles

An extremely fiendish Sudoku

Postby Addlan » Fri Jul 15, 2005 2:21 pm

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.
Addlan
 
Posts: 62
Joined: 15 July 2005

Postby scrose » Fri Jul 15, 2005 2:39 pm

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.
scrose
 
Posts: 322
Joined: 31 May 2005

Postby Addlan » Fri Jul 15, 2005 2:49 pm

Wow, you are very quick and make a good suggestion. Amazing!!!
Addlan
 
Posts: 62
Joined: 15 July 2005

Postby scrose » Fri Jul 15, 2005 2:52 pm

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.
scrose
 
Posts: 322
Joined: 31 May 2005

Postby Addlan » Fri Jul 15, 2005 3:00 pm

All right. See if you can come up with a solution without guessing. Personally I don't like guessing as well.
Addlan
 
Posts: 62
Joined: 15 July 2005

Postby Addlan » Fri Jul 15, 2005 4:18 pm

:idea:
Addlan
 
Posts: 62
Joined: 15 July 2005

Postby Nick70 » Fri Jul 15, 2005 5:12 pm

It can be solved using double forcing chains.
Nick70
 
Posts: 156
Joined: 16 June 2005

Postby Addlan » Fri Jul 15, 2005 5:27 pm

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.
Addlan
 
Posts: 62
Joined: 15 July 2005

Postby Nick70 » Fri Jul 15, 2005 7:21 pm

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)
Nick70
 
Posts: 156
Joined: 16 June 2005

Postby Anette » Fri Jul 15, 2005 7:53 pm

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?
Anette
 
Posts: 55
Joined: 09 June 2005

Postby Addlan » Fri Jul 15, 2005 8:18 pm

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?
Addlan
 
Posts: 62
Joined: 15 July 2005

Solved

Postby fizx1 » Fri Jul 15, 2005 9:13 pm

635127984
149865372
728934165
217648539
956713428
483592716
572389641
891476253
364251897
fizx1
 
Posts: 3
Joined: 15 July 2005

Postby simes » Fri Jul 15, 2005 11:24 pm

Nick70 wrote: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?
Last edited by simes on Sun Dec 11, 2011 9:36 am, edited 1 time in total.
simes
 
Posts: 324
Joined: 11 March 2005
Location: UK

Postby Nick70 » Sat Jul 16, 2005 7:57 am

simes wrote: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
 
Posts: 156
Joined: 16 June 2005

Postby Nick70 » Sat Jul 16, 2005 9:03 pm

Nick70 wrote: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.
Nick70
 
Posts: 156
Joined: 16 June 2005


Return to Advanced solving techniques