The New Sudoku Players' Forum

[Myth Jellies]

Note that in the interest of brevity, I will refer to BUG-lites as BUGs in this thread.

So I think we can use the 2 or nothing BUG rule to find all of the Bivalue deadly patterns (bivalue meaning deadly patterns that are limited to two candidates per cell) which includes unique rectangles. This can help solve a lot of puzzles. However, this technique usually isn't much help when most of your cells contain more than 2 candidates, as is the case in most of the really tough puzzles. The question now becomes, what's the rule for finding deadly patterns that allow for more than two candidates per cell (MUGs, or Multivalued Universal Graves).

I believe that most MUGs are just composites made up of several BUG-lites. Lets look at a few simple setups....

Code: Select all

12 | 123 13
12 | 12  .
------------
.  | 13  13

This is a MUG which is made up of the following two BUGs

Code: Select all

12 | 12  .      .  | 13  13
12 | 12  .      .  | .   . 
-----------  and -----------
.  | .   .      .  | 13  13 

This works even if the two BUGs do not have a candidate in common, for example...

Code: Select all

12 | 1234 34
12 | 12  .
------------
.  | 34   34

I think (not sure) the following pattern would also be a MUG...

Code: Select all

 .   .   abc | abc  .  .  |  .   .   .
 .   .   abc | abc  .  .  |  .   .   .
 .   .   abc | abc  .  .  |  .   .   .


In the above example, the BUG rule will find 9 deadly rectangles. If you take the union of all the deadly rectangle bases, you end up with all of the abc's shown. Yet not every union of BUG's results in a MUG. For example, we know the following...

Code: Select all

 .   .   abc | abc  .  .  |  .   .   .
 .   .   abc | abc  .  .  |  .   .   .
 .   .   .   | .    .  .  |  .   .   .


Is not a deadly pattern MUG even though it is made up of BUG uniqueness rectangles.

So there are a couple of questions here...

1. How can you tell for sure if you have a deadly pattern MUG?

For example, can you tell if the following patterns are MUGs?

Code: Select all

 .   .   abc | abc  .  .  |  .   .   .
 .   .   abc | abc  .  .  |  .   .   .
 .   .   ab  | ab   .  .  |  .   .   .


and

Code: Select all

 .   .   ab  | abc  .  .  |  bc  .   .
 .   .   ab  | abc  .  .  |  bc  .   .
 .   .   .   | .    .  .  |  .   .   .


2. Are there some simple rules about how you can join BUGs together to guarantee you make a MUG?

Is it a number of overlapping cells kind of thing...one guess might be that two BUGs form a MUG so long as all the overlapping cells of the two deadly patterns can be restricted to a single group? BUGs can also be added to MUGs to form bigger MUGs as well??? We know it must work if there is a pattern overlap in only a single cell.

Anyone else have some ideas or comments?

[vidarino]

I think (not sure) the following pattern would also be a MUG...

Code: Select all

 .   .   abc | abc  .  .  |  .   .   .
 .   .   abc | abc  .  .  |  .   .   .
 .   .   abc | abc  .  .  |  .   .   .


Hmm, I'm not so sure about that. If you consider the rows separately, there would have to be an extra a, b or c somewhere outside the pattern, or you'd have to cram three values into two cells, a feat reserved for none but the toughest solvers. ;)

And as far as I can tell, a *UG has to be "self-contained", as in no extra visible candidates outside the pattern.

Or at least I think so?

[Myth Jellies]

I am going to propose that a MUG candidate is really a deadly pattern if you cannot find a group and a candidate where if you got rid of that candidate in that group you would have a valid puzzle pattern that was not a BUG or a MUG. For example...

Code: Select all

 .   .   ab  | abc  .  .  |  bc  .   .
 .   .   ab  | abc  .  .  |  bc  .   .
 .   .   .   | .    .  .  |  .   .   .


...this is a deadly pattern, because you can not get rid of the a's, b's, or c's in any row, column, or box without leaving an impossible pattern for a puzzle with a unique solution. Removing the b's from the middle box leaves a BUG-lite, and clearing any character from any other group will leave a pattern with no solution.

This rule would mean that...

Code: Select all

12 | 1234 34
12 | 12  .
------------
.  | 34   34

...and...

Code: Select all

 .   .   ab  | ab   .  .  |  .   .   .
 .   .   abc | abc  .  .  |  .   .   .
 .   .   bc  | bc   .  .  |  .   .   .


...and...

Code: Select all

 .   .   abc | abc  .  .  |  .   .   .
 .   .   abc | abc  .  .  |  .   .   .
 .   .   ab  | ab   .  .  |  .   .   .


...are all MUGs, but...

