The New Sudoku Players' Forum

[ronk]

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

The serious problem is the "expanded pattern" is not a MUG, as evidenced by this puzzle with a single solution:

Code: Select all

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

Unless there is an error here, my conjecture seems false.

[David P Bird]

Unless there is an error here, my conjecture seems false.

I'm not so sure about that. So far what we seem to have is the proviso if the resultant pattern contains a fully occupied mini-line it isn't guaranteed to be a MUG, something which I suspect won't be that common in practice.

I'm afraid I can't say whether the approach you used to construct your grid is conclusive or not as it's not an area I'm conversant with or tooled-up to explore.

What remains to be investigated is BUG-Lites with more than 4 digits that cover multiple stacks and tiers, when I wonder if the rules for permutating the candidate options may need to be investigated.

[ronk]

Unless there is an error here, my conjecture seems false.

I'm not so sure about that. So far what we seem to have is the proviso if the resultant pattern contains a fully occupied mini-line it isn't guaranteed to be a MUG, something which I suspect won't be that common in practice.

Your BUG-Lite is indeed an outlier, but for a different reason I think. The correct MUG for it is ...

Code: Select all

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

Note the MUG candidates in r2c5 where the BUG-Lite has none. Also note the result of the following "(x)" placements in the MUG's band (your "tier") and outside its pattern . That said, I don't foresee simple expansion and reduction rules I'm going to like.

Code: Select all

 .  ab  .  | .  bc (d) | .  ac  .
(c) ad  .  | .  .   .  | .  ad (b)
 .  bd  .  |(a) bc  .  | .  cd  .
-----------|-----------|-----------
 .  .   .  | .  .   .  | .  .   .

What remains to be investigated is BUG-Lites with more than 4 digits that cover multiple stacks and tiers, when I wonder if the rules for permutating the candidate options may need to be investigated.

We should probably first look at all three-digit and four-digit patterns. Is there an exhaustive catalog of these in unavoidable-set ("UA") form somewhere? In any form?

[David P Bird]

Your BUG-Lite is indeed an outlier, but for a different reason I think. The correct MUG for it is ...

Code: Select all

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

Note the MUG candidates in r2c5 where the BUG-Lite has none.

This confuses me as I don't understand how r2c5 becomes part of the pattern when the digits are pemutated.

Last week I thought your resultant pattern of quads wasn't a MUG, but today I investigated derivatives assuming that no pattern cell contains any other digit and consequently that no containing house could hold more than one external member digit:

Code: Select all

 .  abc .  | .  abd .  | .  acd .           d  abc . | .  ab  . |  . ac   . 
 .  abc .  | .  abd .  | .  acd .    ==>    .  ab  . | c  abd . |  . ad   .
 .  abc .  | .  abd .  | .  acd .           .  ac  . | .  ad  . |  b acd  .   
-----------|-----------|-------------       ---------|----------|-----------
 .  (d) .  | .  (c) .  | .  (b) .           .  .   . | .  .   . |  . .    .

This derivative is definitely a MUG because (d)box1 (c)box2 and (b)box3 must all be true in external cells on different rows to leave a version of the MUG pattern I made a hash of last week.

Code: Select all

 (d)  abc .  | .    abc  .  | .  abc  .         
 .    abc .  | (d)  abc  .  | .  abc  .         
 .    abc .  | .    abc  .  | .  abcd .           
-------------|--------------|-------------     
 .    .   .  | .    .    .  | .  .    .

This derivative leaves just r3c79 capable of holding a member digit. If it's (d) we get a 9-cell MUG and if it's anything else naked pairs force (d)r3c8 to leave an 8-cell MUG.

If these two examples essentially cover all the cases I was wrong before. If so, that's good news for your conjecture with respect to one band of boxes.

What I was saying before, that it should be impossible to reduce any member digit to a single cell, therefore doesn't feature as although this may make one cell solvable, what remains isn't.

We should probably first look at all three-digit and four-digit patterns. Is there an exhaustive catalog of these in unavoidable-set ("UA") form somewhere? In any form?

That’s sensible. The <Sudopedia Entry> is the only catalogue of deadly patterns that I'm aware of.

[dobrichev]

A list of one-band UA sets is available at http://sites.google.com/site/dobrichev/ua/one_band_ua.zip.

See also this topic.

[David P Bird]

Thanks dobrichev!

Here is an extract of the single band UAs with up to 5 digits

Hidden Text: Show

Code: Select all

2  ..............1..2.....2..1
   .....1..2..1..2.....2.....1
3  ...........1..2..3..2..3..1
   .....1..2.....2..3.....3..1
4  ...........1..2.34..3..4.21
   .....1..2..3..2..4..4..3..1
   .....1..2.13..2.4..42....31
   ....12.34..1.3..2...2..4..1
   ....12.34.12.34....34....21
   ....12.34.13.4..2..24..3..1
