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?

32 posts
• Page **2** of **3** • 1, **2**, 3

kjellfp wrote: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
**Posts:**256**Joined:**16 July 2005

JPF wrote: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.

Last edited by Moschopulus on Sat Apr 15, 2006 12:54 pm, edited 2 times in total.

- Moschopulus
**Posts:**256**Joined:**16 July 2005

Since 3x3 is practically impossible, here's 2x2. Yes I know this is trivial, but it might help someone's intuition.Moschopulus wrote:All these functions M, F, H, are impossible to find, I think.

- 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

Ed.

- Red Ed
**Posts:**633**Joined:**06 June 2005

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?

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?

- Moschopulus
**Posts:**256**Joined:**16 July 2005

r.e.s. wrote: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.)

kjellfp wrote: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().)

- r.e.s.
**Posts:**337**Joined:**31 August 2005

JPF wrote: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|

*-----------*

- Ocean
**Posts:**442**Joined:**29 August 2005

Ocean wrote: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

- JPF
- 2017 Supporter
**Posts:**3755**Joined:**06 December 2005**Location:**Paris, France

JPF wrote: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.

- Ocean
**Posts:**442**Joined:**29 August 2005

Ocean wrote: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

- JPF
- 2017 Supporter
**Posts:**3755**Joined:**06 December 2005**Location:**Paris, France

It's more -- I would guess far more -- than 125000.kjellfp wrote:More interresting challenge: What is the smallest number N such that no grid has exactly N solutions?

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.

- Red Ed
**Posts:**633**Joined:**06 June 2005

kjellfp wrote: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

- JPF
- 2017 Supporter
**Posts:**3755**Joined:**06 December 2005**Location:**Paris, France

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.JPF wrote:Could somebody help me to understand how N2c (or N2d) is calculated ?

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.

- Red Ed
**Posts:**633**Joined:**06 June 2005

32 posts
• Page **2** of **3** • 1, **2**, 3