Is there any information about sudoku with the maximal number of clues

such that removal of anyone of those makes the sudoku

unsolvable??

Is there any information about sudoku with the maximal number of clues

such that removal of anyone of those makes the sudoku

unsolvable??

such that removal of anyone of those makes the sudoku

unsolvable??

- giant
**Posts:**18**Joined:**09 August 2005

giant wrote:Is there any information about sudoku with the maximal number of clues

such that removal of anyone of those makes the sudoku

unsolvable??

below are 6 with 30 clues.

Found by removing clues randomly from the 306693 first sudokugrids

in my file of G-classes.

By generating 1million random locally minimal sudokus starting

from an empty grid I got no 30 at all !

....78.....46.15....5....8.2..7..8..4.9..6........3.46..1...25.6.2...41..58.123.9

..25...8.8..96...5.652.4.3121..7....3.6.......976.........5.8.96...92.5.......12.

14..5.78..6........75.8.4.1.1...364....17....739.6..........37..9.....244....51.9

..........3.....6195.68.7..51.....7.6837....5.49.1.6.3.6...7.893..16.......92....

.32..75.68.....2.39....3.81..3...9..5.863.............274.1.3.9.....5647..5...1..

1.2..67.5..53.72........8..2.9.....8..78.....68.2..91..2174....4..9......9.1..4.2

edit: a second randomized run with 306693 minimal sudokus gave only one 30-clue-sudoku:

1..5..7.....7.429.9.762.84..1..46.....8.1.4.2..92.....5....2.89...4....7...1.8...

One such run takes 30min, so if there is a 31-clue minimal sudoku

it's probably not so easy to find with this method.

I also tried starting with the canonical sudoku, where you can easily

put 27 clues which can't be removed:

147......

...258...

......369

471......

...582...

......693

714......

...825...

......936

2985984 solutions.

.. and then adding some more clues until there is only one solution,

then removing superfluous clues.

But this didn't lead to any 30-clue-minimal sudoku.

- dukuso
**Posts:**479**Joined:**25 June 2005

here is one with 32 clues:

- Code: Select all

12...67..

78.12.45.

4.......3

.3..6489.

....9..31

8..2.....

3.2.45...

64.97....

.....2.4.

found by randomly deleting clues from the "canonical" grid.

- dukuso
**Posts:**479**Joined:**25 June 2005

dukuso wrote:here is one with 32 clues:

Here are 16 'internally related' minimal sudokus with 33 clues:

- Code: Select all
`*-----------*`

|.2.|.48|.6.|

|468|3.1|.7.|

|...|7..|...|

|---+---+---|

|914|8..|...|

|286|1..|3.9|

|...|...|...|

|---+---+---|

|83.|6..|59.|

|.7.|...|...|

|6.9|28.|73.|

*-----------*

#

020048060468301005000700000914800000286100309000000000800600590070000000640285730

020048060468301005000700000914800000286100309000000000830600590070000000600285730

020048060468301005000700000914800000286100309000000000830600590070000000609280730

020048060468301005000700000914800600286100009000000000830600590070000000609280730

020048060468301005000700000984100000216800309000000000800600590070000000640285730

020048060468301005000700000984100000216800309000000000830600590070000000600285730

020048060468301005000700000984100000216800309000000000830600590070000000609280730

020048060468301005000700000984100600216800009000000000830600590070000000609280730

020048060468301070000700000914800000286100309000000000800600590070000000640285730

020048060468301070000700000914800000286100309000000000800600590070000000649280730

020048060468301070000700000914800000286100309000000000830600590070000000600285730

020048060468301070000700000914800000286100309000000000830600590070000000609280730

020048060468301070000700000984100000216800309000000000800600590070000000640285730

020048060468301070000700000984100000216800309000000000800600590070000000649280730

020048060468301070000700000984100000216800309000000000830600590070000000600285730

020048060468301070000700000984100000216800309000000000830600590070000000609280730

Can anyone find a 34?

- Ocean
**Posts:**442**Joined:**29 August 2005

- Code: Select all
`+---+---+---+`

|.2.|...|...|

|...|...|..5|

|39.|7.6|8..|

+---+---+---+

|...|...|6..|

|.1.|.5.|..9|

|7..|...|...|

+---+---+---+

|8..|...|...|

|...|91.|...|

|6..|...|73.|

