The New Sudoku Players' Forum

[T_Schellhous]

Hello. I am very interested in the mathematics behind these puzzles. I am happy to see so many people interested in the number of possible puzzles and the number of clues required to see a unique solution.

My question that I have been working on the past few days is a little different: What is the maximum number of clues that can be given without the puzzle having a unique solution? In other words, what is the limit on the number of clues such that one more clue will result in an inevitable unique solution.

If this has already been posted, sorry to waste your time.

~Thomas

[angusj]

What is the maximum number of clues that can be given without the puzzle having a unique solution?

77

[vidarino]

Yep, 77 it is. Here's a 77-clue grid that needs one more to have a unique solution;

Code: Select all

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

Either of the missing cells can be 2 or 6.

What's a bit more interesting is that for this particular solution grid (or rather, either of the two possible ones), one of these 4 cells *must* be part of an initial clue set for a unique solution to be present. That means they're part of a so-called "unavoidable set".

[Red Ed]

What is the maximum number of clues that can be given without the puzzle having a unique solution?

A more interesting question is: what's the maximum number of independent clues? -- see Sourendu Gupta's web site for this and other challenges. Best so far is 41.

[gfroyle]

A more interesting question is: what's the maximum number of independent clues? --

Looked at web page, but couldn't figure out definition of "independent" - set of clues such that none is "derivable from the others"...

What does that mean exactly?

Gordon

[Moschopulus]

Think it means "maximal minimal sudoku" ..... what is the max number of clues in a minimal puzzle.

[MCC]

Code: Select all

1..|...|..8
..6|3.9|7..
.4.|...|.3.
-----------
.8.|4.1|.9.
6..|.3.|..4
.7.|2.5|.8.
-----------
.9.|...|.1.
..4|1.6|8..
2..|...|..3

In the above grid, if any clue is removed from it then there is not enough information available to be able to replace the clue that was removed, this clue and other clues like this that cannot be replaced once removed are independent clues.

Look at cell r7c6 and the number 3.
All other cells in box 8 are covered by 3's in columns 4+5 and row 9, therefore the only place for the 3 is in r7c6, this 3 has been derived from the others.

MCC

[Red Ed]

Another way of putting it: you can relabel any single clue and still have a valid puzzle (possibly with multiple solutions).

Hmm... but looking at S.G.'s example, reproduced below, I think he has either made a mistake or is using a different definition of "independent" to me and Moschopulus. The 1 at row 3, column 4, is implied by the other clues.

Code: Select all

  123|456|78.
  456|78.|12.
  78.|12.|45.
  ---+---+---
  271|34.|...
  364|8..|...
  5..|271|...
  ---+---+---
  632|.17|...
  815|...|...
  ...|5..|...

I'll take a guess at where the problem lies. His greedy algorithm claims to "Enumerate all eliminated possibilities". I bet he does that by a sequence of necessary, but not necessarily sufficient, solving rules (hidden pairs and the like); when really he ought to test each remaining candidate by trying to solve with that candidate fixed in place.

I've mailed him, seeking clarification.

[gsf]

All other cells in box 8 are covered by 3's in columns 4+5 and row 9, therefore the only place for the 3 is in r7c6, this 3 has been derived from the others.
MCC

I must be missing something here

doesn't any hole in any minimal (valid) sudoku satisfy this?
minimal means that every clue is required for a unique solution
dropping any clue produces a puzzle with multiple solutions
therefore each hole can have only one value
and those values lead to the only solution

[gsf]

Think it means "maximal minimal sudoku" ..... what is the max number of clues in a minimal puzzle.

thanks, this clears up my confusion

[Ocean]

Hmm... but looking at S.G.'s example, reproduced below, I think he has either made a mistake or is using a different definition of "independent" to me and Moschopulus. The 1 at row 3, column 4, is implied by the other clues.

Code: Select all

  123|456|78.
  456|78.|12.
  78.|12.|45.
  ---+---+---
  271|34.|...
  364|8..|...
  5..|271|...
  ---+---+---
  632|.17|...
  815|...|...
  ...|5..|...

