## Interesting question...

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

### Interesting question...

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.

~Thomas
T_Schellhous

Posts: 1
Joined: 10 February 2006

### Re: Interesting question...

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

77
angusj

Posts: 306
Joined: 12 June 2005

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

Posts: 295
Joined: 02 January 2006

### Re: Interesting question...

T_Schellhous wrote: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.
Red Ed

Posts: 633
Joined: 06 June 2005

### Re: Interesting question...

Red Ed wrote: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
gfroyle

Posts: 214
Joined: 21 June 2005

Think it means "maximal minimal sudoku" ..... what is the max number of clues in a minimal puzzle.
Last edited by Moschopulus on Sat Feb 11, 2006 10:07 am, edited 2 times in total.
Moschopulus

Posts: 256
Joined: 16 July 2005

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
MCC

Posts: 1275
Joined: 08 June 2005

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.
Last edited by Red Ed on Sat Feb 11, 2006 7:40 pm, edited 2 times in total.
Red Ed

Posts: 633
Joined: 06 June 2005

MCC wrote: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
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

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

thanks, this clears up my confusion
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Red Ed wrote: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.
Ocean

Posts: 442
Joined: 29 August 2005

MCC wrote:
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
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Ocean wrote: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 ...?
Red Ed

Posts: 633
Joined: 06 June 2005

gsf wrote:
MCC wrote:
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
MCC

Posts: 1275
Joined: 08 June 2005

MCC wrote: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
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Next