+---+---+---+ 18 clues

+---+---+---+

|.2.|.48|.6.|

|468|3.1|..5|

|...|7..|...|

+---+---+---+

|984|1..|6..|

|216|8..|..9|

|...|...|...|

+---+---+---+

|83.|6..|59.|

|.7.|...|...|

|6.9|28.|73.|

+---+---+---+ 33 clues [from previous post]

But there is 10 similar clues !

The 10 cant be good and bad at the same time - but it seems they are !

So 8 clues cover exactly the same unavoidable sets as 23 clues !

Last edited by coloin on Thu Feb 23, 2006 1:01 am, edited 1 time in total.

- coloin
**Posts:**1702**Joined:**05 May 2005

It certainly does.

The above maximum puzzle of 33 = collection of 33 given clues[g1,g2,g3,g3....g33] and 48 insertable clues[i]

I think there will be found 33 unavoidable sets each of which will contain only ONE of the given clues. [Otherwise it wont be minimal]

i.e.

the unavoidable sets which we will find will be equivalent to

Here is the unavoidable set with g1 clue - the 2 in r1c2 [a small 6 clue unavoidable]

Here is the unavoidable set with the g30 clue - the 2 in r9c4 [27 clue unavoidable]

Any of those other clues will complete the puzzle but it then wont be a minimal puzzle[I think]

I am not quite sure about it but.....if you can find 34 clues/sets in a grid like this then you might have a 34 puzzle.

EDIT

Am I assuming that each final clue in a maximum only hits one unavoidable set ? Yes this would appear to be so - I will check the rest of the clues.

EDIT 2 No - in this grid many of the clues hit 2 [or more] unavoidable sets

It possibly is irrelevant as for example a minimum puzzle of say 17 clues each of the final clues hits/intersects many unavoidables at the same time. But to have the largest maximum possible - it would be logical that each final clue only hits one unavoidable set.

The above maximum puzzle of 33 = collection of 33 given clues[g1,g2,g3,g3....g33] and 48 insertable clues[i]

- Code: Select all
`+---+---+---+`

|.2.|.48|.6.|

|468|3.1|..5|

|...|7..|...|

+---+---+---+

|984|1..|6..|

|216|8..|..9|

|...|...|...|

+---+---+---+

|83.|6..|59.|

|.7.|...|...|

|6.9|28.|73.|

+---+---+---+

+---+---+---+

|igi|igg|igi|

|ggg|gig|iig|

|iii|gii|iii|

+---+---+---+

|ggg|gii|gii|

|ggg|gii|iig|

|iii|iii|iii|

+---+---+---+

|ggi|gii|ggi|

|igi|iii|iii|

|gig|ggi|ggi|

+---+---+---+

I think there will be found 33 unavoidable sets each of which will contain only ONE of the given clues. [Otherwise it wont be minimal]

i.e.

the unavoidable sets which we will find will be equivalent to

- Code: Select all
`{g1,i,i,i,i,i,i}`

........

{g2+i,i,i,i,i,i,i,i,i,i,i,i,....}

{g3+i,i,i,i,i,i,i,i,i,i,i,i,.....}

{g4+i,i,i,i,i,i,i,i,i,i,i,i,....}

........

{i,i,i,i,i,i,i,i,i,i,i,i,i,i,i,i,i,i,i,i,i,i,i,i,i,g30,i}

{i,i,i,i,g33,i}

Here is the unavoidable set with g1 clue - the 2 in r1c2 [a small 6 clue unavoidable]

- Code: Select all
`+---+---+---+`

|.2.|...|9..|

|...|.9.|2..|

|.9.|.2.|...|

+---+---+---+

|...|...|...|

|...|...|...|

|...|...|...|

+---+---+---+

|...|...|...|

|...|...|...|

|...|...|...|

+---+---+---+ only the 2 in r1c2 is in the 33 puzzle

Here is the unavoidable set with the g30 clue - the 2 in r9c4 [27 clue unavoidable]

- Code: Select all
`+---+---+---+`

|1..|5..|9..|

|...|.9.|2..|

|..5|.2.|.14|

+---+---+---+

|...|..2|.5.|

|...|.57|.4.|

|...|4..|12.|

+---+---+---+

|..1|.74|..2|

|..2|91.|4..|

|...|2.5|...|

