The New Sudoku Players' Forum

[David P Bird]

Unless one knows the contents of all cells in a unit (row, column, box), I don't believe there can be a hidden anything.

Yes quite true when we are solving and I see your perspective, but then I don't see how a candidate can be a naked single in a bivalue cell as per your correction.

However we're hypothesising not solving, and if your pattern existed, it would form locked sets in rows 1 & 3 which gives r13c13579 <> ABCD. Consequently we don't need to know the distribution of the other candidates to apply that analysis.

My posts are far more verbose than yours, and in trying to emulate your terse style, I didn't think that needed spelling out.

[David P Bird]

Here's an alternative proof that might be worth a higher grade . Again it considers ways to reduce each pattern cell to a bivalue:

Code: Select all

*------------*--------------*-----------*
| \  abcd \  | abcd \  abcd | \  abcd \ |
| .  .    .  | \    \  \    | .  .    . |
| \  abcd \  | abcd \  abcd | \  abcd \ |
*------------*--------------*-----------*

1) In either box 1 or box 3 two member digits must be true in row 2 which will leave the pattern cells holding a naked pair. This will force the other two member digits in row 2 to be true in the mirror box to leave its pattern cells holding the complementary naked pair.

2) In column 4 or 6 two member digits must be true in rows 456789 which will leave a naked pair in box 2. This in turn forces the mirror cells to hold the complementary naked pair.

Taking these steps in either order reduces the pattern to a BUG (either an 8-cell DP or two 4-cell DPs).

Provided the pattern candidates in each column are identical in both rows, all sub-patterns will be deadly with 0 or 2 solutions. The restriction ensures that no link to just one candidate in the pattern from an external cell is possible, as that would allow a unique solution to be found.

[daj95376]

[Withdrawn: inappropriate]

[ronk]

My hope is/was to derive a proof that a MUG is always a deadly pattern as long as it is generated from a valid BUG-Lite. The generation method is to overlay all permutations of clue values for the BUG-Lite as shown earlier. Then pattern-by-pattern proofs of MUGs being deadly would not be required. The pattern I chose was just a starting point.

In going from BUG-Lite to MUG and then back to BUG-Lites/URs we start and end with cell sets, i.e., strong inference sets comprised of candidates of cells. Although it makes little sense to me to convert to unit sets, i.e., strong inference sets comprised of candidates of rows, columns and/or boxes, doing so might aid in deriving a proof. Ditto for using unavoidable sets.

[David P Bird]

My hope is/was to derive a proof that a MUG is always a deadly pattern as long as it is generated from a valid BUG-Lite. The generation method is to overlay all permutations of clue values for the BUG-Lite as shown earlier. Then pattern-by-pattern proofs of MUGs being deadly would not be required. The pattern I chose was just a starting point.

That conjecture seems to be eminently sensible. Here's a stab at a generalised proof:

In a BUG the pattern makes locked set in every house it covers which is what isolates it from the rest of the puzzle. This ensures that no single pattern candidate has a unique link to an external cell. When the various permutations of a BUG-Lite are overlaid therefore this property is preserved, but some houses will no longer contain locked sets.

Now each one of those 'unlocked' houses has a capacity for holding external instances of member digits, but when that capacity is exhausted the pattern cells will return to being locked sets. Repeating this for every unlocked house will inevitably restore the pattern to a completely locked state.

In this process it isn't necessary to consider any limitations on which particular combinations of member digits can be held in external cells or where they are located as at the end the reduced pattern will either be impossible or have two solutions.

All we need to find is any counter-examples to tell us if any additional provisos are needed.

[ronk]

[edit: invalid BUG-Lite withdrawn]

[David P Bird]

All we need to find is any counter-examples to tell us if any additional provisos are needed.

Well, there is this BUG-Lite:MUG pair where the MUG has no locked sets.

Code: Select all

 .  ab .  | .  ac .  | .  bc .        .    abcd .    | .    abcd .    | .    abcd .
 .  ac .  | .  ad .  | .  cd .        .    abcd .    | .    abcd .    | .    abcd .
 .  bc .  | .  cd .  | .  bd .        .    abcd .    | .    abcd .    | .    abcd .
----------|----------|----------     ----------------|----------------|----------------
 .  .  .  | .  .  .  | .  .  .        .    .    .    | .    .    .    | .    .    .
 BUG-Lite                             MUG

Perhaps this BUG-Lite is not minimal, but I don't see a smaller deadly pattern there.

That’s good! You've found an interesting case as your BUG-Lite has zero solutions with two cells (I think) needing to hold non members.