I actually can not see the point here, maybe somebody could explain...

First, this grid has 43 clues, not 41 as announced. Second, this grid has no solution (no 6 fits in the centre box). Third, this grid can be reduced to a 41 clue sudoku by removing two of the clues (there is only one valid way of doing that), but the resulting sudoku is not minimal.

[gsf]

Code: Select all

1..|...|..8
..6|3.9|7..
.4.|...|.3.
-----------
.8.|4.1|.9.
6..|.3.|..4
.7.|2.5|.8.
-----------
.9.|...|.1.
..4|1.6|8..
2..|...|..3

In the above grid, if any clue is removed from it then there is not enough information available to be able to replace the clue that was removed, this clue and other clues like this that cannot be replaced once removed are independent clues.

either the grid is bad or the claim is false
this grid is not minimal so there exist clues that can be dropped that result in a puzzle with one solution
e.g., [3,2] can be dropped (changed to a hole) and the puzzle still has only one solution with [3,2]=4
here are three minimal puzzles derived from the above by dropping clues

Code: Select all

# derived minimal #1

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

# derived minimal #2

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

# derived minimal #3

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


[Red Ed]

First, this grid has 43 clues, not 41 as announced. Second, this grid has no solution (no 6 fits in the centre box). Third, this grid can be reduced to a 41 clue sudoku by removing two of the clues (there is only one valid way of doing that), but the resulting sudoku is not minimal.

Oh dear! I confess I hadn't checked any of that, but had merely copied what I saw on Sourendu Gupta's web page.

I don't think the definition of independence should extend to insisting that the clues uniquely define a solution grid: it should just be that the number of solutions increases with the removal of any single clue. But that still doesn't give us any means of getting Gupta's 43 down to a (what-we're-calling) independent 41.

Anyway, enough picking at individual puzzles. A quick scan back through the archives found a similar thread called "Max number of clues". Back then, Guenter found an independent set of 32 clues which had the bonus property of being uniquely solvable. Can we do better if we drop the uniquely-solvable aspect, i.e. just aim for independence ...?

[MCC]

Code: Select all

1..|...|..8
..6|3.9|7..
.4.|...|.3.
-----------
.8.|4.1|.9.
6..|.3.|..4
.7.|2.5|.8.
-----------
.9.|...|.1.
..4|1.6|8..
2..|...|..3

In the above grid, if any clue is removed from it then there is not enough information available to be able to replace the clue that was removed, this clue and other clues like this that cannot be replaced once removed are independent clues.

either the grid is bad or the claim is false
this grid is not minimal so there exist clues that can be dropped that result in a puzzle with one solution
e.g., [3,2] can be dropped (changed to a hole) and the puzzle still has only one solution with [3,2]=4
here are three minimal puzzles derived from the above by dropping clues

Code: Select all

# derived minimal #1

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



The grid is a pappocom v.hard.
It was a puzzle I had to hand.
I did not intend to imply that the grid was minimal.
Or that it has one or multiple solutions.
But to use it to define 'Independent'/'Derivable' clues.

Looking at your # derived minimal #1
You have removed the 4 from [3,2], and the
1 from [4,6]

Can you, as the puzzle stands, replace these numbers with the information available before attempting to solve the puzzle?

If you cannot, then these clues are not derivable from the information available and, as such, are independent clues.

MCC

[gsf]

Looking at your # derived minimal #1
You have removed the 4 from [3,2], and the
1 from [4,6]

Can you, as the puzzle stands, replace these numbers with the information available before attempting to solve the puzzle?

If you cannot, then these clues are not derivable from the information available and, as such, are independent clues.

I haven't had my caffeine boost yet
but I'm having trouble parsing the question
maybe it stems from the fact that I see a direct relationship between "independence" and minimal puzzles

the minimal puzzle has one solution (by definition)
that means that each hole has only one value that leads to the one solution
how much more "derivable" can it get?
the holes in a minimal puzzle have no "independence"

I think that "independent" has been ill-defined to this point
terms like "derivable" and "information available" need to be clarified
or dropped for nomenclature already understood on the forums