+---+---+---+only the 2 in r9c4 is in the 33 puzzle

Any of those other clues will complete the puzzle but it then wont be a minimal puzzle[I think]

I am not quite sure about it but.....if you can find 34 clues/sets in a grid like this then you might have a 34 puzzle.

EDIT

Am I assuming that each final clue in a maximum only hits one unavoidable set ? Yes this would appear to be so - I will check the rest of the clues.

EDIT 2 No - in this grid many of the clues hit 2 [or more] unavoidable sets

It possibly is irrelevant as for example a minimum puzzle of say 17 clues each of the final clues hits/intersects many unavoidables at the same time. But to have the largest maximum possible - it would be logical that each final clue only hits one unavoidable set.

Last edited by coloin on Mon Feb 27, 2006 8:19 pm, edited 1 time in total.

- coloin
**Posts:**1702**Joined:**05 May 2005

coloin wrote:I think there will be found 33 unavoidable sets each of which will contain only ONE of the given clues. [Otherwise it wont be minimal]

Yes, for each clue in a minimal puzzle, there is an unavoidable set that contains only that clue and no other clues.

In a valid puzzle, the set of clues hits every unavoidable set.

In a minimal puzzle, removing any clue leaves an unavoidable set that is not hit by the remaining clues, because there are multiple solutions. That unavoidable set must have contained only that clue.

- Moschopulus
**Posts:**256**Joined:**16 July 2005

Thanks for the verif.

Does it help in getting a 34 ?

The 9 clue at r5c9 covers two unavoidable sets.

Room for improvement then !

Does it help in getting a 34 ?

coloin wrote:Am I assuming that each final clue in a maximum only hits one unavoidable set ? Yes this would appear to be so - I will check the rest of the clues.

The 9 clue at r5c9 covers two unavoidable sets.

Room for improvement then !

- coloin
**Posts:**1702**Joined:**05 May 2005

Moschopulus wrote:coloin wrote:I think there will be found 33 unavoidable sets each of which will contain only ONE of the given clues. [Otherwise it wont be minimal]

Yes, for each clue in a minimal puzzle, there is an unavoidable set that contains only that clue and no other clues.

In a valid puzzle, the set of clues hits every unavoidable set.

In a minimal puzzle, removing any clue leaves an unavoidable set that is not hit by the remaining clues, because there are multiple solutions. That unavoidable set must have contained only that clue.

The connection to unavoidable sets is interesting. When switching to minimal unavoidables, two main points are, if I get it right:

1. A minimal unavoidable set U in a grid G is hit by at least one clue in every valid sudoku S where G is the solution grid.

2. In a minimal sudoku S, for every clue C there is at least one minimal unavoidable set U where C is the only clue in U.

Point 2 can possibly be split into:

Conjecture:

2A. If removing a clue C from a minimal sudoku S results in a pseudo-puzzle P2 with exactly two solutions, then there is exactly one minimal unavoidable set U where C is the only clue in U.

2B. If removing a clue C from a minimal sudoku S results in a puzzle Pn with n solutions, and n>2, then the there are at least two minimal unavoidable sets where C is the only clue. [Edit: Proved wrong by counterexample. Therefore: 2B. If removing a clue C from a minimal sudoku S results in a puzzle Pn with n solutions, and n>2, then the there are between 1 and n-1 minimal unavoidable sets where C is the only clue.]

Removing one clue from the 33-sudoku in the examle gives rise to five 32-clues pseudo-puzzles with 2 solutions. The five clues (from rows 2, 7 and 9) are marked with arrows:

- Code: Select all
`+---+---+---+`

|.2.|.48|.6.|

|468|3.1|..5| <-6,3,5

|...|7..|...|

+---+---+---+

|984|1..|6..|

|216|8..|..9|

|...|...|...|

+---+---+---+

|83.|6..|59.| <-9

|.7.|...|...|

|6.9|28.|73.| <-9

+---+---+---+

Removing the first '2' (in r1c2), results in a puzzle with 7 solutions. Therefore we would expect to find [Edit] between one and six different minimal unavoidables sets where this '2' is the only clue. Further, removing the '4' in row 1 results in a puzzle with 5 solutions, etc, etc.

The whole list (Number of solutions for each 32-puzzle obtained by removing one clue from the 33-sudoku):