Code: Select all

 .   .   abc | abc  .  .  |  .   .   .
 .   .   abc | abc  .  .  |  .   .   .
 .   .   .   | .    .  .  |  .   .   .


...would not be a deadly pattern (because you can get rid of the c's in row 1 and still have a valid pattern for a single solution puzzle. Note that this rule would also apply correctly to BUG-Lite candidates.

[aeb]

I think (not sure) the following pattern would also be a MUG...

Code: Select all

 .   .   abc | abc  .  .  |  .   .   .
 .   .   abc | abc  .  .  |  .   .   .
 .   .   abc | abc  .  .  |  .   .   .


Yes, because one can interchange the two columns (of height 3).

So there are a couple of questions here...

1. How can you tell for sure if you have a deadly pattern MUG?

For example, can you tell if the following patterns are MUGs?

Code: Select all

 .   .   abc | abc  .  .  |  .   .   .
 .   .   abc | abc  .  .  |  .   .   .
 .   .   ab  | ab   .  .  |  .   .   .


Yes, assuming each abc/abc/ab lies in a single box. This is a subset and contains a,b,c. Interchange two columns (of height 3) and find a new solution.

Code: Select all

 .   .   ab  | abc  .  .  |  bc  .   .
 .   .   ab  | abc  .  .  |  bc  .   .
 .   .   .   | .    .  .  |  .   .   .


Again yes, interchanging the three elements in both rows gives a new solution.

The rule is always: find an involution and it will have orbits of sizes 1 and 2. Those of size 2 give an even number of solutions, so can be discarded.

[Myth Jellies]

And as far as I can tell, a *UG has to be "self-contained", as in no extra visible candidates outside the pattern.

I am using a more lenient *UG definition which encompasses unique rectangle deadly patterns as well as BUG-Lites. Both of these must have at least one base candidate outside of the pattern as well, or else the puzzle would be forced into multiple solutions.

[vidarino]

I am using a more lenient *UG definition which encompasses unique rectangle deadly patterns as well as BUG-Lites. Both of these must have at least one base candidate outside of the pattern as well, or else the puzzle would be forced into multiple solutions.

Ah, doh, yes, of course, silly me. *slaps self*

I was stuck in a "unavoidable sets" mindset, where I was imagining hunting for potential *UGs in the solved grid, and of which at least one cell would have to be a given to ensure a unique solution.

Vidar

[aeb]

I am going to propose that a MUG candidate is really a deadly pattern if you cannot find a group and a candidate where if you got rid of that candidate in that group you would have a valid puzzle pattern that was not a BUG or a MUG. For example...

Code: Select all

 .   .   ab  | abc  .  .  |  bc  .   .
 .   .   ab  | abc  .  .  |  bc  .   .
 .   .   .   | .    .  .  |  .   .   .


...this is a deadly pattern, because you can not get rid of the a's, b's, or c's in any row, column, or box without leaving an impossible pattern for a puzzle with a unique solution. Removing the b's from the middle box leaves a BUG-lite, and clearing any character from any other group will leave a pattern with no solution.

Hmm - a recursive definition. And I suppose it cannot be correct because there can be cardinality reasons that prevent you from getting rid of candidates in a group - it can be locked. For example, take an arbitrary puzzle, write candidates in the open squares and look at the pattern they form. You cannot find a row/column/box and a candidate such that the candidate can be removed because every candidate has to occur.

But it is true that the patterns you want to describe have a similar property - you want that if an oracle reveals all outside digits, there still is more than one solution. But the result of revealing all outside digits is discarding these digits from cells inside. So it suffices to have a pattern such that all possible results of discarding zero or more times a given digit from a given row or column or box leaves a pattern with more than one solution.

[Myth Jellies]

Hmm - a recursive definition. And I suppose it cannot be correct because there can be cardinality reasons that prevent you from getting rid of candidates in a group - it can be locked. For example, take an arbitrary puzzle, write candidates in the open squares and look at the pattern they form. You cannot find a row/column/box and a candidate such that the candidate can be removed because every candidate has to occur.

Arggh, I keep banging my head against the same wall . Perhaps the rule describes a necessary, but obviously not sufficient, characteristic possessed by deadly patterns. Perhaps if combined with the concept of the deadly pattern having multiple solutions...?

The rule is always: find an involution and it will have orbits of sizes 1 and 2. Those of size 2 give an even number of solutions, so can be discarded.

Though I sort of see what you are doing in your post, I am not sure I understand the terms above. Will this concept catch MUGs like the following?

Code: Select all

12 | 1234 34
12 | 12  .
------------
.  | 34   34

and

Code: Select all

 .     .     .    | .     .     .     
 .     abcd  ab   | acde  ae    .     
 .     cd    .    | cd    .     .     
------------------+-------------------
 .     cf    .    | cf    .     .     
 .     abcf  ab   | acef  ae    .     
 .     .     .    | .     .     .     

[aeb]

... Perhaps if combined with the concept of the deadly pattern having multiple solutions...?

Not satisfied with my "It suffices to have a pattern such that all possible results of discarding zero or more times a given digit from a given row or column or box leaves a pattern with more than one solution." ?

(If you want necessary and sufficient, I think you are too optimistic. One the one hand because there are many reasons why a pattern can be deadly, and on the other hand because even if we restrict ourselves to BUG-like setups, one can not necessarily remove digits independently from rows, columns and boxes by placing digits outside.)

Code: Select all

12 | 1234 34
12 | 12  .
------------
.  | 34   34

This one is not so interesting. E.g., apply BUG to 12 and conclude that 34 must occur. Now apply BUG to 34.

Code: Select all

 .     .     .    | .     .     .     
 .     abcd  ab   | acde  ae    .     
 .     cd    .    | cd    .     .     
------------------+-------------------
 .     cf    .    | cf    .     .     
 .     abcf  ab   | acef  ae    .     
 .     .     .    | .     .     .     

This one is much nicer. Hmm. But it is wrong, it seems. If my oracle gives me (1,2)a, then it becomes

Code: Select all

 .     a     .    | .     .     .     
 .     d     b    | e     a     .     
 .     c     .    | d     .     .     
------------------+-------------------
 .     f     .    | c     .     .     
 .     b     a    | f     e     .     
 .     .     .    | .     .     .     

and nothing is wrong with that. So this is not a configuration that forces non-uniquenes independent of the exterior.

[vidarino]

Code: Select all

12 | 1234 34
12 | 12  .
------------
.  | 34   34

This one is not so interesting. E.g., apply BUG to 12 and conclude that 34 must occur. Now apply BUG to 34.

Hmm, well, it's trivial if the actual configuration is the above pattern + 1 candidate (which must be the true one), but if there are two or more extras in the two rectangles, it might become useful;

Code: Select all

.   .   .    | .     .
.   .   125  | 1234  345
.   .   12   | 12    .   
-------------+----------
.   .   .    | 34    34

Now neither of the two rectangles lead to any immediate conclusion by themselves, but if you study them combined, you notice that if neither R2C3 nor R2C5 contains a 5, you'd have a MUG (or two BUGs, depending on how you see it). So you can eliminate 5 from the rest of the row.

I'm trying to add some BUG-Lite and MUG functionality to my solver, by the way. Would anyone be in possession of some puzzles that contain interesting patterns?

Thanks,
Vidar

[Myth Jellies]

Not satisfied with my "It suffices to have a pattern such that all possible results of discarding zero or more times a given digit from a given row or column or box leaves a pattern with more than one solution." ?

I'm afraid I just did not understand it at the time. I'm still not sure that I do. If you mean, "It suffices to have a pattern such that all possible results of discarding all of the occurances of a given digit within zero or more groups from the pattern leaves a pattern with zero or more than one solution." Then I agree. If you mean that you can pick off instances of the digit from anywhere in the pattern and hope to leave a multi-solution pattern, then that seems too restrictive. Even a deadly rectangle can't live up to that definition.

Good catch on my one pattern by the way (I like your oracle concept). I was only concentrating on removing candidates from a single group, and forgot about removing them from multiple groups.

[aeb]

Not satisfied with my "It suffices to have a pattern such that all possible results of discarding zero or more times a given digit from a given row or column or box leaves a pattern with more than one solution." ?

I'm afraid I just did not understand it at the time. I'm still not sure that I do. If you mean, "It suffices to have a pattern such that all possible results of discarding all of the occurances of a given digit within zero or more groups from the pattern leaves a pattern with zero or more than one solution." Then I agree.

We agree. A pattern is deadly if its occurrence makes sure there is no unique solution. For this it suffices that no matter how my oracle fills the outside, the inside does not have a unique completion. Each time a digit is placed on the outside it kills that digit in the corresponding row, column and box from the inside (and there is a correlation). Forgetting about this correlation one arrives at the sufficient condition:
"A pattern is deadly if every pattern that arises by discarding zero or more times all occurrences of a given digit from a given group is a pattern without unique solution."

It is possible to be slightly more precise and only consider oracles that fill the outside in a legal way. Then, when the outside has been filled, the remaining pattern is tight - each group has as many open cells as there are candidates for these cells.
(E.g., in the case of your nice pattern the first column has four cells with five candidates, and one needs not verify that this pattern as given fails to have a unique solution, it suffices to look at the situation that remains after a column erasure. That saves some work.)
Now the sufficient condition becomes: "A pattern is deadly if every tight pattern that arises ...".

[Myth Jellies]

I'm trying to add some BUG-Lite and MUG functionality to my solver, by the way. Would anyone be in possession of some puzzles that contain interesting patterns?

Unfortunately, I don't have a puzzle database. You can pick up a couple interesting ones from the various BUG and BUG Lite threads, though

[Myth Jellies]

I've run our test on this, and I am pretty sure this is a MUG pattern (if aeb proves this one wrong I think I might burst into tears).

Code: Select all

-------------------+-------------------+-------------------
 .     .     .     | .     .     .     | .     .     .     
 .     .     abcd  | abcd  abcd  .     | .     .     .     
 .     .     abcd  | abcd  abcd  .     | .     .     .     
-------------------+-------------------+-------------------
 .     .     .     | abcd  abcd  .     | .     .     .     
 .     .     .     | .     .     .     | .     .     .     
 .     .     .     | .     .     .     | .     .     .     
-------------------+-------------------+-------------------
 .     .     .     | .     .     .     | .     .     .     
 .     .     .     | .     .     .     | .     .     .     
 .     .     .     | .     .     .     | .     .     .     
-------------------+-------------------+-------------------

Note that there are a bunch of way to remove all of a candidate's digits in a group and still leave a workable pattern. Since the above is a MUG, any derived workable pattern must also be a MUG. For example, remove all of the d's in column 5 and you end up with this MUG...

Code: Select all

 .     .     abcd  | abcd  abc   .     | .     .     .     
 .     .     abcd  | abcd  abc   .     | .     .     .     
-------------------+-------------------+-------------------
 .     .     .     | abcd  abc   .     | .     .     .     

Now remove all the d's in the top row of the pattern. Note that the box 2 component of the pattern is a locked set. Thus the only remaining box 2 'd' in the pattern must be true. Remove the remaining d's that see the one in box 2 and you have the following MUG...

Code: Select all

 .     .     abc   | abc   abc   .     | .     .     .     
 .     .     abc   | d     abc   .     | .     .     .     
-------------------+-------------------+-------------------
 .     .     .     | abc   abc   .     | .     .     .     

If you use two similar operations to wipe out the c's in the middle row...

Code: Select all

 .     .     abc   | abc   abc   .     | .     .     .     
 .     .     ab    | d     ab    .     | .     .     .     
-------------------+-------------------+-------------------
 .     .     .     | abc   abc   .     | .     .     .     

...and column, you end up with this familiar MUG/BUG/Uniqueness Deadly Pattern

Code: Select all

 .     .     ab    | ab    c     .     | .     .     .     
 .     .     ab    | d     ab    .     | .     .     .     
-------------------+-------------------+-------------------
 .     .     .     | ab    ab    .     | .     .     .     

This shows a reduction of a MUG to a BUG...I'm wondering if there is an obvious reverse operation here...one that will grow a BUG into a MUG.

[vidarino]

I'm trying to add some BUG-Lite and MUG functionality to my solver, by the way. Would anyone be in possession of some puzzles that contain interesting patterns?

Unfortunately, I don't have a puzzle database. You can pick up a couple interesting ones from the various BUG and BUG Lite threads, though

Yep, thanks, I scraped a few examples from there, but I had more luck just going through my whole collection of random home-made ones.

Anyway, I'm still - like you, it seems - battling with the concept of defining a good, generic detection algorithm for these patterns. In the mean time, I have resorted to adding a few hard-coded patterns (such as the 2x3 and 3x2 deadly "sextuples"), coupled with a generic function on how to treat them when they're found (i.e. analogous to the different types of Unique Rectangle; single extra candidate = fix it, multiple occurrances of single extra number = elim from cells that see all extras, etc.)

Even with this rather minor extension of Unique Rectangles, it's already picking up some interesting shortcuts:

Code: Select all

      8      9      2 |      17     47      6 |       3      5     14
     14      7      3 |     125     45     25 |       6      8      9
   1456   1456    456 |       3      9      8 |      14      7      2
----------------------+-----------------------+----------------------
   1457   1458   4578 |      58      2      3 |       9      6    147
  12567  12568   5678 |       4     58      9 |      15      3     17
      3     45      9 |       6      1      7 |      45      2      8
----------------------+-----------------------+----------------------
      9      3     58 |    2578    578      1 |      27      4      6
    267     26     67 |       9      3      4 |       8      1      5
     45    458      1 |    2578      6     25 |      27      9      3


There's a potentially deadly 3x2-pattern in R58C123 (candidates 267), where the extra candidates in row 5 (15, 158 and 58) form a quantum cell of 158, which in turn forms a naked triple together with R5C5 and R5C7, eliminating the 1 in R5C9, leaving a naked 7!

Certainly not something one sees every day, but nice to catch.

Vidar