I've little time available today but it quickly looking at it, my tentative proof depends on it being impossible for any combination of external assignments to reduce a member digit to a single instance in any house. Your crossed triples in rows and mini-columns allows that though. For example assigning the same digit to r1c1 and r2c4 would isolate it in r3c8.

As you say, no locked set survives when the pattern is permutated which causes another problem needing further provisos as any supposed assignment will simultaneously create locked sets in two or three houses, but that's probably easier to deal with.

None of the patterns I briefly played with yesterday gave such problems but caused me to wonder if you would have any rules to follow regarding how to permutate the larger bugs covering several tiers and stacks?

[ronk]

That’s good! You've found an interesting case as your BUG-Lite has zero solutions with two cells (I think) needing to hold non members.

That's not good, as the conjecture is meant to apply to valid BUG-Lites only.

[David P Bird]

I meant good in the sense that it brought us closer to finding the conditions under which the conjecture will hold.

Your bivalue pattern is certainly a valid Deadly Pattern as it has no solutions, which is the way I'm using that term.

However, here's a BUG-Lite with two solutions that produces the same problem when it's expanded:

Code: Select all

*--------*--------*--------*
| . ab . | . bc . | . ca . |
| . da . | . .  . | . ad . |
| . bd . | . cb . | . dc . |
*--------*--------*--------*

It's the mini-columns containing locked sets that cause the trouble.

[ronk]

Your bivalue pattern is certainly a valid Deadly Pattern as it has no solutions, which is the way I'm using that term.

For me it makes no sense to use patterns with no solution as "seeds for generating MUGs", and I've been careful not to use the deadly pattern term in that sense. IOW I don't believe we apply uniqueness techniques to patterns with no solution.

[David P Bird]

For me it makes no sense to use patterns with no solution as "seeds for generating MUGs", and I've been careful not to use the deadly pattern term in that sense. IOW I don't believe we apply uniqueness techniques to patterns with no solution.

In my view it doesn't matter as patterns with 0 or 2 solutions must both be avoided. However it would be distracting to argue the point. We can simply wait to see if anything we find only applies to one case.

Code: Select all

 *----------*----------*----------*   *----------*----------*----------*
 | D# ab D# | .  ac .  | .  bc .  |   |    ab    | D# bc D# |    ca    |
 | .  ca .  | B# ad B# | .  cd .  |   | C# da C# |          | B# ad B# |
 | .  cb .  | .  cd .  | A# bd A# |   |    bd    | A# cb A# |    dc    |
 *----------*----------*----------*   *----------*----------*----------*

Here are the last two bivalue patterns with 0 and 2 solutions repeated with the external cells capable of holding member digits shown by A# etc. These show that the external cells in the tier can only hold one instance of a member digit. When the patterns are permutated individual identities are lost, but we know that this restriction must still apply.

If nothing else this produces a minor theorem whereby all the external cells in the tier are weakly linked with respect to any member digit if the permuted patterns or derivatives of them are found. (This finding is independent of whether the pattern has zero or two solutions.)

Furthermore, I can't get a pattern with 4 member digits and with 3 mini-columns fully occupied ever to produce two solutions. I order the digits in the cells as I go which shows up contradictions once one row and one column has been entered and the further options are considered.

[ronk]

I can't get a pattern with 4 member digits and with 3 mini-columns fully occupied ever to produce two solutions. I order the digits in the cells as I go which shows up contradictions once one row and one column has been entered and the further options are considered.

If you're referring to the so-called BUG-Lite I posted, I already admitted it was bogus. One proper seed pattern would have been this impermeable MUG.

Code: Select all

 .  abc .  | .  ab  .  | .  ac  .         .    abcd .    | .    abcd .    | .    abcd .
 .  ab  .  | .  abd .  | .  ad  .   ==>   .    abcd .    | .    abcd .    | .    abcd .
 .  ac  .  | .  ad  .  | .  acd .         .    abcd .    | .    abcd .    | .    abcd .
-----------|-----------|-----------      ----------------|----------------|----------------
 .  .   .  | .  .   .  | .  .   .         .    .    .    | .    .    .    | .    .    .
 impermeable MUG                          permeable MUG

If nothing else this produces a minor theorem whereby all the external cells in the tier are weakly linked with respect to any member digit if the permuted patterns or derivatives of them are found. (This finding is independent of whether the pattern has zero or two solutions.).

How does this pertain to the thread title "Forming MUGs from BUG-Lite composites", or to proving that the formed patterns are indeed MUGs?

[David P Bird]

I can't get a pattern with 4 member digits and with 3 mini-columns fully occupied ever to produce two solutions. I order the digits in the cells as I go which shows up contradictions once one row and one column has been entered and the further options are considered.

