The Hidden BUG

Advanced methods and approaches for solving Sudoku puzzles

The Hidden BUG

Postby RW » Sat Apr 15, 2006 7:16 am

Hi guys

I was just going through my old examples from this thread, when I realised that there was a much simpler way to recognize these large double solution patterns. I already showed you how to find large double solution patterns that involve only two different numbers with the reverse BUG, my new theory can easily find multiple solution patterns that involve more than two numbers:

Code: Select all
If consentrating on all candidates of any amount of numbers shows exactly 0 or 2 candidates in every cell, then the puzzle has multiple solutions.


I'll bring back my last example from the previous thread to illustrate:

Code: Select all
 *-----------*
 |...|..4|.82|
 |.79|.8.|.4.|
 |.6.|7.5|.9.|
 |---+---+---|
 |...|...|...|
 |.31|2..|...|
 |.8.|43.|..7|
 |---+---+---|
 |...|6..|..5|
 |.4.|8..|.7.|
 |..3|...|9..|
 *-----------*


Basic steps and one uniqueness rectangle take us here:

Code: Select all
*--------------------------------------------------------------------*
 | 3      1      5      | 9      6      4      | 7      8      2      |
 | 2      7      9      | 3      8      1      | 5      4      6      |
 | 48     6      48     | 7      2      5      | 13     9      13     |
 |----------------------+----------------------+----------------------|
 | 4679   259    47     | 15     179    6789   | 3468   236    489    |
 | 45679  3      1      | 2      579    6789   | 468    56     489    |
 | 569    8      26     | 4      3      69     | 126    15     7      |
 |----------------------+----------------------+----------------------|
 | 1789   29     78     | 6      1479   237    | 48     123    5      |
 | 159    4      26     | 8      159    39     | 26     7      13     |
 | 1678   25     3      | 15     147    27     | 9      126    48     |
 *--------------------------------------------------------------------*


Now let's show all candidates of 4, 7 and 8:

Code: Select all
*-----------------------------------------*
|             |          4  | 7    8      |
|      7      |     8       |      4      |
|(48)     (48)| 7           |             |
|-------------+-------------+-------------|
|(47)     (47)|    (7)  (78)|(48)     (48)|
|(47)         |    (7)  (78)|(48)     (48)|
|      8      | 4           |          7  |
|-------------+-------------+-------------|
|(78)     (78)|    (47) (7) |(48)         |
|      4      | 8           |      7      |
|(78)         |    (47) (7) |         (48)|
*-----------------------------------------*

[Edit: Typo fixed]

All cells that hold candidates, hold exactly 2 candidates, except r45c5 and r79c6. Therefore at least one of these must be true and we can remove candidate 7 from r45c6 and r79c5 which solves the puzzle.

The BUG rule also says that "if a candidate exists in a row, column, or box, it shows up exactly twice", but that doesn't need to be taken in consideration here, because there is still unsolved instances of other numbers. If the candidates form pairs in every cell, they would in the end appear exactly twice in every unit after solving the other numbers.

Questions?

RW
Last edited by RW on Sat Apr 15, 2006 5:08 am, edited 1 time in total.
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby Myth Jellies » Sat Apr 15, 2006 8:58 am

Interesting. Your 7 in row 6 should be in column 9.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby RW » Sat Apr 15, 2006 9:06 am

Myth Jellies wrote:Your 7 in row 6 should be in column 9.

Of course, I really have to learn to get rid of these stupid typos. Doesn't affect the rest of the puzzle though.

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

Re: The Hidden BUG

Postby re'born » Sat Apr 15, 2006 6:29 pm

RW,

Very nice. I have a quick question, though. At the point you apply the technique,

RW wrote:
Basic steps and one uniqueness rectangle take us here:

Code: Select all
*--------------------------------------------------------------------*
 | 3      1      5      | 9      6      4      | 7      8      2      |
 | 2      7      9      | 3      8      1      | 5      4      6      |
 | 48     6      48     | 7      2      5      | 13     9      13     |
 |----------------------+----------------------+----------------------|
 | 4679   259    47     | 15     179    6789   | 3468   236    489    |
 | 45679  3      1      | 2      579    6789   | 468    56     489    |
 | 569    8      26     | 4      3      69     | 126    15     7      |
 |----------------------+----------------------+----------------------|
 | 1789   29     78     | 6      1479   237    | 48     123    5      |
 | 159    4      26     | 8      159    39     | 26     7      13     |
 | 1678   25     3      | 15     147    27     | 9      126    48     |
 *--------------------------------------------------------------------*


