Technique Name Please

Everything about Sudoku that doesn't fit in one of the other sections

Technique Name Please

Postby daj95376 » Mon Dec 04, 2006 7:27 pm

Code: Select all
 *-----------*
 |...|.27|3..|
 |...|5..|64.|
 |..1|..3|.5.|
 |---+---+---|
 |..9|652|...|
 |..6|..4|...|
 |..7|..9|...|
 |---+---+---|
 |...|38.|...|
 |.83|..1|9..|
 |6..|...|.7.|
 *-----------* # recent post by m_b_metcalf

# XY-Chain 1-[r1c9]-9-[r5c9]-2-[r5c2]-5-[r5c7]-1-[r4c9]
 *-----------------------------------------------------------*
 | 5     6     8     | 4     2     7     | 3     19   *19    |
 | 39    39    2     | 5     1     8     | 6     4     7     |
 | 47    47    1     | 9     6     3     | 2     5     8     |
 |-------------------+-------------------+-------------------|
 | 1348  34    9     | 6     5     2     | 7     38    4-1   |
 | 138   5-2   6     | 18    7     4     | 1-5   2389  2-9   |
 | 148   25    7     | 18    3     9     | 145   28    6     |
 |-------------------+-------------------+-------------------|
 | 79    79    5     | 3     8     6     | 14    12    124   |
 | 2     8     3     | 7     4     1     | 9     6     5     |
 | 6     1     4     | 2     9     5     | 8     7     3     |
 *-----------------------------------------------------------*

# alternate route
# 1-[r1c9]-9-[r5c9]-2-[r6c8]-8-[r4c8]-3-[r4c2]-4-[r4c9]-1
 *-----------------------------------------------------------*
 | 5     6     8     | 4     2     7     | 3     19   *19    |
 | 39    39    2     | 5     1     8     | 6     4     7     |
 | 47    47    1     | 9     6     3     | 2     5     8     |
 |-------------------+-------------------+-------------------|
 | 1348  4-3   9     | 6     5     2     | 7     3-8   1-4   |
 | 138   25    6     | 18    7     4     | 15    2389  2-9   |
 | 148   25    7     | 18    3     9     | 145   8-2   6     |
 |-------------------+-------------------+-------------------|
 | 79    79    5     | 3     8     6     | 14    12    124   |
 | 2     8     3     | 7     4     1     | 9     6     5     |
 | 6     1     4     | 2     9     5     | 8     7     3     |
 *-----------------------------------------------------------*

Now, since [r1c9]=9 leads to two different assignments for [r4c9], it's easy to deduce that [r1c9]<>9. However, I don't recall reading about a technique for this elimination in <9>. What's its name?
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby ravel » Mon Dec 04, 2006 7:35 pm

For me its a contradiction chain or simple nice loop:
[r1c9]-9-[r5c9]-2-[r5c2]-5-[r5c7]-1-[r4c9]-4-[r4c2]-3-[r4c8]-8-[r6c8]-2-[r5c9]-9-[r1c9]
ravel
 
Posts: 998
Joined: 21 February 2006

Postby RW » Mon Dec 04, 2006 7:40 pm

daj95376 wrote:# XY-Chain 1-[r1c9]-9-[r5c9]-2-[r5c2]-5-[r5c7]-1-[r4c9]

...which implies that r4c9<>1 and solves the puzzle. Why make it more complicated than that?

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

Postby daj95376 » Mon Dec 04, 2006 8:42 pm

RW wrote:
daj95376 wrote:# XY-Chain 1-[r1c9]-9-[r5c9]-2-[r5c2]-5-[r5c7]-1-[r4c9]

...which implies that r4c9<>1 and solves the puzzle. Why make it more complicated than that?

RW

Good question. To me, it makes more sense to accurately deduce [r1c9]<>9 that to use a false assumption, [r1c9]=9, and deduce [r4c9]<>1. I was hoping there was a technique similar to XY-Chains that would let me do so.

It appears that ravel's chain is the way to go. I just happen to have XY-Chains before contradiction chains in my solver, and the fact that this puzzle then solved with singles prevented me from needing to check for contradiction chains.

Thanks RW and ravel for your assistance! Now, all I have to do is remember it. (The gray matter is fading fast anymore!)
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby RW » Mon Dec 04, 2006 10:20 pm

daj95376 wrote:To me, it makes more sense to accurately deduce [r1c9]<>9 that to use a false assumption, [r1c9]=9, and deduce [r4c9]<>1

Aren't you using the same false assumption to deduce r1c9<>9? To deduce r4c9<>9 you actually look at all possibilities: if r1c9=1 => r4c9<>1, if r1c9=9 => ... => r4c9<>1. But this deduction would probably also be best written as a nice loop:
[r4c9]-1-[r1c9]-9-[r5c9]-2-[r5c2]-5-[r5c7]-1-[r4c9]

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

Postby RW » Mon Dec 04, 2006 10:34 pm

daj95376 wrote:I was hoping there was a technique similar to XY-Chains that would let me do so.

Upon closer inspection, there actually is a XY-chain to make that deduction:
Code: Select all
 *-----------------------------------------------------------*
 | 5     6     8     | 4     2     7     | 3    *19   -19    |
 | 39    39    2     | 5     1     8     | 6     4     7     |
 | 47    47    1     | 9     6     3     | 2     5     8     |
 |-------------------+-------------------+-------------------|
 | 1348 *34    9     | 6     5     2     | 7    *38   *14    |
 | 138  *25    6     | 18    7     4     |*15    2389 *29    |
 | 148   25    7     | 18    3     9     | 145  *28    6     |
 |-------------------+-------------------+-------------------|
 | 79    79    5     | 3     8     6     | 14   *12    124   |
 | 2     8     3     | 7     4     1     | 9     6     5     |
 | 6     1     4     | 2     9     5     | 8     7     3     |
 *-----------------------------------------------------------*

[r1c8]-1-[r7c8]-2-[r6c8]-8-[r4c8]-3-[r4c2]-4-[r4c9]-1-[r5c7]-5-[r5c2]-2-[r5c9]-9-[r1c9]

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

Postby daj95376 » Tue Dec 05, 2006 1:47 am

Okay, I see that my point is as clear as mud. Please let me restate my position.

1) My XY-Chain -- and all XY-Chains -- rely on starting with two candidates in one cell and using them to determine an elimination in another cell. This works because there's an overlap in eliminations from choosing either candidate in the original cell. I accept this as a valid and useful technique. However, it bothers me when different paths from the false assumption lead to different results in cells affected by the correct assumption. (I guess that I need to learn to get over this!)

2) However, there are times when just following an assumption all by itself might be productive. In my example, I was trying to show that working with [r1c9]=9 (alone) resulted in two paths leading to different assignments in [r4c9]. Now, a conclusion can be reached about the original assumption. I thought this was significant in itself, but don't remember ever reading of a technique that took this approach. I thought someone else might have used this approach and given it a name.

Am I still as clear as mud?

Addendum: The more I think about it, the more it sounds like I'm just using a different perspective to performing a contradiction chain on [r1c9]=9. Drat!
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby wapati » Tue Dec 05, 2006 5:49 am

daj95376 wrote:2) However, there are times when just following an assumption all by itself might be productive.


Assumptions are guesses. I cannot find them attractive, however well they work.
wapati
2010 Supporter
 
Posts: 527
Joined: 13 September 2006
Location: Brampton, Ontario, Canada


Return to General