The New Sudoku Players' Forum

[ronk]

Would symbolism like ...

S(C) ... meaning 'S' solutions as a function of 'C' clues, and

C(S) ... meaning 'C' clues as a function of 'S' solutions

... make too much sense?

[Moschopulus]

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

It might be quite large.

Here are puzzles with N solutions for N=1,2,3,4,5,6,7,8,9,10.

002009740409702001005014003000000002000291000600000000700340500500107308083900100
000010400800000060000900000041050000000000083900000000200806000060000100000300000
009010400800000060000000000041050000000009083000000000200806000060000100000300000
100600000000000050000000030000040720000020000300000000024000100000300600070500000
002700046810402005460300100000005420504801000670090508240080351705100800000540000
000060502801000000000000000050020000400000080000900300000804090020000000000100000
200000306001050000000000000000041050670000200030000000008000040000700000000600000
000057000100030000604000000200000060000400010070000000030000705000100000000000300
400350000610000000000700000083001000000000020000000040500000100200400000000000800
500000400000710003000020000000004620070000000010000000600002000000030010400000000

[Moschopulus]

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.

Yes, thank you.

Here'a another function

H(N) = maximum number of solutions over all puzzles with N clues.

H(81)=1
H(80)=1
H(79)=1
H(78)=1
H(77)=2
[Edited, rubbish deleted]
...
H(2)=123535254667056906240 (by kjellfp post above)
H(1)=741211528002341437440
H(0)=6670903752021072936960

Or while we're at it, find all possible numbers of solutions as we range over all puzzles with N clues.

All these functions M, F, H, are impossible to find, I think.

[Red Ed]

All these functions M, F, H, are impossible to find, I think.

Since 3x3 is practically impossible, here's 2x2. Yes I know this is trivial, but it might help someone's intuition.

Code: Select all

  Nr solns   Nr Clues
  --------   -------------------------------------------------
   1 soln:               4  5  6  7  8  9 10 11 12 13 14 15 16
   2 solns:              4  5  6  7  8  9 10 11 12
   3 solns:           3  4  5  6  7  8  9
   4 solns:              4  5  6  7  8
   5 solns:              4  5  6
   6 solns:           3  4  5  6
   7 solns:              4
   8 solns:              4
   9 solns:           3
  10 solns:              4
  12 solns:        2  3  4
  18 solns:        2  3  4
  24 solns:        2
  36 solns:        2
  72 solns:     1
 288 solns:  0

Just to clarify: this means that to have, say, 5 solutions you need 4, 5 or 6 clues; and with 9 clues you can have 1, 2 or 3 solutions.

Ed.

[Moschopulus]

Interesting to see the numbers for 2x2.

The smallest N for which there is no puzzle with exactly N solutions is N=11.

This occurs around the 3-4 clue area, and 4 is the minimum for a unique solution.

Generalizing on the basis of one example is ridiculous, but for 3x3, perhaps around the 16-17 clue area we might find the corresponding N?

[r.e.s.]

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

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

Agreed! (I think it would be very interesting to know more about the topography of the "gaps" in the domain of M().)

[JPF]

I deleted this post with incorrect statements. (see Ocean's comments below).
Revised post below too.
JPF

[Ocean]

Monotonicity

1)The function Max().
It' s clear that Max() is not a monotonic function for all n=0,...,p^4.
For p=3 : Max(75)=2 ; Max(76)=1 ; Max(77)=2.
but it's seem to be true for p =2 ...
In addition, maybe a coincidence,
For p =2 or p=3 :
Max(p^4-4)=2
Max(p^4-k)=1 ; k=0,1,2,3

JPF

Just to comment on a sligth misunderstanding.
The funcion Max(x) is a monotonic function, as is easy to prove.
The example below shows that Max(76)=2. (Unavoidable sets of size 5 exist - but they are not 'minimal').

Code: Select all

 77 clues. 2 solutions.
 *-----------*
 |627|004|815|
 |951|728|364|
 |348|516|972|
 |---+---+---|
 |564|873|129|
 |179|642|583|
 |832|159|647|
 |---+---+---|
 |286|007|451|
 |713|465|298|
 |495|281|736|
 *-----------*

Code: Select all

 76 clues. 2 solutions.
 *-----------*
 |627|000|815|
 |951|728|364|
 |348|516|972|
 |---+---+---|
 |564|873|129|
 |179|642|583|
 |832|159|647|
 |---+---+---|
 |286|007|451|
 |713|465|298|
 |495|281|736|
 *-----------*

[JPF]

Just to comment on a sligth misunderstanding.
The funcion Max(x) is a monotonic function, as is easy to prove.
The example below shows that Max(76)=2. (Unavoidable sets of size 5 exist - but they are not 'minimal').

I take your point.
I'm not sure I understand what I did not understand...
Is it easy to prove that Max(x) is decreasing ?

JPF

[Ocean]

Is it easy to prove that Max(x) is decreasing ?

JPF

I think that is easy, if this principle is true: It is never possible to increase the number of solutions to a given puzzle by adding clues, and it is never possible to decrease the number of solutions to a given puzzle by removing clues.

Then:
For any puzzle S with n clues and N solutions: Removing one clue from S gives a puzzle S1 with n-1 clues, and k solutions, where k>=N. So, if Max(n)=N, then there exists a puzzle with n-1 clues and k>=N solutions. Therefore Max(n)<=Max(n-1) (for 0<n<=p^4).


