The New Sudoku Players' Forum

[RW]

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

[Myth Jellies]

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

[RW]

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

[re'born]

RW,

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

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?

[RW]

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.

"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.

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

[re'born]

RW,

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

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).

[RW]

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

[re'born]

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.

[MAGREMENT]

Hi !

I've just finished implementing the Hidden BUG in my solver and I came accross a weird case

For this puzzle :

Code: Select all

...........1..2..3..4..5.6.......7.1.3.......5............8.......14...765.....3.

After basic steps and one UR we arrive at this state :

Code: Select all

+-----------+-----------+-----------+
|279 267 <5>|679 <3> <8>|<4> <1> 29 |
|89  689 <1>|<4> 69  <2>|<5> <7> <3>|
|<3> 279 <4>|79  <1> <5>|29  <6> <8>|
+-----------+-----------+-----------+
|48  48  <6>|<3> <5> <9>|<7> <2> <1>|
|17  <3> 29 |268 267 14 |69  48  <5>|
|<5> 17  29 |268 267 14 |<3> 48  69 |
+-----------+-----------+-----------+
|14  14  <7>|<5> <8> <3>|26  <9> 26 |
|29  29  <3>|<1> <4> <6>|<8> <5> <7>|
|<6> <5> <8>|29  29  <7>|<1> <3> <4>|
+-----------+-----------+-----------+

Where my solver finds r2c5<>9 and r3c2<>9 because of the Hidden BUG for 2, 6 and 9 :



But they are faulty as the solution for this puzzle is :

Code: Select all

+-----------+-----------+-----------+
|<2> <7> <5>|<6> <3> <8>|<4> <1> <9>|
|<8> <6> <1>|<4> <9> <2>|<5> <7> <3>|
|<3> <9> <4>|<7> <1> <5>|<2> <6> <8>|
+-----------+-----------+-----------+
|<4> <8> <6>|<3> <5> <9>|<7> <2> <1>|
|<7> <3> <2>|<8> <6> <1>|<9> <4> <5>|
|<5> <1> <9>|<2> <7> <4>|<3> <8> <6>|
+-----------+-----------+-----------+
|<1> <4> <7>|<5> <8> <3>|<6> <9> <2>|
|<9> <2> <3>|<1> <4> <6>|<8> <5> <7>|
|<6> <5> <8>|<9> <2> <7>|<1> <3> <4>|
+-----------+-----------+-----------+


I've checked with Sudoku wiki and this puzzle indeed has only one solution.

Am I doing something wrong ?

[MAGREMENT]

After some testing I believe the answer is that for the Hidden BUG to work, you need to take into account candidates removed by anything other than a solved cell as part of the pattern.

[eleven]

Thanx for this (counter-)example, which shows that the pattern must be there before applying a w-wing, which kicks out one of the 3 digits in a cell. The BUG does not hold, because placing the 7 there forces all 3 digits (and not exactly 2) to be elsewhere.
So i am wondering, if any other elimination but by singles may be done before the pattern must exist (e.g. subsets or locked candidates).
It seems, that RW made a mistake saying "what if some other reduction made by another technique is necessary to make the application of this technique possible..., but if it does the solution should be found this way". (i didn't understand, what he meant with "-> The order of how to do it: ...")

[MAGREMENT]

I believe the way to use this technique is not by looking at the candidates but the solved cells (this includes givens/clues and cells solved by the player). The definition my solver implements and that has not been proven false yet is this :

Code: Select all

For any number of n digits, if every non-solved cell can see either n solved digits or n-2 solved digits, the puzzle has multiple solution

This definition allows you to use this technique after other more complex techniques than singles & locked candidates/subsets.

For example, for the puzzle that was discussed previously in this thread, the pattern still holds after a xy-wing :




I sadly have not real proof of this, just that it doesn't give any wrong eliminations in 50k sudoku bank

[MAGREMENT]

Also, previously in this thread, the question of the frequency of the pattern was asked. In my 50k Sudoku bank, only 9 puzzles have this pattern (which is quite rare) :

Code: Select all

................12..3..4........5..4.1.....67.8..3.......81......5...3...6.2.....
................12..3..4..5.....367..8.......29...........2...8...91......5...4..
................12..3.45.............6.1.....12.7...8.......4....4.6.5...7.2.....
................12..3.45.........3.4.1.2......6.7.3.......8......5...4..6..1.....
................12..3.45........3......1....6.75...8.......75...1.2.....6......3.
................12..3.45........3....1.6.....7.....5.....17..8....4......85...6..
..............1..2..3.4..5..............5.36.27...8.....63.....1....4...5.......7
..............1..2.34....5.....3.......5....62.......1..5...4...7.8...3.1....6...
........1........2..3..4.5......56...1..2.....72...........83..1........6..7..4..

Some interesting examples are :

-The #2 where some 7's in box 2 are eliminated from a Hidden double and an X-Wing but the pattern still works !



The guardians are 7r1c7, 7r2c7 and 7r8c7 => r3c7 <> 7, r7c7 <> 7

-The #3 with a single guardian



The guardian is 9r7c8 => r7c8 == 9

-The #6 which is quite unique. The hidden bug is for 4 candidates (2, 3, 7, 9) and it is the only technique harder than singles needed to solve the puzzle



The guardians are 9r3c8 and 9r5c7 => r3c7 <> 9, r4c8 <> 9, r6c8 <> 9, r1c7 <> 9

While going through the examples I have made 2 observations :
-Most of the time the pattern consist of a digit solved in every box except 2 in the same band. The 2 other digits are solved only in the box with the 3rd digit in this band. (Like #2)
-This pattern is very often found in puzzle having Reverse BUG's or Reverse BUG-Lite's

[eleven]

Code: Select all

For any number of n digits, if every non-solved cell can see either n solved digits or n-2 solved digits, the puzzle has multiple solution

Yes, that's a nice idea. Then to use it, you can apply any technique you want (but the pattern could only be simplified, if it leads to solved cells).
I guess, it could be proved similar to Nick's proof for a BUG, though even more complicated: take a solution, and for unsolved cells, which in the solution hold a number of the n digits, show, that there must be another solution by exchanging these numbers in a defined way.

[Edit:]At second glance it's already proved, because after removing these numbers from the solution grid you must have a BUG pattern, and therefore a second solution.
[Edit2:] Corrected the link to the proof, seems that no one was interested to see it

[eleven]

Maybe this is, what RW meant with "You should not touch the pairs in the pattern".

This is a BUG+2 by tso from the above mentioned thread:

Code: Select all

     5    1    3    | 67  *27+6 9    | 46   8    24
     8    6    4    | 1    23   5    | 7    9    23
     7    2    9    | 4    8    36   | 5    36   1
     ---------------+----------------+-------------
     1    34   5    | 36   46   8    | 2    7    9
     6    9    2    | 37   57   1    | 8    4    35
     34   7    8    | 9    45   2    | 1    35   6
     ---------------+----------------+-------------
     9    8    6    | 5    1    4    | 3    2    7
     34  *35+4 1    | 2    9    7    | 46   56   8
     2   #45   7    | 8    36   36   | 9    1    45

Though it is a sample for a BUG+2 with 5-digits 34567, from the solved cells you would have an additional candidate 3 in r9c2. But the pair 36 removes it.
So i think, not only solved cells, but also locked candidates and subsets with one of the digits can be counted to check for a hidden bug (because the whole unit can't have these digits elsewhere).