I would have then employed an xy-wing to eliminate the 4 from r4c7. The candidate chart for 4,7 and 8 would then look like

Code: Select all
*-----------------------------------------*
|             |          4  | 7    8      |
|      7      |     8       |      4      |
|(48)     (48)| 7           |             |
|-------------+-------------+-------------|
|(47)     (47)|    (7)  (78)|(8)      (48)|
|(47)         |    (7)  (78)|(48)     (48)|
|      8      | 4           |          7  |
|-------------+-------------+-------------|
|(78)     (78)|    (47) (7) |(48)         |
|      4      | 8           |      7      |
|(78)         |    (47) (7) |         (48)|
*-----------------------------------------*


What eliminations (if any) could be made with your technique? vidarino wrote in the related thread here that "you never get less information during the course of a puzzle." So we should be able to make the same deductions (or more). Am I missing something obvious?

On a related note, has anyone tested some of the lists (topXX, etc.) to see how often the reverse bug or the hidden bug rear their buggy little heads?
re'born
 
Posts: 551
Joined: 31 May 2007

Postby RW » Sat Apr 15, 2006 9:02 pm

rep'nA wrote:I would have then employed an xy-wing to eliminate the 4 from r4c7.


I was aware of that xy-wing and was expecting your question. This is indeed a tricky situation and I've been trying to come up with a good way to formulate an answer during the day. When I first solved this puzzle with the techniques described in the "uniqueness chains" thread, this did not interfere in any way with those techniques - I could still make the same reductions. One solution could be that this candidate chart for the involved numbers should only consider direct reductions by solved cells in the grid, at least we will always get a valid result if we do it that way. The biggest problem with that is: what if some other reduction made by another technique is neccessary to make the application of this technique possible. I'm not sure if such a situation can happen, but if it does the solution should be found this way (this is a very hypothetical situation, if anybody can find an illustration that explains this I'd be happy to see it):

Say there would be an X-wing that removes 2 instances of candidate 3. Then you look for a hidden BUG, only considering direct reductions by already solved cells, you find an almost hidden bug pattern involving number 2, 3 and 4, only one single candidate 2 and two single candidate 3s. You know that one of them must be true. The 3s cannot be true due to the X-wing, therefore the 2 has to be true.

-> The order of how to do it: First find the almost Hidden BUG, then remove any singles in the pattern that you have removed from your original pencilmarkgrid. You should not touch the pairs in the pattern, because if the solved numbers allow the pairs to be there, the cell will support the hidden BUG.

I'm still trying to work out a more satisfying solution to this particular problem, if anybody has any good ideas I'm open for suggestions. At the moment I'm also working on a theory that would allow us to remove candidate 8 from the same cell you removed candidate 4 from with the XY-wing, but more on that later.

rep'nA wrote:"you never get less information during the course of a puzzle." So we should be able to make the same deductions (or more).


This is another very interesting topic. It is true that you never get less information, but you can make a puzzle harder to solve for a human being, because a human solver don't work directly with raw information, but with patterns. I was once presented with this little problem:

Code: Select all
*--------------------------------------------*
| 2    6    38 | 9    1    5  | 38   7    4  |
| 389  89   1  | 4    2    7  | 358  6    58 |
| 4    7    5  | 3    6    8  | 2    9    1  |
|--------------------------------------------|
| 5    1    7  | 8    4    3  | 6    2    9  |
|3689  89   389| 56   7    2  | 4    1    58 |
| 68   2    4  | 56   9    1  | 58   3    7  |
|--------------------------------------------|
| 7    4    6  | 2    5    9  | 1    8    3  |
| 89   5    89 | 1    3    6  | 7    4    2  |
| 1    3    2  | 7    8    4  | 9    5    6  |
*--------------------------------------------*


To a trained eye it is not hard to see that if r5c1=3 => BUG-lite in r2c12, r5c23 and r8c13 => r5c1<>3 which solves the puzzle. However the x-wing in r25c29 would let you reduce candidate 8 from r2c1, r5c1 and r5c3. Now you can't see the double solution pattern anymore but have to find the XY-wing in r2c1, r3c1, r8c1 (reduce 8 from r8c3) to solve the puzzle. This XY-wing is, at least for me, a lot harder to see than the uniqueness pattern that could be seen before the X-wing reduction. But if we look at the problem in a pure logical sense, removing candidate 3 from r5c1 with the uniqueness reduction would require the following steps:

if r5c1=3 then either
r5c3=8 => r8c3=9 => r8c1=8 => r2c1=9 => r2c2=8 => r5c2=9 => Double solution
or r5c3=9 => r8c3=8 => r8c1=9 => r2c1=8 => r2c2=9 => r5c2=8 => Double solution
=> r5c1 <> 3

After making the x-wing reduction we only need to follow the trail this far:

if r5c1=3 => r5c3=9 => r8c3=8 => r8c1=9 => no possible candidate in r2c1 => r5c1<>3

As we can see the x-wing greatly reduced the amount of logical steps we need to take between the assumption and the contradiction. But that doesn't neccessarily make it easier. I think the unfortunate example with the xy-wing in my hidden-BUG example falls into this same category. The pattern is simply easier to see before you make the xy-wing reduction.

rep'nA wrote:has anyone tested some of the lists (topXX, etc.) to see how often the reverse bug or the hidden bug rear their buggy little heads?


If anybody has I'd be very interested to hear the results also. I don't think they are very common, but there should be some appearances. Don't have any solver software on my own, I just come up with techniques that you may implement into your solvers. Finding these hidden BUGs manually would probably be very hard.

RW
Last edited by RW on Sun Apr 16, 2006 6:40 am, edited 1 time in total.
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby re'born » Sun Apr 16, 2006 10:16 am

RW,

Thank you for the very thorough response. I will keep thinking about the issue as well.

RW wrote:Finding these hidden BUGs manually would probably be very hard.


I spent this afternoon going through a couple of puzzles and looking for hidden BUG's and reverse BUG's. The nice thing is that at any given point in the puzzle, one can check in a rather systematic fashion for these patterns (I would certainly find a hidden bug before an ALS xz-rule situation, a pattern that I have no algorithm for finding). The problem is finding the appropriate point. Without further refinement of the technique, even a computer solver would presumably need to prioritize it near the top of the list (certainly before XY-wings as your example shows). This would make it unwieldly for a human solver (except in retrospect).
re'born
 
Posts: 551
Joined: 31 May 2007

Postby RW » Sat Aug 11, 2007 11:22 pm

This thread had vanished from the forum directory page and could not be found by the forum search engine. Most likely this was because of the rep'nA incident earlier this year. Turns out not only threads started by rep'nA, but also threads where rep'nA had the last post have become invisible. By replying to such a thread it can still be resurrected (that's what I'm doing right now). I've tried to add a post and then delete it to move the thread back to its correct place in the timeline (April 2006), but unfortunately it vanished again as soon as I deleted the post. If anyone knows of any other threads of any significance, not started by rep'nA, but where he had the last word, you can still find the threads with google and add a reply to bring them back to life.

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

Postby re'born » Sun Aug 12, 2007 8:14 am

RW wrote:This thread had vanished from the forum directory page and could not be found by the forum search engine. Most likely this was because of the rep'nA incident earlier this year. Turns out not only threads started by rep'nA, but also threads where rep'nA had the last post have become invisible. By replying to such a thread it can still be resurrected (that's what I'm doing right now). I've tried to add a post and then delete it to move the thread back to its correct place in the timeline (April 2006), but unfortunately it vanished again as soon as I deleted the post. If anyone knows of any other threads of any significance, not started by rep'nA, but where he had the last word, you can still find the threads with google and add a reply to bring them back to life.

RW


Wow. Thank you for figuring this out, RW. Your threads on BUGs and Uniqueness are some of my favorites, so I am quite relieved that you resurrected this one from the depths of internet h-ll. It is still disappointing to me that no one programmed reverse and hidden BUGs into a solver, at least to see if they were worth looking for.
re'born
 
Posts: 551
Joined: 31 May 2007


Return to Advanced solving techniques