5  ...........1.23.45..2.45.31
   .....1..2....32.45....54.31
   .....1..2..3..2.45..5..4.31
   .....1..2.13.42.5..42.5..31
   .....1..2.13.42.5..52.3..41
   ....12.34..1.3..5...5..4.21
   ....12.34..1.34..5..3..5.21
   ....12.34..1.34.25..2..5..1
   ....12.34..1.35.2...3..4.51
   ....12.34..1.35.2...5..4..1
   ....12.34.12.34..5.35....21
   ..1..2..3..2..4.5...5..3.41
   ..1..2..3.2..41.5..43.5..12
   ..1..2.34.2..53.1..54.1...2
   ..1..2.34.23.14..5.5..3..21
   ..1..2.34.34.5..1..5..43..2

[ronk]

A list of one-band UA sets is available at http://sites.google.com/site/dobrichev/ua/one_band_ua.zip.

I too thank you for that list but, as is often the case, I have a question. I chose this 4-digit UA sets because it's the size currently being discussed.

Code: Select all

...........................................................1..2.13..2.4..42....31


It's easy to show that it is one of six essentially-different UAs for this [ed: band-]impermeable MUG:

Code: Select all

 .    .    .    | .    .    12   | .    .    12 
 .    1234 1234 | .    .    12   | .    1234 .
 .    1234 1234 | .    .    .    | .    1234 1234

Code: Select all

...........................................................1..2.31..2.4..24....13
...........................................................1..2.31..2.4..24....31
...........................................................1..2.31..2.4..42....13
...........................................................1..2.31..2.4..42....31
...........................................................1..2.34..2.1..12....43
...........................................................1..2.34..2.1..12....34

In grid checker, e.g., how are you dealing with essentially-different UAs for the same pattern?

[dobrichev]

Hi Ronk,

I don't know whether UA classification by pattern has ever been made.

If you are asking for something else, please rephrase.

[David P Bird]

Code: Select all

...........................................................1..2.13..2.4..42....31


It's easy to show that it is one of six essentially-different UAs for this impermeable MUG:

Code: Select all

 .    .    .    | .    .    12   | .    .    12 
 .    1234 1234 | .    .    12   | .    1234 .
 .    1234 1234 | .    .    .    | .    1234 1234

Code: Select all

...........................................................1..2.31..2.4..24....13
...........................................................1..2.31..2.4..24....31
...........................................................1..2.31..2.4..42....13
...........................................................1..2.31..2.4..42....31
...........................................................1..2.34..2.1..12....43
...........................................................1..2.34..2.1..12....34

In grid checker, e.g., how are you dealing with essentially-different UAs for the same pattern?

You need as new term for 'impermeable' as you are applying it here as the pattern is only impermeable with respect to external member digits in the rows and the boxes but not in the columns.

This is how the UA expands into a BUG-Lite with the pairs ordered:

Code: Select all

 .  .  .  | .  .  1  | .  .  2        .  .   .   | .  .  12  | .  .  21 
 .  1  3  | .  .  2  | .  4  .   ==>  .  14  32  | .  .  21  | .  43 .
 .  4  2  | .  .  .  | .  3  1        .  41  23  | .  .  .   | .  34 12

Note that r1c6 and r3c9 must be the same to be able to make an x-y chain through r1c9. But this only happens in two cases in your list of alternative UAs (Nos 2 & 4) and I don't think the others are valid.

Note also that by setting the pairing in r2c2 all the other pairings in this pattern are forced. I therefore presume that gridchecker is running some sort of canonicalising routine to screen out those that are essentially the same.

In the previous patterns we've discussed there's been a choice about which 3 digits would occupy the pattern cells in any house, but here we have two rows and two boxes where all of them are required. This forces (34)r1c45 which will be covered by some other UA. Some additional head scratching is therefore required, and I'm not sure if this will lead to rules that you'd like.

[ronk]

So lots of fuzzy thinking led me to think that this potential, i.e. prospective, MUG ...

Code: Select all

 .    .    .    | .    .    .    | .    .    .
----------------|----------------|----------------
 .    .    .    | .    .    1234 | .    .    1234
 .    1234 1234 | .    .    1234 | .    1234 .
 .    1234 1234 | .    .    .    | .    1234 1234


... was actually a MUG, but it is not. There are six essentially-different placements of the candidates, one of which is dobrichev's UA used as the "seed", three of which contain smaller UAs, and two of which are non-deadly. It's these two which prove the MUG prospect to be a false one.

I now think further effort to add one or more provisos to the earlier stated conjecture is fool-hardy. Indeed, I'm considering splitting off this recent discussion into a separate thread so as not to have polluted Myth Jellies' original thread.

[David P Bird]

So lots of fuzzy thinking led me to think ....

But you can't challenge my leadership in that field!

I now think further effort to add one or more provisos to the earlier stated conjecture is fool-hardy.

Certainly I don't think one simple generalisation will cover all eventualities and that a lot of plodding is required to check out the different possibilities. That said though, your concept has merit. It gives us a direction to follow in trying to determine what patterns are permeable MUGs because, however they are legitimately reduced, an impermeable MUG will remain.

I'm considering splitting off this recent discussion into a separate thread so as not to have polluted Myth Jellies' original thread.

I've no problem with that. If nothing else our exchanges have illustrated some of the potential pitfalls to avoid in this area which should be one of the purposes of this forum.