7,5,3,11,13,2,17,2,22,2,3,9,7,4,9,9,4,11,5,4,24,3,7,25,5,2,13,21,2,5,6,51,15.

- Code: Select all
`The five pseudos correspond to these minimal unavoidable sets:`

#1 - Size 6: 11-14-20-24-50-51

+-----------+

|...|...|...|

|.6.|.9.|...|

|.9.|..6|...|

|---+---+---|

|...|...|...|

|...|...|...|

|...|.69|...|

|---+---+---|

|...|...|...|

|...|...|...|

|...|...|...|

+-----------+

#2 - Size 10: 13-14-23-24-32-33-50-51-67-69

+-----------+

|...|...|...|

|...|39.|...|

|...|.26|...|

|---+---+---|

|...|.32|...|

|...|...|...|

|...|.69|...|

|---+---+---|

|...|...|...|

|...|9.3|...|

|...|...|...|

+-----------+

#3 - Size 4: 30-31-42-43

+-----------+

|...|...|...|

|...|...|.75|

|...|...|...|

|---+---+---|

|...|...|.57|

|...|...|...|

|...|...|...|

|---+---+---|

|...|...|...|

|...|...|...|

|...|...|...|

+-----------+

#4 - Size 12: 25-27-49-51-53-54-60-62-63-67-70-71

+-----------+

|...|...|...|

|...|...|...|

|...|...|8.4|

|---+---+---|

|...|...|...|

|...|...|...|

|...|4.9|.28|

|---+---+---|

|...|..4|.92|

|...|9..|48.|

|...|...|...|

+-----------+

#5 - Size 26: 1-3-19-21-25-27-41-42-46-48-49-51-53-54-57-59-60-63-64-66-67-68-70-71-75-78

+-----------+

|1.7|...|...|

|...|...|...|

|3.5|...|8.4|

|---+---+---|

|...|...|...|

|...|.57|...|

|7.3|4.9|.28|

|---+---+---|

|..1|.74|..2|

|5.2|91.|48.|

|..9|..5|...|

+-----------+

coloin wrote:The 9 clue at r5c9 covers two unavoidable sets.coloin wrote:Am I assuming that each final clue in a maximum only hits one unavoidable set ? Yes this would appear to be so - I will check the rest of the clues.

Room for improvement then !

If the conjecture (2A/2B above) is correct, for this particular sudoku we should expect to find [Edit:] between 33 and 295 minimal unavoidable sets hit by only one clue.

Last edited by Ocean on Sun Feb 26, 2006 4:26 am, edited 2 times in total.

- Ocean
**Posts:**442**Joined:**29 August 2005

I agree with a lot of what you say.

I think we have to be careful not to confuse grid solutions and clue completions.[I know you know]

The number of grid solutions is not particularly helpful in this context...as you say if one clue completes the grid then this clue is in at least one unavoidable set. In the context of a maximum sudoku if there is only one unavoidable set then all the clues in this will complete the grid....but at the expense of making a few other clues in the grid superfluous.

I dont think you can say from the number of solutions >2 that there will always be more than one unavoidable set involved.........the first '2' r1c2 has 7 grid solutions but only one unavoidable set. I think the larger "solution number" clues will tend to have more than 1 unavoidable sets. In maximum sudokus it tends to be 1.

The unavoidables covered by one clue.......

EDIT

I thought you were talking about the number of unavoidables covered by a single clue in an empty grid/on isertion of the first given......I have wondered if thus could be calculated easily ? ......we know the unavoidables< size 45 ,add 10 clues what have you got left ?.....you can cover it in 8 or 23 clues...!

How much furthur than 33 clues do you think we can go ?

I think we have to be careful not to confuse grid solutions and clue completions.[I know you know]

The number of grid solutions is not particularly helpful in this context...as you say if one clue completes the grid then this clue is in at least one unavoidable set. In the context of a maximum sudoku if there is only one unavoidable set then all the clues in this will complete the grid....but at the expense of making a few other clues in the grid superfluous.

ocean wrote:Removing the first '2' (in r1c2), results in a puzzle with 7 solutions. Therefore we would expect to find at least two different minimal unavoidables sets U1 and U2 where this '2' is the only clue in both U1 and U2.

I dont think you can say from the number of solutions >2 that there will always be more than one unavoidable set involved.........the first '2' r1c2 has 7 grid solutions but only one unavoidable set. I think the larger "solution number" clues will tend to have more than 1 unavoidable sets. In maximum sudokus it tends to be 1.

