## The Hidden BUG

Advanced methods and approaches for solving Sudoku puzzles

### The Hidden BUG

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

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

Posts: 593
Joined: 19 September 2005

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

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

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

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

RW
RW
2010 Supporter

Posts: 1000
Joined: 16 March 2006