Help with BUG

Advanced methods and approaches for solving Sudoku puzzles

Postby eleven » Wed Feb 20, 2008 11:35 pm

ab wrote:
eleven wrote:I agree, that xy-chains are kind of guessing
Solve as you like, but dont snip, when you quote me. I said, xy-chains are kind of guessing, because you have to guess, where to begin to search for one.
In this puzzle a manual player probably never would find this xy-chain, because there is one from each cell i tried. Or is there a reason to start with r9c3 ?

EnderGT wrote:While I understand your reasoning here, it seems to me that applying an assumption of uniqueness to a puzzle that isn't, in fact, unique, would actually end up resulting in a no-solution state.
Or you would not even notice it, because you find one of say 3 or 5 solutions.
eleven
 
Posts: 1559
Joined: 10 February 2008

Postby Mike Barker » Thu Feb 21, 2008 12:24 am

Ron, my mistake for not showing the non-BUG candidates. I'm not sure I understand your comment about a single nice loop. I showed two independent eliminations from the same BUG. I'm having a little problem understanding your chain which is basically the same as my first chain, but appears to be missing a link. On the other hand, when I posted regarding advanced BUG/BUG-Lites, I was thinking of them as "advanced" techniques, but you are right the existence of the BUG/BUG-Lite makes the strong inference more obvious. I should probably move them up in my solving hierarchy.

Ender, there are arguments ad infinitum about what is and what isn't an acceptable technique. I've learned enough to stay away from them (most of the time). Nice Loops or their twin, AICs, in their simplest form establish derived strong inferences by linking together strong links and/or bivalue cells to form a final strong inference: cell1=x=cell2 (x is in cell1 or cell2). In the XY-chain example I posted the inference was r9c3=6=r2c9. Anything which sees these cells cannot contain "6". This is what an X-wing or an XY-wing does only expanded. One big advantage of this approach is that any derived strong inference is always true. You can use it any time is solving the puzzle. Also these inferences can make a large number of eliminations. Assuming a candidate and creating a forcing chain does neither. You may create several strong inferences before finding an elimination, but the effort isn't wasted because they are reusable.

Another viewpoint would be Denis' resolution rules approach. X-wings and XY-chains are examples of resolution rules. They are attractive because having defined the rule you can search for the pattern. Denis has extended these rules to longer chains. An example of these are W-wings which are similar to XY-wings, but combine strong links and bivalues. I think as you attempt more difficult puzzles you will find these techniques (nice loops, AICs, advanced patterns/resolution rules) as indispensable.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby ab » Thu Feb 21, 2008 12:54 am

EnderGT wrote:
ab wrote:xy chains are not guessing they're pattern based. In this example there are two possibilities for row 9 column 3. If it's 7 then row 1 column 3 must be 8, so row 1 column 7 must be 9 therefore row 2 column 9 is 6. Alternatively row 9 column 3 is 6. Either way row 9 column 9 can't be 6. Where is the guesswork?


I bolded the part where you guessed.

No that was not a guess! I was stepping through the two possiblilites. r9c3 is 6 or 7. In the case where it's 6 obviously r9c9 cannot be 6 but in the case where it's 7, we can look at the consequences. There is a pattern formed by several cells having just two candidates, in much the same way that say a naked pair forms a certain pattern or an x wing forms a certain pattern.
ab
 
Posts: 451
Joined: 06 September 2005

Re: Help with BUG

Postby daj95376 » Thu Feb 21, 2008 1:41 am

EnderGT wrote:Sounds like 2 BUGs to me... except one is and one isn't, and I can't figure out how I'm supposed to identify which is and which isn't. The only reason I know right now is that the program told me that one of them was incorrect.

Can someone take a look and tell me what I'm missing, and what to look for in the future? Thanks...

Wow, did this thread go off on several tangents. Back to the original question ... and assumption that this PM is accurate.

Code: Select all
 *--------------------------------------------------*
 | 6    3    78   | 47   49   1    | 89   5    2    |
 | 1    78   4    | 57   2    59   | 389  36   69   |
 | 9    2    5    | 8    3    6    | 1    7    4    |
 |----------------+----------------+----------------|
 | 8    4    9    | 1    7    3    | 6    2    5    |
 | 7    6    3    | 9    5    2    | 4    8    1    |
 | 5    1    2    | 6    8    4    | 7    9    3    |
 |----------------+----------------+----------------|
 | 34   5    16   | 2    49   7    | 39   16   8    |
 | 34   78   178  | 45   6    59   | 2    13   79   |
 | 2    9    67   | 3    1    8    | 5    4    67   |
 *--------------------------------------------------*

First off, you can't have two BUGs to my knowledge. What you have is a (possible) BUG+2 situation. This possibility has already been addressed.

There is an X-Wing r17\c57 that results in [r2c7]<>9. After performing the X-Wing elimination and checking the resulting grid, a BUG+1 remains for cell [r8c3]=7. This was all mentioned by Mike Barker in his first reply, but I think its significance was lost as the best way to go.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby eleven » Thu Feb 21, 2008 9:50 am