[RW]

So lots of fuzzy thinking led me to think that this potential, i.e. prospective, MUG ...

Code: Select all

 .    .    .    | .    .    .    | .    .    .
----------------|----------------|----------------
 .    .    .    | .    .    1234 | .    .    1234
 .    1234 1234 | .    .    1234 | .    1234 .
 .    1234 1234 | .    .    .    | .    1234 1234


... was actually a MUG, but it is not. There are six essentially-different placements of the candidates, one of which is dobrichev's UA used as the "seed", three of which contain smaller UAs, and two of which are non-deadly. It's these two which prove the MUG prospect to be a false one.

For each cell in an unavoidable set there must exist a digit that it can see in every unit. This is the value the cell will have in the other solution. If no such digit exists, then the cell cannot hold any other value without interfering with the cells outside the set and may thus not be a part of the unavoidable set.

The candidates in the set above can be placed in such a way that r7c6<>r9c9. In this case there is no digit that r6c9 can see in each house and the set is not unavoidable (though it can still contain smaller UAs).

[RW]

Code: Select all

 .  AB .  | AC .  BD | .  CD .
 .  .  .  | .  .  .  | .  .  .
 .  AB .  | AC .  BD | .  CD .
----------+----------+----------
 .  .  .  | .  .  .  | .  .  .

If for this BUG-Lite we overlay all 96 permutations of assignments of tokens <abcd> to <ABCD>, we have the following MUG:

Code: Select all

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

1. Given that the BUG-Lite is a deadly pattern, how does one elegantly prove that the MUG is a deadly pattern?

2. How does one elegantly prove that any possible reduction or permeation of the MUG is also a deadly pattern?

I don't have any nice proof for it, but I think you could define an unavoidable according to the rules I explained above. "For each cell in an unavoidable set there must exist a digit that it can see in every unit." Let's call this other digit which it can see in all houses a 'buddy digit'. If every cell in the set has a buddy digit which is unique for all cells in the same units (no two cells in the same unit may have the same buddy digit), then the set is unavoidable. When this is true you can simply replace the value in each cell with the buddy digit and you have a new solution that still includes the exactly same values in each house and as such can not be solved from the outside. Perhaps there is already somewhere a more elegant definition for this.

Looking at the MUG above, you can use this info to easily prove that it is a deadly pattern. Place any value a in any cell A and any other value b in the other cell in the box (which also shares the same column with cell A). Now value b must also appear somewhere in the same row as cell A => A can see b in all three houses and will have a buddy digit. This is true for all cells no matter how you place the values and no cells in the same unit can have the same buddy digit => No matter how you solve the MUG it will lead to an unavoidable set.

PS. This also leads to an interesting puzzle variant. Below is a 60 cell unavoidable set (found by Ocean). Find the other solution to the set by finding the unique buddy digit for each cell. I just solved it using only singles and pairs, might be solvable with singles only. (You can of course in this case also rely on symmetry, but that's no challenge...)

Code: Select all

 *-----------*
 |.68|973|.45|
 |7.2|1.5|689|
 |49.|82.|173|
 |---+---+---|
 |529|.14|.68|
 |3.1|6.7|9.2|
 |87.|59.|43.|
 |---+---+---|
 |.53|.69|.14|
 |614|2.8|3.7|
 |987|43.|52.|
 *-----------*

[Luke]

I have managed to convince myself that this pattern is a MUG in that it reduces to either URs or BUG-Lites or no solution. Of course, just because the reductions I’ve found so far have turned out that way don’t mean that all will.

Code: Select all

*----------------*-----------------*------------*
| .  abcde abcde | abcde  .  abcde | .  abcde . |
| .    .     .   |   .    .    .   | .    .   . |
| .  abcde abcde | abcde  .  abcde | .  abcde . |
*----------------*-----------------*------------*

Does applying your proof bear this out, or am I wrongly convinced?

[ronk]

I have managed to convince myself that this pattern is a MUG in that it reduces to either URs or BUG-Lites or no solution. Of course, just because the reductions I’ve found so far have turned out that way don’t mean that all will.

I'm interested in RW's response too, but it's a MUG. gsf's program shows that placements for this pattern ...

Code: Select all

 .     12345 12345 | 12345 .     12345 | .     12345 .   
 .     .     .     | .     .     .     | .     .     .
 .     12345 12345 | 12345 .     12345 | .     12345 .   
-------------------|-------------------|-------------------
 .     .     .     | .     .     .     | .     .     .

... produce only two essentially-different [edit: results. As RW later pointed out, the first is an overlay of a 4-cell and a 6-cell unavoidable, while the second is a 10-cell unavoidable.]

Code: Select all

 . 1 2 | 3 . 4 | . 5 .                . 1 2 | 3 . 4 | . 5 .
 . . . | . . . | . . .                . . . | . . . | . . .
 . 3 4 | 5 . 2 | . 1 .                . 3 4 | 2 . 5 | . 1 .
-------+-------+-------              -------+-------+-------
 . . . | . . . | . . .                . . . | . . . | . . .