The New Sudoku Players' Forum

[giant]

Is there any information about sudoku with the maximal number of clues
such that removal of anyone of those makes the sudoku
unsolvable??

[dukuso]

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]

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.

[Ocean]

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?

[coloin]

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 !

[Wolfgang]

Fine observation, coloin. I wouldnt have bet a cent, that it is possible to fix 10 clues in a given grid and then add 8 clues to get an easy 18 or to add 23 clues to get a hard 33. The mystery of sudoku lives

[coloin]

It certainly does.

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.

[Moschopulus]

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.

[coloin]

Thanks for the verif.
Does it help in getting a 34 ?

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 !

[Ocean]

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

#

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 !

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.

[coloin]

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.

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 ?

[Moschopulus]

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.

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.

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:

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.

[coloin]

I dont think conjecture 2B is correct -

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

[Red Ed]

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.

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.

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

[Ocean]

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

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.

With similar "add-ons" we can explain all the 7 solutions/permutations for the g1 case.

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

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

Y2 is an unavoidable set, in which X2 is a subset.

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.

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

Thanks for the verification!

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.

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.