## Minimum number of clues for exactly N solutions?

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

### Minimum number of clues for exactly N solutions?

Let M(N) be the minimum number of clues that will ensure existence of exactly N solutions.

What are the best known least upper bounds for M(N) (N=1,2,3,...)?
(The best known l.u.b. for M(1) is apparently 17.)

What can be said about the behavior of the function M()?
Is M(1) < M(2)? Is M() monotonic?
r.e.s.

Posts: 337
Joined: 31 August 2005

### Re: Minimum number of clues for exactly N solutions?

r.e.s. wrote:Is M(1) < M(2)?
As far as we know at the moment, the opposite is true: M(1)=17, but M(2)=16. Ed.
Red Ed

Posts: 633
Joined: 06 June 2005

### Re: Minimum number of clues for exactly N solutions?

Red Ed wrote:
r.e.s. wrote:Is M(1) < M(2)?
As far as we know at the moment, the opposite is true: M(1)=17, but M(2)=16.

Thanks for the link. Maybe the graph of M() is a "descending 17-step staircase", with increasingly-wide steps.
On the other hand, might there be values of N (less than the total number of sudoku solutions) for which
no sudoku puzzle has exactly N solutions? (If there are such values of N, I wonder what's the smallest one.)
r.e.s.

Posts: 337
Joined: 31 August 2005

When M(1) = 17, and M(2) = 16,

Then we could consider:

When M(3) can always be made M(1) by adding a single clue, then M(3) = 16.

For this we have to look at the possible configurations of the 'incomplete parts' that allow 3 solutions.

Sounds like an assignment for our math people...

Ruud.
Ruud

Posts: 664
Joined: 28 October 2005

qfroyle wrote:Here are the pseudo-Sudokus with low numbers of completions... the file name indicates how many completions (ie xall16-002 lists all the ones I know with 16 clues and 2 completions).
Code: Select all
` xall16-002 5.2...4.....71...3..............46...7.2......1.......6....2.......3..1.4........ xall16-004 1..6............5........3.....4.72.....2....3.........24...1.....3..6...7.5..... 5.42.........4..3.1.........6..73.........5.1..........3.....7....5..4..6........ 5.42.........4..3.1.........6..73.........5.1..........3.....7....5..4..8........ xall16-006 ....6.5.28.1................5..2....4......8....9..3.....8.4.9..2..........1..... ...71....4.6......2.............45..6..2...........31..3..5...........42.1....... .7....3.2...5.6............5..4.........7.2....1......6.....4...2..3.......1...5. 1.42.........4..3.5.........6..73.........5.1..........3.....7....1..4..8........ 6...42....3....7............8.73...........42...1.....2.4..5.........3..5........ xall16-007 2.....3.6..1.5.................41.5.67....2...3.........8....4....7........6..... xall16-008 ....57...1...3....6.4......2......6....4...1..7........3....7.5...1...........3.. ....9.2.56.8................5..2....4......8....9..3.....8.4.6..2..........1..... ....9.5.26.8................5..2....4......8....9..3.....8.4.6..2..........1..... ....9.5.28.1................5..2....4......8....9..3.....8.4.9..2..........1..... .3.5.....7......2........1..43...5......1..........3..2.1..7......3..6.4......... 6.1...........24...........42...3.......5..17.........5..16.....4....3.....7..... 6.2...5.....13...4..............57...3.2......1.......7....2.......4..3.5........ 7.38........6..4..2...............73.4.1..............61....9......2.1......7.... xall16-009 4..35....61..........7......83..1..........2........4.5.....1..2..4...........8.. `

There is a 15 clue with 596 grid solutions
Code: Select all
`+---+---+---+|...|3.1|...||2.4|...|...||...|...|...|+---+---+---+|8..|52.|...||...|...|9.1||...|...|3..|+---+---+---+|...|.4.|.5.||91.|...|...||.3.|...|...|+---+---+---+`

Therefore M(596)=15

C
coloin

Posts: 1804
Joined: 05 May 2005

coloin wrote:There is a 15 clue with 596 grid solutions [...]
Therefore M(596)=15

I think that should be ... "therefore M(596) <= 15", right?
(M() is the actual minimum, as distinct from its best known estimate.)
r.e.s.

Posts: 337
Joined: 31 August 2005

### Re: Minimum number of clues for exactly N solutions?

r.e.s. wrote:Let M(N) be the minimum number of clues that will ensure existence of exactly N solutions.

If and when it becomes time to graph the function, I think the inverse would make more sense, i.e., ...

Let M(N) be the minimum number of solutions that can be obtained with N clues.

Then you end up with a quasi-hyperbolic curve with asymptotes of N=0 and M=1 ... I think.
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Something we at least know and not only believe...

M(6670903752021072936960)=0
M(741211528002341437440)=1
M(92651441000292679680)=2 (r1c1=1 r1c2=2)
M(82356836444704604160)=2 (r1c1=r4c4=1)
M(123535254667056906240)=2 (r1c1=r2c4=1)
M(77209534166910566400)=2 (r1c1=1 r2c4=2)

and that's all M(*)=2. I leave M(*)=3 and upwards for others.
kjellfp

Posts: 140
Joined: 04 October 2005

kjellfp wrote:Something we at least know and not only believe...

M(6670903752021072936960)=0
M(741211528002341437440)=1

If i am not mistaken the figure 6670903752021072936960 is reduced from the absolute maximum and considers changing the candidates around to be the same puzzle.

Therefore i belive that any grid with 1 clue has 6670903752021072936960 possible conbinations
Pi

Posts: 389
Joined: 27 May 2005

6670903752021072936960 is the total number of Sudoku grids. Introducing a clue reduces the solution space by a factor of 9.
kjellfp

Posts: 140
Joined: 04 October 2005

The domain of the function M (N) is not easy to define.

In any case, N must verify the condition 0<=N<=Ng
with Ng =6670903752021072936960
But reciprocally it is not evident that for any number N such that 0<=N<=Ng , the function M (N) is defined.

We know, that the function is defined for some numbers ; for example : 0, 1, 2, 596, Ng

M (0) =2 (R1C1=R1C2=1)
M (1) exists; 0<M (1) <=17
M (2) exists; 0<M (2) <=16
M (596) exists; 0<M (596) <=15
M (Ng) =0

But what about M (1000)? , M(10000)?
In other words, is it possible for each number N such that 0<=N<=Ng, to find a (pseudo)puzzle with N solutions ?

I think that even this (first) question is very hard to answer.

JPF
JPF
2017 Supporter

Posts: 3755
Joined: 06 December 2005
Location: Paris, France

JPF wrote:In other words, is it possible for each number N such that 0<=N<=Ng, to find a (pseudo)puzzle with N solutions ?

Indeed not. The 0-clue grid has N0=6670903752021072936960 solutions, the 1-clue grid has N1=741211528002341437440. Any grid with at least two clues has less than N1 solutions, so the numbers between N0 and N1 are never the exact number of solutions to a puzzle.

More interresting challenge: What is the smallest number N such that no grid has exactly N solutions?
kjellfp

Posts: 140
Joined: 04 October 2005

JPF wrote:The domain of the function M (N) is not easy to define.

In any case, N must verify the condition 0<=N<=Ng
with Ng =6670903752021072936960
But reciprocally it is not evident that for any number N such that 0<=N<=Ng , the function M (N) is defined.

That's why, as ronk suggested, the inverse function might be better.

F(N)=minimum number of solutions over all puzzles with N clues.

F(17)=1.
F(16)=2 we think.
F(15) <= 596.

Of course we can't figure out F(16) so I don't know how we can figure out the others.
Moschopulus

Posts: 256
Joined: 16 July 2005

kjellfp wrote:
JPF wrote:In other words, is it possible for each number N such that 0<=N<=Ng, to find a (pseudo)puzzle with N solutions ?

Indeed not. The 0-clue grid has N0=6670903752021072936960 solutions, the 1-clue grid has N1=741211528002341437440. Any grid with at least two clues has less than N1 solutions, so the numbers between N0 and N1 are never the exact number of solutions to a puzzle.

Good point !

kjellfp wrote:More interresting challenge: What is the smallest number N such that no grid has exactly N solutions?

It's going to be very dificult to answer, because we will have to check every numbers from 3 to N ...
At this stage, we cannot say for instance that N =596, without making puzzles with 3, 4, ...,595 solutions.
which is a necessary, (but not a sufficient) condition.

JPF
JPF
2017 Supporter

Posts: 3755
Joined: 06 December 2005
Location: Paris, France

Moschopulus wrote:That's why, as ronk suggested, the inverse function might be better.
F(N)=minimum number of solutions over all puzzles with N clues.

We should be a bit more precise on the definition of F.
If not :
F(N)=0 for N>0.

The puzzles must have at least 1 solution.

F(0)=Ng
F(1)=Ng/9
...

F(15)<=596
F(16)<=2
F(k)=1 ; k=17,...,81

JPF
JPF
2017 Supporter

Posts: 3755
Joined: 06 December 2005
Location: Paris, France

Next