I don't see the logic behind this...

Advanced methods and approaches for solving Sudoku puzzles

I don't see the logic behind this...

Postby jeanboucher » Tue Sep 05, 2006 11:06 am

Image

Here is the reduction that SudokuSusser:

Squares R4C1, R5C1, R4C8 and R5C8 form a Type-4 Unique Rectangle on <56>. Because they share two rows, two columns, and two blocks, if they all had possibilities <56> then the puzzle would have two solutions; you could simply exchange the <5>s with the <6>s in the squares to get the other solution, and their common rows, columns and blocks would still contain one of each value. If you look carefully, you'll see that the only squares in block 6 that can contain <5> are the "roof" squares -- R4C8 and R5C8. Since one of these squares must be <5>, the only way to avoid the "deadly pattern" is if neither of them can contain <6>.

R4C8 - can remove <6> from <45678> leaving <4578>.
R5C8 - can remove <6> from <5678> leaving <578>.

If you are looking in a human point of vue, I really don't see why I can remove the 6 Candidate!

I agree that the candidate 5 must occupie one of the 2 square, but what is the logic behind the 6?
jeanboucher
 
Posts: 24
Joined: 04 August 2006

Postby udosuk » Tue Sep 05, 2006 12:01 pm

It should be easy to see from a human standpoint too...

The 5 on c8 must be on either r4c8 or r5c8.

Now, suppose r4c8=6, then r5c8 must be 5. And r4c1 must be 5, r5c1 must be 6.
Code: Select all
...|...|...
...|...|...
...|...|...
---+---+---
5..|...|.6.
6..|...|.5.
...|...|...
---+---+---
...|...|...
...|...|...
...|...|...

This pattern of {56} should not be appearing in any valid sudoku puzzles unless at least one of the 4 cells is presented as an initial clue, which is not true in this case...

Similarly, suppose r5c8=6, then r4c8 must be 5. And r4c1 must be 6, r5c1 must be 5.
Code: Select all
...|...|...
...|...|...
...|...|...
---+---+---
6..|...|.5.
5..|...|.6.
...|...|...
---+---+---
...|...|...
...|...|...
...|...|...

Same deal here...
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby jeanboucher » Tue Sep 05, 2006 1:30 pm

At this point, What are the indices that prevent me from this:

Code: Select all
...|...|...
...|...|...
...|...|...
---+---+---
6..|...|.5.
5..|...|.7.
...|...|...
---+---+---
...|...|...
...|...|...
...|...|...


or this:

Code: Select all
...|...|...
...|...|...
...|...|...
---+---+---
5..|...|.4.
6..|...|.5.
...|...|...
---+---+---
...|...|...
...|...|...
...|...|...


or even this:

Code: Select all
...|...|...
...|...|...
...|...|...
---+---+---
5..|...|.8.
6..|...|.5.
...|...|...
---+---+---
...|...|...
...|...|...
...|...|...
jeanboucher
 
Posts: 24
Joined: 04 August 2006

Postby udosuk » Tue Sep 05, 2006 4:37 pm

jeanboucher wrote:At this point, What are the indices that prevent me from this: ...

Nothing prevents you from those cases! They're all possible (at that point)... As long as no 6 in those 2 right cells.

That's why you could eliminate 6 from r45c8...
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby jeanboucher » Tue Sep 05, 2006 5:44 pm

udosuk wrote:So, What you are saying:

This pattern of {56} should not be appearing in any valid sudoku puzzles unless at least one of the 4 cells is presented as an initial clue, which is not true in this case...

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


OR

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



Since we know that the Candidate 5 MUST be included in C8, we can completely eliminate de Candidate 6.

Thanks udosuk
jeanboucher
 
Posts: 24
Joined: 04 August 2006

Postby udosuk » Tue Sep 05, 2006 7:19 pm

jeanboucher wrote:Thanks udosuk

You're welcomed...:)

Just to add that this pattern is called "deadly pattern" by the experts here... Or "2-digit unavoidable set" when it's used to study the "minimum-clues problem"...
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby RW » Wed Sep 06, 2006 8:03 pm

udosuk wrote:Just to add that this pattern is called "deadly pattern" by the experts here... Or "2-digit unavoidable set" when it's used to study the "minimum-clues problem"...

I think we agreed in the structures thread that:

Unavoidable set = A set of n clues that if removed can be solved in multiple ways
Deadly pattern = A set of n cells that can be solved in multiple ways

So, as a solver you see potential deadly patterns (empty cells that would give multiple solutions), and as a puzzle generator you deal with unavoidable sets (sets of givens that cannot be completely removed in order to preserve an unique solution).

RW
RW
2010 Supporter
 
Posts: 1010
Joined: 16 March 2006


Return to Advanced solving techniques