How close together are the isomorphs of two random grids ?

Everything about Sudoku that doesn't fit in one of the other sections

Postby RW » Sun Nov 16, 2008 10:22 am

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.

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

Do you have a 18 cell example of this?

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby Red Ed » Sun Nov 16, 2008 11:49 am

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.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby Addlan » Sun Nov 16, 2008 7:16 pm

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?
Addlan
 
Posts: 62
Joined: 15 July 2005

Postby RW » Sun Nov 16, 2008 7:28 pm

Red Ed wrote: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
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby Addlan » Sun Nov 16, 2008 8:07 pm

RW wrote: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
......
Last edited by Addlan on Tue Nov 18, 2008 1:02 pm, edited 1 time in total.
Addlan
 
Posts: 62
Joined: 15 July 2005

Postby RW » Mon Nov 17, 2008 2:28 am

Addlan wrote:
RW wrote: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
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby Addlan » Tue Nov 18, 2008 4:01 pm

RW wrote: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
 
Posts: 62
Joined: 15 July 2005

Postby Addlan » Tue Nov 18, 2008 4:45 pm

RW wrote: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).
Addlan
 
Posts: 62
Joined: 15 July 2005

Postby RW » Tue Nov 18, 2008 9:55 pm

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
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby coloin » Wed Nov 19, 2008 1:56 am

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
coloin
 
Posts: 1637
Joined: 05 May 2005

Postby JPF » Wed Nov 19, 2008 2:12 am

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

JPF
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby Addlan » Thu Nov 20, 2008 7:58 pm

JPF wrote: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?
Addlan
 
Posts: 62
Joined: 15 July 2005

Postby Red Ed » Thu Nov 20, 2008 9:02 pm

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.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby RW » Fri Nov 21, 2008 2:59 am

Red Ed wrote: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
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby coloin » Fri Nov 21, 2008 3:43 am

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 ?
coloin
 
Posts: 1637
Joined: 05 May 2005

PreviousNext

Return to General