stuck

Advanced methods and approaches for solving Sudoku puzzles

Postby cho » Sat Nov 12, 2005 3:58 am

Perhaps I just don't get what's new about this. It seems like a few techniques I've seen lately that you are just trying a limited branch to see what shakes out. Unless there is a reason for placing a 4 in R2C1 it's just T&E. Said placement quickly leads to an invalid puzzle - three 16 pairs in C3. It's all deduction based on "what if". Not that I view that as inappropriate necessarily as some do, it just isn't new.

If R2C1 = 4 -> R3C1 = 3, R2C4 = 8 : R1C3 = 16, R2C3 = 16, R5C3 = 16
Therefore R2C1 <> 4
(probably didn't get the shorthand right)

Noting that '3, 4, or 8 must go in one of the two cells' is the obverse of '1 and 6 can't go in both of them' which is obvious. Neither is needed to be known in order to do the test R2C1 = 4, nor do they indicate it as far as I can see. But I've been wrong a time or two here.

cho
cho
 
Posts: 18
Joined: 07 August 2005

Postby Jeff » Sat Nov 12, 2005 7:38 am

Cho, thank you for sharing your thoughts.
Code: Select all
If R2C1 = 4 -> R3C1 = 3, R2C4 = 8 : R1C3 = 16, R2C3 = 16, R5C3 = 16
Therefore R2C1 <> 4

You are right, the forcing net does the trick to prove that r2c1<>4 too. Without any preconceived ideas, one probably had to go through every cell to find it. In fact, there are other chains and nets that can lead to the same outcome; some of them are T&E and some of them are not. Lets not forget that all deductions can be made through one T&E approach or the other.

Once a deduction is presented, a question is often asked on how the deduction was to be identified, and this is what makes the difference between whether the technique is T&E or not. For example:

MikeF asked: ".....I'm wondering what exactly is the pattern to look for in applying this strategy?"
Em asked: ".....Do you have any idea before you start how to pick the key cells?"
vibes1234 asked: ".....could u tell me what is the basis for choosing a particular cell to start the chain ?"

Personally, I classify a technique as non-T&E with 2 criteria:

  • It must have a particular pattern to be recognised with such that the element of 'trial' is removed.
  • It must not require any backtracking such that the element of 'error' is removed.
To explain the processes, I am temporarily referring the 2 techniques as 'Non-cell contradiction' and 'Advanced naked pairs' for easy reference only. These names will be limited to our discussion until better names are finalised.

With 'Non-cell contradiction', the pattern to look for is a target cell with 3 candidates, which can be a single trivalue cell as in xyz-wing, or one of the 2 cells as demonstrated in bennys' example. Next, the chain required to remove all candidates in the target cell is no more than a simple xy-chain. Once the pattern is recognised, the first candidate of the chain can be eliminated.

With 'Advanced naked pairs', the pattern to look for is 2 target cells with 4 candidates in-line in a box or 3 target cells with 5 candidates in-line in a box and then 2 mutually exclusive bivalue cells, one in the same row and one in the same box as the target cells. Once this pattern is recognised, all other candidates in the same row and box due to the implied naked pairs can be eliminated.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby rubylips » Sun Nov 13, 2005 3:10 pm

Personally, I found it helpful to couch this problem in terms of the techniques introduced in the thread I didn't see this argument used before. The cells r3c1, r1c3 and r5c3 form an Almost Disjoint Subset as they will be filled by three values from the set {1,3,4,6}. (Normally, an Almost Disjoint Subset lies within a single sector but the current example is valid because the two cells that don't share a sector - r3c1 and r5c3 - have no common candidate). The cell r2c4 is a trivial Almost Disjoint Subset as it has just the two candidates. The link cell is r2c3, which has four candidates rather than the two that appeared in the link cell examples in the previous thread. However, the logic used is similar. When the cell contains a value from the set {1,6}, a Disjoint Subset is formed in the cells r3c1, r1c3, r2c3 and r5c3 - in fact, two Disjoint Subsets are formed, as the cells r2c3 and r5c3 contain the values {1,6} and the cells r3c1 and r1c3 contain the values {3,4}. The key conclusion drawn here is that when r2c3 contains a value from the set {1,6}, the values 3 and 4 in Box 1 are constrained to the cells r1c3 and r3c1. Now consider what happens when r2c3 contains a value from the set {4,8} - a Disjoint Subset is formed in the cells r2c3 and r2c4, so the values 4 and 8 in Row 2 are constrained to these two cells. It follows that whichever value is taken by the cell r2c3, the value 4 can't be a candidate for the cells r2c1 or r2c2.