The unavoidables covered by one clue.......

EDIT

I thought you were talking about the number of unavoidables covered by a single clue in an empty grid/on isertion of the first given......I have wondered if thus could be calculated easily ? ......we know the unavoidables< size 45 ,add 10 clues what have you got left ?.....you can cover it in 8 or 23 clues...!

How much furthur than 33 clues do you think we can go ?

Last edited by coloin on Mon Feb 27, 2006 8:23 pm, edited 2 times in total.

- coloin
**Posts:**1702**Joined:**05 May 2005

Ocean wrote:1. A minimal unavoidable set U in a grid G is hit by at least one clue in every valid sudoku S where G is the solution grid.

You can remove the word "minimal" here and it is still true.

Ocean wrote:2. In a minimal sudoku S, for every clue C there is at least one minimal unavoidable set U where C is the only clue in U.

What I said was "In a minimal sudoku S, for every clue C there is at least one unavoidable set U where C is the only clue in U. " I didn't say that U is a minimal unavoidable set. This might be true .... it doesn't seem obvious to me. Maybe I am being stupid.

Ocean wrote:Conjecture:

2A. If removing a clue C from a minimal sudoku S results in a pseudo-puzzle P2 with exactly two solutions, then there is exactly one minimal unavoidable set U where C is the only clue in U.

That is true. We discussed that in the pseudo-puzzles thread:

Red Ed wrote:As a side note: an alternative to your proof would be to note that any pseudo puzzle on n clues must have its solutions differing by a unique minimal unavoidable set, from which you can borrow any clue to make a uniquely-solvable puzzle on n+1 clues.

Not sure about 2B.

- Moschopulus
**Posts:**256**Joined:**16 July 2005

I dont think conjecture 2B is correct -

This one

These are the clue completions following the removal of the 2 clue at r9c4. [5 grid solutions]

I am presuming it is an unavoidable !

I have looked at the 51 grid solutions with one clue r9c7 removed

This specific grid has 10 clue completions around this clue.

The 7 clue at r9c7 is the only minimal one

Here is the clues .....but It doesnt look like an unavoidable set ! It must be the conjoint clues in two large unavoidables.

The pseudo puzzle [2 grid solutions] issue is easy - one unavoidable set - clue completions as per unavoidable - only one clue tends to give a minimal puzzle.

Those with low grid solution numbers will tend to be clue completed with the clues from one unavoidable set. I would tend to think that the more of these single unavoidables the better.

It is strange to be trying not to solve the grid !!!

coloin wrote:Here is the unavoidable set with g1 clue - the 2 in r1c2 [a small 6 clue unavoidable]

- Code: Select all
`+---+---+---+`

|.2.|...|9..|

|...|.9.|2..|

|.9.|.2.|...|

+---+---+---+

|...|...|...|

|...|...|...|

|...|...|...|

+---+---+---+

|...|...|...|

|...|...|...|

|...|...|...|

+---+---+---+ only the 2 in r1c2 is in the 33 puzzle

This one

- Code: Select all
`+---+---+---+`

|1..|5..|9..|

|...|.9.|2..|

|..5|.2.|.14|

+---+---+---+

|...|..2|.5.|

|...|.57|.4.|

|...|4..|12.|

+---+---+---+

|..1|.74|..2|

|..2|91.|4..|

|...|2.5|...|

+---+---+---+

These are the clue completions following the removal of the 2 clue at r9c4. [5 grid solutions]

I am presuming it is an unavoidable !

I have looked at the 51 grid solutions with one clue r9c7 removed

- Code: Select all
`+---+---+---+`

|.2.|.48|.6.|

|468|3.1|..5|

|...|7..|...|

+---+---+---+

|984|1..|6..|

|216|8..|..9|

|...|...|...|

+---+---+---+

|83.|6..|59.|

|.7.|...|...|

|6.9|28.|73.|

+---+---+---+ 7 clue at r9c7 removed - 51 grid solutions

This specific grid has 10 clue completions around this clue.

The 7 clue at r9c7 is the only minimal one

Here is the clues .....but It doesnt look like an unavoidable set ! It must be the conjoint clues in two large unavoidables.

- Code: Select all
`+---+---+---+`

|...|...|...|

