## Least Upper Bound

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

### Least Upper Bound

Is there a number M such that the following is true:

If a pseudo-puzzle with 16 clues has M different completions, then we cannot add a clue to make a valid puzzle (1 completion) with 17 clues.

What is the smallest such M?

Another way of looking at it: suppose you have a valid sudoku with 17 clues. You remove one clue. Is there any limit on the number of completions the resulting pseudo-puzzle can have?
Moschopulus

Posts: 256
Joined: 16 July 2005

### Re: Least Upper Bound

Moschopulus wrote:suppose you have a valid sudoku with 17 clues. You remove one clue. Is there any limit on the number of completions the resulting pseudo-puzzle can have?
Well, by your original definition of pseudo-puzzle, the answer would have to be two !
Red Ed

Posts: 633
Joined: 06 June 2005

### Re: Least Upper Bound

Red Ed wrote:Well, by your original definition of pseudo-puzzle, the answer would have to be two !

You've got your bounds the wrong way round..

Consider all the 17s.. drop one clue from each and we get a whole range of pseudo-puzzles with 2, 4, 200, ... etc completions.

He wants the biggest possible number among this collection, call it N.

Then we would know for sure that if there was N+1 completions in a 16-pseudo then it could not be contained in a valid 17.

(Actually he phrased it as the search for M = N+1 but you get the idea..)

Does such an M exist? Yes clearly.. there are a finite number of 17s, and hence a finite number of 16 pseudo-puzzles arising from them, and hence we need the biggest number in a finite set whose existence is not in doubt (though its value is no closer..)

Gordon
gfroyle

Posts: 214
Joined: 21 June 2005

### Re: Least Upper Bound

gfroyle wrote:You've got your bounds the wrong way round..
No I haven't -- I was merely picking up, in a lighthearted manner, on the original definition of pseudo-puzzles that insisted on them having just two completions. Obviously he didn't mean us to use the old definition for this new question ...
Red Ed

Posts: 633
Joined: 06 June 2005

No I haven't -- I was merely picking up, in a lighthearted manner,

Indeed...

My apologies ..

I will go and write out 100 times "I must think before I type, I must think before I type"....

Gordon
gfroyle

Posts: 214
Joined: 21 June 2005

Okay, I think you both know what I mean....

I can't think of something nontrivial to say. Picking some examples from Gordon's list of 17s, and removing clues, there is one 16 so obtained with >900,000 completions. I find it a bit frightening.....I didn't think it would get even that large, and probably one can go much higher.

I suppose one can write it down in terms of unavoidable sets. But we don't have any nontrivial bounds on how many unavoidables a grid has.
Moschopulus

Posts: 256
Joined: 16 July 2005