I prefer this form of argument because, although the initial pattern is tough to spot (though not necessarily more tough than a forcing net), it proceeds without proof by contradiction and reaches a more general conclusion (the value 4 is excluded from two cells - admittedly, it isn't a candidate for one) than some other arguments posted to the thread.
rubylips
 
Posts: 149
Joined: 01 November 2005

Postby MikeF » Mon Nov 14, 2005 2:29 am

Perhaps we can sum this up as follows:

To proceed with this puzzle, basically we have

a) bennys technique, which Jeff has called Non-Cell Contradiction.

or

b) the deductions outlined by angusj and cho, which some may label as T&E.

Which raises the question, is bennys technique here the only non-T&E method that works?
MikeF
 
Posts: 11
Joined: 07 September 2005

Postby rubylips » Mon Nov 14, 2005 1:24 pm

Mike,

It's not strictly necessary to use one of the techniques discussed in this thread in order to solve the puzzle - it's just a lot easier. Here's the initial part of the solution if we limit ourselves to forcing chains (without tables):

Code: Select all
1. The value 4 in Box 6 must lie in Row 5.
- The moves r4c7:=4 and r4c9:=4 have been eliminated.
The value 7 in Box 1 must lie in Column 2.
- The move r2c3:=7 has been eliminated.
The value 7 in Box 5 must lie in Column 6.
- The moves r4c5:=7 and r6c5:=7 have been eliminated.
The value 9 in Box 1 must lie in Column 2.
- The moves r1c3:=9 and r2c3:=9 have been eliminated.
The values 5 and 7 occupy the cells r4c3 and r6c3 in some order.
- The moves r4c3:=6, r6c3:=1 and r6c3:=6 have been eliminated.
Consider the chain r2c1~6~r2c8-6-r5c8~6~r5c3-6-r6c1.
When the cell r2c1 contains the value 6, so does the cell r6c1 - a contradiction.
Therefore, the cell r2c1 cannot contain the value 6.
- The move r2c1:=6 has been eliminated.
Consider the chain r8c4-3-r6c4~3~r5c6-1-r5c3~6~r5c8-6-r2c8-2-r8c8.
When the cell r8c8 contains the value 3, some other value must occupy the cell r8c4, which means that the value 2 must occupy the cell r8c8 - a contradiction.
Therefore, the cell r8c8 cannot contain the value 3.
- The move r8c8:=3 has been eliminated.
Consider the chain r8c4-3-r6c4~3~r5c6-1-r5c3-1-r6c1-1-r2c1~4~r2c4~8~r8c4.
When the cell r8c4 contains the value 8, it likewise contains the value 3 - a contradiction.
Therefore, the cell r8c4 cannot contain the value 8.
- The move r8c4:=8 has been eliminated.
Consider the chain r2c1-1-r6c1-6-r7c1~6~r7c2~8~r3c2-8-r3c5~8~r2c4~4~r2c1~1~r2c3.
When the cell r2c3 contains the value 1, so does the cell r2c1 - a contradiction.
Therefore, the cell r2c3 cannot contain the value 1.
- The move r2c3:=1 has been eliminated.
Consider the chain r6c1-6-r7c1~6~r7c2~8~r3c2-8-r3c5~8~r2c4~4~r2c1-1-r6c1~6~r6c4.
When the cell r6c4 contains the value 6, so does the cell r6c1 - a contradiction.
Therefore, the cell r6c4 cannot contain the value 6.
- The move r6c4:=6 has been eliminated.
Consider the chain r2c8~4~r2c4~8~r6c4~3~r5c6-1-r5c3~6~r5c8-6-r2c8.
When the cell r2c8 contains the value 4, it likewise contains the value 6 - a contradiction.
Therefore, the cell r2c8 cannot contain the value 4.
- The move r2c8:=4 has been eliminated.
Consider the chain r2c7-1-r2c1-1-r6c1-1-r5c3-1-r5c6~3~r6c4~8~r2c4~4~r2c7.
When the cell r2c7 contains the value 4, it likewise contains the value 1 - a contradiction.
Therefore, the cell r2c7 cannot contain the value 4.
- The move r2c7:=4 has been eliminated.
Consider the chain r4c4~8~r6c4~3~r5c6-1-r5c3-1-r6c1-1-r2c1~4~r2c4-4-r4c4.
When the cell r4c4 contains the value 8, it likewise contains the value 4 - a contradiction.
Therefore, the cell r4c4 cannot contain the value 8.
- The move r4c4:=8 has been eliminated.
Consider the chain r6c6~3~r5c6-1-r5c3-1-r1c3-1-r2c1~4~r2c4-8-r6c4~3~r6c6.
When the cell r6c6 contains the value 3, the chain is self-contradicting.
Therefore, the cell r6c6 cannot contain the value 3.
- The move r6c6:=3 has been eliminated.
Consider the chain r6c5~3~r5c6-1-r5c3-1-r1c3-1-r2c1~4~r2c4-8-r6c4~3~r6c5.
When the cell r6c5 contains the value 3, the chain is self-contradicting.
Therefore, the cell r6c5 cannot contain the value 3.
- The move r6c5:=3 has been eliminated.
Consider the chain r2c1-1-r6c1-1-r5c3-1-r5c6-3-r6c4-8-r2c4.
The cells r2c1 and r2c4 contain one value from the set {1,8} and the value 4.
The value 4 occupies 1 of the cells r2c1 and r2c4.
- The moves r2c3:=4 and r2c5:=4 have been eliminated.
The values 1, 3 and 4 occupy the cells r1c3, r2c1 and r3c1 in some order.
- The move r1c3:=6 has been eliminated.
Consider the chain r1c7-6-r1c2~6~r2c3~8~r2c4-8-r6c4-3-r6c7.
When the cell r6c7 contains the value 6, some other value must occupy the cell r1c7, which means that the value 3 must occupy the cell r6c7 - a contradiction.
Therefore, the cell r6c7 cannot contain the value 6.
- The move r6c7:=6 has been eliminated.
Consider the chain r6c4-8-r2c4-4-r2c1-1-r6c1-6-r6c5.
When the cell r6c5 contains the value 8, some other value must occupy the cell r6c4, which means that the value 6 must occupy the cell r6c5 - a contradiction.
Therefore, the cell r6c5 cannot contain the value 8.
- The move r6c5:=8 has been eliminated.
Consider the chain r4c5-4-r4c4-4-r2c4-4-r2c1-1-r6c1-6-r6c5.
When the cell r4c5 contains the value 6, so does the cell r6c5 - a contradiction.
Therefore, the cell r4c5 cannot contain the value 6.
- The move r4c5:=6 has been eliminated.
Consider the chain r5c8-6-r2c8~6~r2c3~8~r2c4-8-r6c4-3-r6c7.
When the cell r5c8 contains the value 3, so does the cell r6c7 - a contradiction.
Therefore, the cell r5c8 cannot contain the value 3.
- The move r5c8:=3 has been eliminated.
The value 3 in Box 9 must lie in Column 8.
- The moves r8c7:=3 and r9c7:=3 have been eliminated.
Consider the chain r1c7-6-r1c2~6~r2c3~8~r2c4-4-r4c4-6-r4c7.
When the cell r4c7 contains the value 6, so does the cell r1c7 - a contradiction.
Therefore, the cell r4c7 cannot contain the value 6.
- The move r4c7:=6 has been eliminated.
The cell r4c4 is the only candidate for the value 6 in Row 4.
2. The value 3 is the only candidate for the cell r8c4.
3. The value 8 is the only candidate for the cell r6c4.
4. The value 4 is the only candidate for the cell r2c4.
5. The value 1 is the only candidate for the cell r2c1.
6. The value 6 is the only candidate for the cell r6c1.
7. The value 1 is the only candidate for the cell r5c3.
8. The value 3 is the only candidate for the cell r5c6.
9. The value 2 is the only candidate for the cell r1c6.
10. The value 7 is the only candidate for the cell r4c6.
11. The value 5 is the only candidate for the cell r4c3.
12. The value 1 is the only candidate for the cell r6c6.
13. The value 8 is the only candidate for the cell r8c6.
14. The value 2 is the only candidate for the cell r6c5.
15. The value 7 is the only candidate for the cell r9c5.
16. The value 3 is the only candidate for the cell r9c8.
17. The value 4 is the only candidate for the cell r4c5.
18. The value 7 is the only candidate for the cell r6c3.
19. The value 3 is the only candidate for the cell r6c7.
20. The value 5 is the only candidate for the cell r6c9.
21. The cell r7c8 is the only candidate for the value 7 in Row 7.
22. Consider the chain r8c3-9-r9c3-8-r9c7-8-r4c7-2-r4c9-2-r8c9.
When the cell r8c9 contains the value 9, some other value must occupy the cell r8c3, which means that the value 2 must occupy the cell r8c9 - a contradiction.
Therefore, the cell r8c9 cannot contain the value 9.
- The move r8c9:=9 has been eliminated.
The value 9 in Box 3 must lie in Column 9.
- The moves r1c7:=9, r2c7:=9 and r3c7:=9 have been eliminated.
Consider the chain r3c2-7-r2c2-9-r2c5-8-r3c5-8-r3c2.
When the cell r3c2 contains the value 8, it likewise contains the value 7 - a contradiction.
Therefore, the cell r3c2 cannot contain the value 8.
- The move r3c2:=8 has been eliminated.
The cell r3c5 is the only candidate for the value 8 in Row 3.
23. The value 9 is the only candidate for the cell r2c5.
24. The value 3 is the only candidate for the cell r1c5.
25. The value 4 is the only candidate for the cell r1c3.
26. The value 3 is the only candidate for the cell r3c1.
27. The value 4 is the only candidate for the cell r7c1.
28. The cell r7c3 is the only candidate for the value 3 in Row 7.
29. Consider the chain r8c9-4-r3c9-9-r3c2-7-r2c2-8-r7c2-8-r7c9-8-r4c9-2-r8c9.
The cell r8c9 must contain the value 2 if it doesn't contain the value 4.
Therefore, these two values are the only candidates for the cell r8c9.
- The move r8c9:=1 has been eliminated.
The values 1, 6 and 9 occupy the cells r8c3, r8c5 and r8c7 in some order.
- The moves r8c7:=2 and r8c7:=4 have been eliminated.
Consider the chain r1c2-9-r1c9-1-r7c9-8-r7c2.
The cells r1c2 and r7c2 contain one value from the set {9,8} and the value 6.
The value 6 occupies 1 of the cells r1c2 and r7c2.
- The move r2c2:=6 has been eliminated.
Consider the chain r1c7-6-r1c2-9-r3c2-7-r3c7-4-r5c7.
When the cell r5c7 contains the value 6, some other value must occupy the cell r1c7, which means that the value 4 must occupy the cell r5c7 - a contradiction.
Therefore, the cell r5c7 cannot contain the value 6.
- The move r5c7:=6 has been eliminated.
The value 4 is the only candidate for the cell r5c7.
rubylips
 