|...|...|27.|

|...|...|...|

+---+---+---+

|...|.3.|..7|

|...|...|.4.|

|...|...|12.|

+---+---+---+

|...|...|...|

|...|...|4..|

|...|...|7.1|

+---+---+---+

The pseudo puzzle [2 grid solutions] issue is easy - one unavoidable set - clue completions as per unavoidable - only one clue tends to give a minimal puzzle.

Those with low grid solution numbers will tend to be clue completed with the clues from one unavoidable set. I would tend to think that the more of these single unavoidables the better.

It is strange to be trying not to solve the grid !!!

- coloin
**Posts:**1702**Joined:**05 May 2005

Of course this is true! A grid is uniquely specified by a set of clues iff those clues hit all minimal unavoidables. If removing some C gives you multiple solutions then you've gone from hitting all minimals to missing some collection, M, of them: so C was the only clue on those sets in M.Moschopulus wrote:What I said was "In a minimal sudoku S, for every clue C there is at least one unavoidable set U where C is the only clue in U. " I didn't say that U is a minimal unavoidable set. This might be true .... it doesn't seem obvious to me.Ocean wrote:2. In a minimal sudoku S, for every clue C there is at least one minimal unavoidable set U where C is the only clue in U.

Is there ever any reason to talk about non-minimal unavoidability? I don't think so.

- Red Ed
**Posts:**633**Joined:**06 June 2005

Thanks to coloin, Moschopulus and Red Ed for good comments, corrections and inspirations!

You are right! The case with the g1 clue (- the 2 in r1c2 - where there is only one minimal unavoidable set) proves 2B was not correct. (I have edited the original post, and changed a few things which were based on the false assumption.)

This case is also interesting when we try to analyse why there is more than two solutions. With a few "add-ons" we get this (non-minimal) unavoidable set:

This is not an unavoidable set. Proof: Subtract the set X1 from the solution grid G. The result S1 is a valid sudoku, therefore X1 is not unavoidable.

...and likewise this is not unavoidable. Proof as above: Subtract the set X2 from the solution grid G. The result S2 is a valid sudoku, therefore X2 is not unavoidable.

Thanks for the verification!

Thanks for verification of conjecture 2A.

This leaves only 2B wrong. I have rephrased it in the above post (2B: If removing a clue C from a minimal sudoku S results in a puzzle Pn with n solutions, and n>2, then the there are between 1 and n-1 minimal unavoidable sets where C is the only clue.), and also given it a different form in conjecture X below.

I think there might be reasons... but it's easier to explain if we call the baby something else (at least temporarily):

Definitions:

1. A permutable set is an alternative name for an unavoidable set.

2. A k-permutable set (for k>=2) is a permutable set that has k valid permutations.

3. A minimal k-permutable set is a k-permutable set that does not contain any other k-permutable set.

[Edit:]False conjecture 1. A minimal unavoidable set is a minimal 2-permutable set.

[Edit:]False conjecture 2. A k-permutable set contains between 1 and k-1 minimal 2-permutable sets as subsets.

Conjecture 1. A minimal unavoidable set is a minimal k-permutable set.

Conjecture 2. A k-permutable set contains between 1 and k-1 minimal unavoidable sets as subsets.

Conjecture X. If removing one clue C from a minimal sudoku S results in a puzzle with n solutions, then there is exactly one minimal n-permutable set X where C is the only clue contained in that set. All minimal k-permutable sets in S which do not contain other clues than C are subsets of X.

The first figure in this post (unavoidable set with add-on) is an example of a minimal 3-permutable set.

coloin wrote:I dont think conjecture 2B is correct -

You are right! The case with the g1 clue (- the 2 in r1c2 - where there is only one minimal unavoidable set) proves 2B was not correct. (I have edited the original post, and changed a few things which were based on the false assumption.)

This case is also interesting when we try to analyse why there is more than two solutions. With a few "add-ons" we get this (non-minimal) unavoidable set:

- Code: Select all
`+---+---+---+`

|.2.|...|9..|

|...|.9.|2..|

|.9.|.26|...|

+---+---+---+

|...|...|...|

|...|...|...|

|...|.69|...|

+---+---+---+

|...|...|...|

|...|...|...|

|...|...|...|

+---+---+---+ "add-on": gives an unavoidable set with 3 possible permutations.

coloin wrote:This one

