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?

Postby r.e.s. » Wed Apr 12, 2006 9:17 pm

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?

Postby Red Ed » Wed Apr 12, 2006 9:34 pm

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.

ImageEd.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Re: Minimum number of clues for exactly N solutions?

Postby r.e.s. » Wed Apr 12, 2006 10:18 pm

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

Postby Ruud » Wed Apr 12, 2006 10:43 pm

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

Postby coloin » Thu Apr 13, 2006 1:02 am

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: 1772
Joined: 05 May 2005

Postby r.e.s. » Thu Apr 13, 2006 1:12 am

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?

Postby ronk » Thu Apr 13, 2006 1:59 am

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

Postby kjellfp » Thu Apr 13, 2006 12:03 pm

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

Postby Pi » Thu Apr 13, 2006 2:57 pm

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

Postby kjellfp » Thu Apr 13, 2006 5:07 pm

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

Postby JPF » Thu Apr 13, 2006 9:38 pm

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

Postby kjellfp » Thu Apr 13, 2006 9:49 pm

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

Postby Moschopulus » Thu Apr 13, 2006 9:52 pm

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

Postby JPF » Thu Apr 13, 2006 10:42 pm

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

Postby JPF » Thu Apr 13, 2006 11:17 pm

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

Return to General

cron