If you're referring to the so-called BUG-Lite I posted, I already admitted it was bogus. One proper seed pattern would have been this impermeable MUG.

Code: Select all

 .  abc .  | .  ab  .  | .  ac  .         .    abcd .    | .    abcd .    | .    abcd .
 .  ab  .  | .  abd .  | .  ad  .   ==>   .    abcd .    | .    abcd .    | .    abcd .
 .  ac  .  | .  ad  .  | .  acd .         .    abcd .    | .    abcd .    | .    abcd .
-----------|-----------|-----------      ----------------|----------------|----------------
 .  .   .  | .  .   .  | .  .   .         .    .    .    | .    .    .    | .    .    .
 impermeable MUG                          permeable MUG

This poses the question as to whether a 'valid' impermeable MUG must have more than one solution in your view, as that one doesn't. It's certainly deadly though.

From my previous post, a different member digit must be true in an external cell in each box, added to which no row can hold two external member digits.

Code: Select all

 *----------------*----------------*----------------*
 | a    cb-d .    | .    cd   .    | .    db   .    |
 | .    dc   .    | b    ac-d .    | .    ad   .    |
 | .    bd   .    | .    da   .    | c    ba-d .    |
 *----------------*----------------*----------------*

This is the result shown with the surviving candidates ordered together with those that will be excluded as a consequence of that ordering. This therefore has permutated a pattern that has no solutions into one that could have two solutions.

If nothing else this produces a minor theorem whereby all the external cells in the tier are weakly linked with respect to any member digit if the permuted patterns or derivatives of them are found. (This finding is independent of whether the pattern has zero or two solutions.).

How does this pertain to the thread title "Forming MUGs from BUG-Lite composites", or to proving that the formed patterns are indeed MUGs?

Why you make this point baffles me. It was just an observation akin to noticing that the penicillin in breadmould kills bacteria. If you consider I'm wasting bandwidth, then aren't you wasting even more in responding to it?

[daj95376]

One proper seed pattern would have been this impermeable MUG.

Code: Select all

 .  abc .  | .  ab  .  | .  ac  .         .    abcd .    | .    abcd .    | .    abcd .
 .  ab  .  | .  abd .  | .  ad  .   ==>   .    abcd .    | .    abcd .    | .    abcd .
 .  ac  .  | .  ad  .  | .  acd .         .    abcd .    | .    abcd .    | .    abcd .
-----------|-----------|-----------      ----------------|----------------|----------------
 .  .   .  | .  .   .  | .  .   .         .    .    .    | .    .    .    | .    .    .
 impermeable MUG                          permeable MUG

This poses the question as to whether a 'valid' impermeable MUG must have more than one solution in your view, as that one doesn't. It's certainly deadly though.

It doesn't? What did I do wrong?

Code: Select all

 .  abc .  | .  ab  .  | .  ac  .
 .  ab  .  | .  abd .  | .  ad  .
 .  ac  .  | .  ad  .  | .  acd .
-----------|-----------|-----------
 .  .   .  | .  .   .  | .  .   .
 impermeable MUG



 .  c   .  | .  b   .  | .  a   .
 .  b   .  | .  a   .  | .  d   .
 .  a   .  | .  d   .  | .  c   .
-----------|-----------|-----------
 .  .   .  | .  .   .  | .  .   .


 .  b   .  | .  a   .  | .  c   .
 .  a   .  | .  b   .  | .  d   .
 .  c   .  | .  d   .  | .  a   .
-----------|-----------|-----------
 .  .   .  | .  .   .  | .  .   .


 .  a   .  | .  b   .  | .  c   .
 .  b   .  | .  a   .  | .  d   .
 .  c   .  | .  d   .  | .  a   .
-----------|-----------|-----------
 .  .   .  | .  .   .  | .  .   .


 .  a   .  | .  b   .  | .  c   .
 .  b   .  | .  d   .  | .  a   .
 .  c   .  | .  a   .  | .  d   .
-----------|-----------|-----------
 .  .   .  | .  .   .  | .  .   .


[David P Bird]

Apologies, I got that wrong. The annoying thing is that on retracing my steps I don't know how I managed it.

Nevertheless, unlike you ronk, I'm happy to accept permutations of positions with zero solutions as the basis for producing new deadly patterns and it has to be admitted that the 'bogus' BUG-Lite and the impermeable MUG produce identical patterns. Given that in a puzzle we'll be looking at the child and won't be able to divine its parentage, I've yet to be convinced that we need bother to make any distinction.