- Code: Select all
`+---+---+---+`

|1..|5..|9..|

|...|.9.|2..|

|..5|.2.|.14|

+---+---+---+

|...|..2|.5.|

|...|.57|.4.|

|...|4..|12.|

+---+---+---+

|..1|.74|..2|

|..2|91.|4..|

|...|2.5|...|

+---+---+---+

These are the clue completions following the removal of the 2 clue at r9c4. [5 grid solutions]

I am presuming it is an unavoidable !

This is not an unavoidable set. Proof: Subtract the set X1 from the solution grid G. The result S1 is a valid sudoku, therefore X1 is not unavoidable.

- Code: Select all
`127548963468391275395726814984132657216857349753469128831674592572913486649285731 G`

1..5..9......9.2....5.2..14.....2.5.....57.4....4..12...1.74..2..291.4.....2.5... X1

.27.48.634683.1.7539.7.68..98413.6.72168..3.9753.69..883.6..59.57...3.86649.8.731 S1

coloin wrote:The 7 clue at r9c7 is the only minimal one

Here is the clues .....but It doesnt look like an unavoidable set ! It must be the conjoint clues in two large unavoidables.

...

...and likewise this is not unavoidable. Proof as above: Subtract the set X2 from the solution grid G. The result S2 is a valid sudoku, therefore X2 is not unavoidable.

- Code: Select all
`127548963468391275395726814984132657216857349753469128831674592572913486649285731 G`

...............27..............3...7.......4.......12................4........7.1 X2

127548963468391..53957268149841.265.2168573.9753469..8831674592572913.86649285.3. S2

..75..9.3....9.27.395.2..14....32..7....5734.753469128..1.74..2..2913486......7.1 Y2

Red Ed wrote:...Of course this is true! A grid is uniquely specified by a set of clues iff those clues hit all minimal unavoidables. If removing some C gives you multiple solutions then you've gone from hitting all minimals to missing some collection, M, of them: so C was the only clue on those sets in M.Moschopulus wrote:What I said was "In a minimal sudoku S, for every clue C there is at least one unavoidable set U where C is the only clue in U. " I didn't say that U is a minimal unavoidable set. This might be true .... it doesn't seem obvious to me.Ocean wrote:2. In a minimal sudoku S, for every clue C there is at least one minimal unavoidable set U where C is the only clue in U.

Thanks for the verification!

Moschopulus wrote:Ocean wrote:Conjecture:

2A. If removing a clue C from a minimal sudoku S results in a pseudo-puzzle P2 with exactly two solutions, then there is exactly one minimal unavoidable set U where C is the only clue in U.

That is true. We discussed that in the pseudo-puzzles thread

Thanks for verification of conjecture 2A.

This leaves only 2B wrong. I have rephrased it in the above post (2B: If removing a clue C from a minimal sudoku S results in a puzzle Pn with n solutions, and n>2, then the there are between 1 and n-1 minimal unavoidable sets where C is the only clue.), and also given it a different form in conjecture X below.

Red Ed wrote:Is there ever any reason to talk about non-minimal unavoidability? I don't think so.

I think there might be reasons... but it's easier to explain if we call the baby something else (at least temporarily):

Definitions:

1. A permutable set is an alternative name for an unavoidable set.

2. A k-permutable set (for k>=2) is a permutable set that has k valid permutations.

3. A minimal k-permutable set is a k-permutable set that does not contain any other k-permutable set.

[Edit:]False conjecture 1. A minimal unavoidable set is a minimal 2-permutable set.

[Edit:]False conjecture 2. A k-permutable set contains between 1 and k-1 minimal 2-permutable sets as subsets.

Conjecture 1. A minimal unavoidable set is a minimal k-permutable set.

Conjecture 2. A k-permutable set contains between 1 and k-1 minimal unavoidable sets as subsets.

Conjecture X. If removing one clue C from a minimal sudoku S results in a puzzle with n solutions, then there is exactly one minimal n-permutable set X where C is the only clue contained in that set. All minimal k-permutable sets in S which do not contain other clues than C are subsets of X.

The first figure in this post (unavoidable set with add-on) is an example of a minimal 3-permutable set.

Last edited by Ocean on Mon Feb 27, 2006 7:02 pm, edited 1 time in total.

- Ocean
**Posts:**442**Joined:**29 August 2005