The New Sudoku Players' Forum

[RW]

Thanks Red Ed for the example. These big unavoidables sure can be quite bizarre creatures...

So all weakly minimal unavoidables have valency >2. Next question is of course: Are all minimal unavoidables with valency >2 weakly minimal? I'm pretty sure the answer is yes, though I suppose you have more accurate information.

only a few of the bigger (18+ cells) unavoidables are weakly minimal.

Do you have a 18 cell example of this?

RW

[Red Ed]

I've started a mindless random search for valency >2 minimal unavoidables. In the first 100 or so there were no strong ones. I bet you're right. I wonder how to prove it ...?

I rather doubt that the current program is going to hit upon an 18. If time permits, I'll see if I can dig out my old code.

[Addlan]

An unavoidable set appears to be a mini-puzzle to me if I understand it correctly. Then disjoint unavoidable sets are disjoint mini-puzzles. Is it possible to define something which is related directly to the number of the solutions? e.g. the number of the mini-puzzles or something is the number of the solutions.

If the number of unavoidable sets is larger than the number of the solutions, those extra unavoidable sets may be deduced by other unavoidable sets - called the redundant unavoidable sets. If there are redundant unavoidable sets, is it possible to exclude them in the first place?

[RW]

I wonder how to prove it ...?

Tough one...

The corresponding deadly pattern to a hypothetical strongly minimal valency 3 unavoidable set would have to consist of three candidates in each cell and each candidate would have to appear three times in each unit. Such a pattern containing only three different digits will always have at least 6 solutions:

Code: Select all

 *--------------------------------------------------*
 | 7    369  8    | 369  369  5    | 4    2    1    |
 | 1    2    369  | 369  7    4    | 5    8    369  |
 | 4    5    369  | 2    1    8    | 369  7    369  |
 |----------------+----------------+----------------|
 | 369  7    2    | 5    8    369  | 369  1    4    |
 | 5    369  4    | 1    2    369  | 8    369  7    |
 | 369  8    1    | 4    369  7    | 2    5    369  |
 |----------------+----------------+----------------|
 | 369  1    7    | 369  5    2    | 369  4    8    |
 | 8    369  5    | 7    4    369  | 1    369  2    |
 | 2    4    369  | 8    369  1    | 7    369  5    |
 *--------------------------------------------------*

because once the first digit is solved, there is still two possible ways to solve the remaining two digits (solving one digit leaves a situation with two candidates in each cell and each candidate appears exactly twice in each unit = classic BUG).

I'm not 100% sure what happens if we add more different digits to the equation. I think the same will apply in some way, but I shall not make any claims yet. I've learned not to underestimate the surprising features of massive unavoidable sets...

RW

[Addlan]

I'm not 100% sure what happens if we add more different digits to the equation.

If we leave everything blank, it results in a valency 9 unavoidable set - the original Sudoku. Thus we may view Sudoku this way: to dismantle this big unavoidable set into little ones.

Valency 2 unavoidable set => 2 solutions
Valency 3 unavoidable set => 6 solutions
......

[RW]

I'm not 100% sure what happens if we add more different digits to the equation.

If we leave everything blank, it results in a valency 9 unavoidable set - the original Sudoku.

No. A valency 9 unavoidable set would be a set of cells of a solution grid that is minimally unavoidable and which can be permutated to 9 different valid solutions. An empty grid has a few more valid solution and it is not part of a solution grid.

Just to make clear, the example in my previous post is not the deadly pattern of a valency 3 unavoidable set. Neither is it a minimal deadly pattern. It has six solutions and every solution will contain smaller unavoidable sets. It was just an example to show why a valency 3 strongly minimal unavoidable set cannot exist with only three digits.

Anyway, your post at least reminded me of one thing we can know for certain: There are no strongly minimal valency 9 or valency 8 unavoidable sets!

RW

[Addlan]

No. A valency 9 unavoidable set would be a set of cells of a solution grid that is minimally unavoidable and which can be permutated to 9 different valid solutions.

Fine. But I am still confused.

[Addlan]

Anyway, your post at least reminded me of one thing we can know for certain: There are no strongly minimal valency 9 or valency 8 unavoidable sets!
RW

*-----------*
|...|...|...|
|...|...|...|
|...|...|...|
|---+---+---|
|...|218|679|
|...|654|238|
|...|937|145|
|---+---+---|
|...|493|861|
|...|725|394|
|...|186|527|
*-----------*
The first block is a valency 9 unavoidable set. Every cell in that block could be filled in with any of the 9 digits. However, I "guess" you are right. These can lead to more than 9 different valid solutions (permutation and leading to have the same effect to me actually).

[RW]

Addlan, it seems I caused some confusion when I earlier in this thread asked for the amount of unavoidable sets in empty cells. As Red Ed has shown us, the choice of terminology was bad, because unavoidable sets do not exist in empty cells, they exist in solution grids. I should rather have used "deadly pattern" which is what we use when talking about empty cells.

To clarify, this is a minimal unavoidable set:

Code: Select all

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

If you start removing givens from the solution grid, you may remove all but one clue from this set and still have an unique solution. But if you remove all marked clues, you get two solutions, the second solution being:

Code: Select all

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

The value of all cells marked with '*' has changed, while the rest of the puzzle has remained the same.

If you look at the empty cells when all clues are removed:

Code: Select all

                           | 36  35  56   
 ------------+-------------+------------ 
 45          | 34          |     35       
 45          | 34          | 36      56   

This is not an unavoidable set. It is a deadly pattern. A deadly pattern is a set of empty cells that always can be solved in at least two ways.

Also, please not that the valency>2 unavoidables discussed in this thread are extremely rare and very complex. As far as I know (correct me if I'm wrong Red Ed), none has yet been constructed manually, those we know of have been found by computers.

RW

[coloin]

Mauricio has just found a few 9-mutable puzzles

http://forum.enjoysudoku.com/viewtopic.php?p=64136#p64136

Code: Select all

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

9 grid solutions, solved with r1c1



The unavoidable sets /deadly patterns in these possibly might be interesting.

Do we want to change the title or move some of this thread to "Unavoidable sets and deadly patterns revisited" ?

C

[JPF]

IMO, a new thread on the unavoidables, with definitions, main known properties and so on... would be welcome.

JPF

[Addlan]

IMO, a new thread on the unavoidables, with definitions, main known properties and so on... would be welcome.
JPF

Agree, it would be much easier for the interested newbies on these subjects to catch up. Would it be possible to make it sticky in the forum?

[Red Ed]

Probably better to thrash out the details on Sudopedia, rather than fill a new sticky thread full of disagreements? There are plenty of aspects to this that are not agreed.

[RW]

Probably better to thrash out the details on Sudopedia, rather than fill a new sticky thread full of disagreements? There are plenty of aspects to this that are not agreed.

If there is lots of disagreements, then wouldn't a thread here be the right place to discuss them? I'm not sure what disagreements you talk about, though I can think of a lot that isn't researched properly yet.

I don't think it should be a sticky thread, we can't make sticky threads on every subject that deserves one. But I've always wished to see some kind of index sticky thread that would contain links to interesting, important and frequently quoted discussions hidden in the general/puzzle forum.

RW

[coloin]

Fair points, theres plenty of stuff weve thrashed out which could informatively and advantageously be transposed to "sudopedia" - but it would be a task.

EDIT...it has been started !! http://www.sudopedia.org/wiki/Deadly_Pattern

I am sure there are many who are inquisituive enough to wonder about the make up of the puzzles and their solutions - but never see the relevant [hidden] pages in this forum.

BTW...who moderates the sudopedia edits ?