Posts: 149
Joined: 01 November 2005

Postby Jeff » Mon Nov 14, 2005 6:04 pm

Hi, Rubylips

Whilst I am still chewing over your preferred argument for the technique, could you clarify whether there is a typo in the statement "the value 4 can't be a candidate for the cells r2c1 or r2c2".

From your computer printout, I must say that your solver is the best when comes to identifying double implication chains. Although I am always a manual solver enjoying drawing my bilocation/bivalue plots, I do from time to time consult your solver to check my results, especially for checking whether any chains has been missed out due to human errors. Thanks again.

Hi, Mike

Using the bilocation/bivalue plot, which is human executable and non-T&E, 2 double implication chains can be identified to draw the same conclusion that r2c1<>4.

Chain 1: Combination chain (also known as a turbot fish)
[r2c1]-6-[r2c8]=6=[r5c8]-6-[r5c3]=6=[r6c1]-6-[r2c1] => r2c1<>6

Chain 2: Combination chain (after removing 6 from r2c1)
[r2c1]-4-[r2c4]-8-[r3c5]=8=[r3c2]-8-[r7c2]-6-[r7c1]=6=[r6c1]=1=[r2c1] => r2c1<>4

As you can see, although both techniques are non-T&E, the empty cell contradiction technique is more elegant because it can be done by pure inspection without filtering nor construction of any plot.

As angus has pointed out, a 3rd chain is required to complete the puzzle and this can be identified by means of the bilocation/bivalue plot also.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby rubylips » Tue Nov 15, 2005 12:26 am

Jeff wrote:Whilst I am still chewing over your preferred argument for the technique, could you clarify whether there is a typo in the statement "the value 4 can't be a candidate for the cells r2c1 or r2c2".

I think this statement is correct. It's based upon an analysis of the following candidate grid:
Code: Select all
 .  . 1346 | .  . . | . . .
 .  . 1468 | 48 . . | . . .
 34 . .    | .  . . | . . .
-----------+--------+------
 .  . .    | .  . . | . . .
 .  . 16   | .  . . | . . .
 .  . .    | .  . . | . . .

The statement appears silly because the value 4 isn't a candidate for the cell r2c2 - but that isn't apparent from the candidate excerpt given.
rubylips
 
Posts: 149
Joined: 01 November 2005

Postby Jeff » Tue Nov 15, 2005 9:53 am

Got it, thanks, Rubylips

I still think the empty cell contradiction argument is easier to spot though.
Jeff
 
Posts: 708
Joined: 01 August 2005

Previous

Return to Advanced solving techniques