PS.
The reason for my first comment was that the 'false' statement about H(76) lead to the conclusion that 'Max()' was not monotonic - which could not be true. (Hope you excuse me if I'm totally wrong here -). The rest of your post was just perfect! (as far as I can judge) - a valuable contribution.

[JPF]

PS.
The reason for my first comment was that the 'false' statement about H(76) lead to the conclusion that 'Max()' was not monotonic - which could not be true. (Hope you excuse me if I'm totally wrong here -). The rest of your post was just perfect! (as far as I can judge) - a valuable contribution.

Thanxs.
Anyway, I answered too quickly.
I should have checked this strange value for " H(76)"

Here is my revised post :

May I suggest that we use n for a number of clues et N when we speak about number of solutions.

Let Sp be the number of "Sudokus" of a "pxp" grid (p^4 cells)
For a (normal) sudoku 3x3, S3= 6670903752021072936960
For a 2x2 su(b)doku, S2 = 288.

For n= 0,...,p^4 :

Let Min(n) be the minimum number of solutions over all puzzles with n clues and having at least 1 solution. (F() until now)

Let Max(n) be the maximum number of solutions over all puzzles with n clues (H() before)

We have the almost trivial relations :

1<=Min(n)<=Max(n)<=Sp
Min(0) = Max(0)=Sp
Min(1)= Max(1)= Sp/(p^2)
...
Min(p^4)=Max(p^4)=1

In addition :
if for p=3, Max(2)= 123535254667056906240 (??), we can say that :

Max(2)=Sp/kp where kp is an integer (k2=8 and k3=54)

Last point : for p=2, one can note that Min() and Max() are divisors of S2 (=288)
I was wondering if for p=3, Min(2)= 77209534166910566400 (??)
if it is the case, it would be not true for p=3.



Monotonicity

About the Monotonicity of Max() and Min(), I'm almost clear now :
Ocean, I'm expanding your proof a bit, even if this topic has probably been already developed in this forum.

Let P be a puzzle (with at least 1 solution) and let n(P) be the number of clues, N(P) be the number of solutions of P.

a) If P and Q are 2 puzzles such that Q<P (all the clues of Q are included in the set of clues of P),

then N(P)<=N(Q)

The reason is that every solution S of the puzzle P contains the n(Q) clues of Q and therefore is a solution of Q.
The set of solutions of P is included in the set of solutions of Q.
As a consequence : N(P)<= N(Q)

b) Max(n)<=Max(n-1) ; n=1,...,p^4
Let's assume that P is one n clues puzzle with the maximum of solutions N(P)=Max(n)
If we remove one clue (n>=1) to P, we get the puzzle Q with n-1 clues and Q<P
We know that Q<P => N(P)<=N(Q).
But P is a n clues maximum puzzle and Q is a (n-1) clues puzzle.
Therefore :
Max(n)=N(P)<=N(Q)<=Max(n-1)

c) Min(n)<=Min(n-1)
Same proof, but adding one clue to a minimum (n-1) puzzle.

Both Min() and Max() are decreasing.



In addition, maybe a coincidence,
For p =2 or p=3 :
Max(p^4-4)=2
Max(p^4-k)=1 ; k=0,1,2,3

As a consequence that both Min() and Max() are decreasing and that Min(p^4)=Max(p^4)=1, there exist 2 numbers km and kM (1<km<=kM<p^4) such that :

n>=km => Min(n)=1
n>=kM => Max(n)=1

for p=2 or 3 : kM=p^4-3

When p=2 ; km = 4 and kM=13
When p=3 ; km <=17 and kM=78



JPF

[Red Ed]

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

It's more -- I would guess far more -- than 125000.

By random searching I've found N-solution grids for N=1,2,...,125332, with no sign that the first gap (at 125333 - at the moment) is at all significant. Of course random searching would never give a conclusive smallest-N, but my point is that whatever that smallest-N is, it's a lot bigger than I, at least, expected.

I don't think we can solve the problem when the clues are chosen freely.

Alternatively, you might fix some solution grid G and then consider N(G) = smallest number N such that no subgrid of G has exactly N solutions. This simpler problem also appears to be hard, with N(G)>10000 for each of the two randomly chosen G that I've just been playing with. Even the highly regular "canonical grid", which you might expect to be somewhat lacking in choices of interesting clue sets, has N(G)>10000.

Ed.

[JPF]

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.

N0=6670903752021072936960
N1=N0/9=741211528002341437440
N2a=92651441000292679680= N0/(9!/7!)=N0/72
N2b=82356836444704604160=N0/(9^2)=N0/81
N2c=123535254667056906240
N2d=77209534166910566400

Could somebody help me to understand how N2c (or N2d) is calculated ?

I understand that : 9(N2c+8N2d)=N0

Thanks in advance.

JPF

[Red Ed]

Could somebody help me to understand how N2c (or N2d) is calculated ?

For N2c (r1c1 = 1, r2c4 = 1): pick a solution grid at random. It has r1c1=1 with probability 1/9. Conditional on that, the '1' in r2 is in c4 with probability 1/6 (it can be in any of c4-c9 with equal chance). So N2c = N0*1/9*1/6 = 123535254667056906240.

For N2d (r1c1 = 1, r2c4 = 2): conditional on r1c1=1 (prob 1/9 as above), there's a 5/6 probability that r2c4!=1 (as above), 1/8 of which times we have r2c4=2 (it could take any value other than '1'). So N2d = N0*1/9*5/6*1/8 = 77209534166910566400.

While I'm here, an update on the minimum unattainable number of solutions. Having given up on the 3x3 case, I looked at 3x2 and 4x2. The answer for 3x2 appears to be just over 1000: I'm stuck at 1019 at the moment (any takers?). The answer for 4x2 is more than 138288: I will probably have to give up on this case.

Ed.

[JPF]

It's clear.
Thanks a lot.

JPF