Look at such a grid for 5 seconds. What will you see ? A BUG, x-wing or xy-chain ? For me it is clear, what to do next - see what candidates come from the BUG.
eleven
 
Posts: 1559
Joined: 10 February 2008

Postby daj95376 » Thu Feb 21, 2008 2:10 pm

[Withdrawn] I accept that searching for an overlapping chain may be preferred by some people.
Last edited by daj95376 on Thu Feb 21, 2008 11:02 am, edited 1 time in total.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby ronk » Thu Feb 21, 2008 2:47 pm

Mike Barker wrote:I'm not sure I understand your comment about a single nice loop. I showed two independent eliminations from the same BUG.

I merely meant that only one of the two was required ... "setting up" the following comparison to the xy-chain.

I'm having a little problem understanding your chain which is basically the same as my first chain, but appears to be missing a link.

Sorry, that's due to my (now corrected) typo. However, eleven later posted an even shorter chain ...

r7c7 -9- BUG:(r2c7 =9|7= r8c3) -7- r8c9 -9- r7c7, implies r7c7<>9
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby daj95376 » Thu Feb 21, 2008 3:55 pm

Code: Select all
variant on ronk:   [r2c7]-9-[r7c7]-3-[r8c8]-1-[r8c3]
variant on eleven: [r8c3]-7-[r8c9]-9-[r7c7]-3-[r2c7]

Without knowing ahead of time that all correlations/chains go through box 9, I still think the X-Wing for candidate 9 has merit.

Code: Select all
 12 + correlations for [r2c7]=9 & [r8c3]=7
 12 - correlations for [r2c7]=9 & [r8c3]=7
 +-----------------------------------------+
 |  .   .   -  |  -   -   .  |  -   .   .  |
 |  .   -   .  |  -   .   -  |  -  +3  +6  |
 |  .   .   .  |  .   .   .  |  .   .   .  |
 |-------------+-------------+-------------|
 |  .   .   .  |  .   .   .  |  .   .   .  |
 |  .   .   .  |  .   .   .  |  .   .   .  |
 |  .   .   .  |  .   .   .  |  .   .   .  |
 |-------------+-------------+-------------|
 | +4   .  +1  |  .  +9   .  | +3  +6   .  |
 | +3   -   -  |  -   .   -  |  .  +1  +9  |
 |  .   .  +6  |  .   .   .  |  .   .  +7  |
 +-----------------------------------------+
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: Help with BUG

Postby EnderGT » Thu Feb 21, 2008 5:11 pm

daj95376 wrote:Wow, did this thread go off on several tangents.

Yes, it did, and it's at least partially my own fault, if not mostly...:)

daj95376 wrote:First off, you can't have two BUGs to my knowledge. What you have is a (possible) BUG+2 situation. This possibility has already been addressed.

This is correct. My statement of "two BUGs" was rooted in my inexperience with this solving technique. I agree that the correct terminology would have been BUG+2, and thus my question should have been how to determine which cell was the "BUG buster" or whatever the appropriate term is.

daj95376 wrote:There is an X-Wing r17\c57 that results in [r2c7]<>9. After performing the X-Wing elimination and checking the resulting grid, a BUG+1 remains for cell [r8c3]=7. This was all mentioned by Mike Barker in his first reply, but I think its significance was lost as the best way to go.

This post was not lost on me. Once he pointed it out, I immediately saw it and the puzzle was completely solved. I hadn't seen it before because I was focussed on trying to identify the BUG that the analysis tool told me would be there. Incidentally, I think that it was because of this answer that I allowed myself to hijack my own thread - my question had been answered.

eleven wrote:
EnderGT wrote:While I understand your reasoning here, it seems to me that applying an assumption of uniqueness to a puzzle that isn't, in fact, unique, would actually end up resulting in a no-solution state.
Or you would not even notice it, because you find one of say 3 or 5 solutions.

I suppose this is true, but yet... if the application of one single assumption of uniqueness leads me to a single solution, then I'd argue that that is the only valid solution. If I have to make multiple assumptions of uniqueness, this doesn't hold true, but I'd almost rather not know that there could have been other solutions.

ab wrote:No that was not a guess! I was stepping through the two possiblilites. r9c3 is 6 or 7. In the case where it's 6 obviously r9c9 cannot be 6 but in the case where it's 7, we can look at the consequences. There is a pattern formed by several cells having just two candidates, in much the same way that say a naked pair forms a certain pattern or an x wing forms a certain pattern.

I'm beginning to see the truth in your argument - you are performing a candidate reduction on r9c9 based on the link between it's buddy cells. I'll have to work with this some more to figure out how to apply it as a pattern and not as guesswork.

Thank you, everyone, for your inputs.
EnderGT
 
Posts: 69
Joined: 19 February 2008

Postby ronk » Thu Feb 21, 2008 5:13 pm

