The New Sudoku Players' Forum

[r.e.s.]

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?

[Red Ed]

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.

[r.e.s.]

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

[Ruud]

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.

[coloin]

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

[r.e.s.]

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

[ronk]

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.

[kjellfp]

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.

[Pi]

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

[kjellfp]

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

[JPF]

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

[kjellfp]

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?

[Moschopulus]

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.

[JPF]

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 !

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]

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