daj95376 wrote:
Code: Select all
variant on ronk:   [r2c7]-9-[r7c7]-3-[r8c8]-1-[r8c3]
variant on eleven: [r8c3]-7-[r8c9]-9-[r7c7]-3-[r2c7]

I don't see a loop that would cause an elimination in those variants, so I don't understand what you're saying.

Without knowing ahead of time that all correlations/chains go through box 9, I still think the X-Wing for candidate 9 has merit.

Yeh, I would do the x-wing, then BUG+1 too, but the question was about BUG+2 ... so I'm just pretending I didn't see the x-wing.:)
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby EnderGT » Thu Feb 21, 2008 5:31 pm

ronk wrote:Yeh, I would do the x-wing, then BUG+1 too, but the question was about BUG+2 ... so I'm just pretending I didn't see the x-wing.:)


Actually, it wasn't about BUG+2 - I had discovered through trial and, more importantly, error that it wasn't a BUG+2, and was asking for advice on how to recognize and identify such situations in the future without resorting to trial and error.

The X-wing is exactly the answer I needed to remove the non-BUG extra candidate. I hadn't seen it because, as I've said before, I was hung up on the BUG+1 that the analysis tool told me was there.

Edit: Maybe my lack of experience is biting me once again. My impression is that in BUG+2 either of the extra candidates could be used to solve the puzzle. If this is correct, then what I wrote above holds true because I knew that one of them would not solve the puzzle. If it's not true, then yes the question was about BUG+2, and I haven't gotten an answer yet, even though the x-wing does solve the puzzle.
EnderGT
 
Posts: 69
Joined: 19 February 2008

Postby ronk » Thu Feb 21, 2008 5:48 pm

EnderGT wrote:My impression is that in BUG+2 either of the extra candidates could be used to solve the puzzle. If this is correct, then what I wrote above holds true because I knew that one of them would not solve the puzzle. If it's not true, then yes the question was about BUG+2 ...

For your BUG+2, at least one of the two extra candidates must ultimately be true. That's not really the same as "either of the extra candidates could be used to solve the puzzle."

In general, for any BUG+N, at least one of the extra candidates must be true. BTW the 'N' is the number of cells with extra candidates, not the number of extra candidates.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby EnderGT » Thu Feb 21, 2008 6:05 pm

ronk wrote:
EnderGT wrote:My impression is that in BUG+2 either of the extra candidates could be used to solve the puzzle. If this is correct, then what I wrote above holds true because I knew that one of them would not solve the puzzle. If it's not true, then yes the question was about BUG+2 ...

For your BUG+2, at least one of the two extra candidates must ultimately be true. That's not really the same as "either of the extra candidates could be used to solve the puzzle."

Just to make sure I understand what you're saying - BUG+N means that at least one of the cells will "break" the BUG, but not that each of the N cells will. As such, my original question was how to identify which cell would break the BUG, and it was answered by pointing out the X-wing that reduced it from BUG+2 to BUG+1.

ronk wrote:In general, for any BUG+N, at least one of the extra candidates must be true. BTW the 'N' is the number of cells with extra candidates, not the number of extra candidates.

Thanks for that clarification.

It seems the general answer given by this thread is that when confronted with BUG+N (N>1), look for other methods of either reducing it to BUG+1, or of solving some other cell(s).
EnderGT
 
Posts: 69
Joined: 19 February 2008

Postby eleven » Thu Feb 21, 2008 7:38 pm

My answer is, when confronted with a BUG+2 or BUG+3, i will try to use the fact that at least one of 2 or 3 candidates must be true, to make an elimination (in a way ronk or i showed above). This is quickly done and often solves the puzzle.

Would you solve this with an xy-chain ? http://forum.enjoysudoku.com/viewtopic.php?p=52686#p52686
eleven
 
Posts: 1559
Joined: 10 February 2008

Postby daj95376 » Thu Feb 21, 2008 10:00 pm

ronk wrote:
daj95376 wrote:
Code: Select all
variant on ronk:   [r2c7]-9-[r7c7]-3-[r8c8]-1-[r8c3]
variant on eleven: [r8c3]-7-[r8c9]-9-[r7c7]-3-[r2c7]

I don't see a loop that would cause an elimination in those variants, so I don't understand what you're saying.

Sorry ronk, I was too brief.

Code: Select all
Either [r2c7]=9 and/or [r8c3]=7 must be true.

[r2c7]=9 => [r2c7]<>3|8
[r8c3]=7 => [r8c3]<>1|8

With the first variant, I took your [r8c3]<>1 conclusion and derived it from the assumption [r2c7]=9. No matter which either is true, I conclude that [r8c3]<>1.

On the second variant, I used eleven's assumption of [r8c3]=7 and reached [r2c7]<>3 as a conclusion. No matter which either is true, I conclude that [r2c7]<>3.

No matter which conclusion is used, the puzzle is now solvable through Singles.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

PreviousNext

Return to Advanced solving techniques