minimum number of solutions

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

minimum number of solutions

Postby dukuso » Fri Sep 16, 2005 9:54 am

with 17 or more clues we can have puzzles with just one solution.
2 solutions for 16 clues.
1089 for 15 clues.
...


What's the minimum number of solutions for a puzzle with 9 clues ?
Can we make it, so that all ones and twos are forced ?

Or what's the maximum number of forced digits that can be filled in ?
dukuso
 
Posts: 479
Joined: 25 June 2005

Re: minimum number of solutions

Postby gfroyle » Fri Sep 16, 2005 11:46 am

dukuso wrote:with 17 or more clues we can have puzzles with just one solution.
2 solutions for 16 clues.
1089 for 15 clues.



Try this 15...

Code: Select all
. . .  3 . 1  . . . 
2 . 4  . . .  . . . 
. . .  . . .  . . . 

8 . .  5 2 .  . . . 
. . .  . . .  9 . 1 
. . .  . . .  3 . . 

. . .  . 4 .  . 5 . 
9 1 .  . . .  . . . 
. 3 .  . . .  . . . 


It's the best one I have so far...

Gordon
gfroyle
 
Posts: 214
Joined: 21 June 2005

Re: minimum number of solutions

Postby angusj » Fri Sep 16, 2005 2:20 pm

gfroyle wrote:Try this 15...
It's the best one I have so far.

Closer, but still no cigar (ie 596 solutions):) .
angusj
 
Posts: 306
Joined: 12 June 2005

Postby Pi » Fri Sep 16, 2005 5:05 pm

I am entregued about how you calculate that, i have onsidered setting up a similar solver and am very interested
Pi
 
Posts: 389
Joined: 27 May 2005

Postby gfroyle » Sat Sep 17, 2005 1:39 am

Pi wrote:I am entregued about how you calculate that, i have onsidered setting up a similar solver and am very interested


Basically, a backtrack program is needed to count all the solutions. We want a function numCompletions(G) which will return the number of completions of the grid G.

Then you would code it something like this - I hope its clear but I have tried to write it in a language neutral way, rather than assume that you are a C programmer, Java programmer or whatever...

Code: Select all
numCompletions(G)

  if G is a complete grid, then return 1

  otherwise

 choose an empty position, and find all legal entries for that position, call them x1, x2, .. ,xN
 
 if there are no legal entries, then return 0

 otherwise

 add up the values of numCompletions(G+x1), numCompletions(G+x2), numCompletions(G+xN) and return this value


This is obviously recursive, in that numCompletions calls itself... the idea is just that you try every possible entry in a position, and then see how many ways there are of completing the grid from there.

In practice, you need to be a bit more efficient, but that is the basic idea behind a backtrack program..

Some people have solvers that attempt to emulate human logic (by working out naked singles etc etc) but for counting problems, a backtrack is ultimately needed..

Gordon
gfroyle
 
Posts: 214
Joined: 21 June 2005

Re: minimum number of solutions

Postby coloin » Tue Sep 20, 2005 11:24 pm

dukuso wrote:What's the minimum number of solutions for a puzzle with 9 clues ?
Can we make it, so that all ones and twos are forced ?

Or what's the maximum number of forced digits that can be filled in ?


The best I got was

1xx xxx xxx
xxx xxx 1x2
xxx xx2 xxx

xxx 1xx xxx
xx2 xxx xxx
xxx xxx x2x

xxx xxx xx1
xxx xxx xxx
x1x xxx xxx 9 clues

-----------------gives

12x xxx xxx
xxx xxx 1x2
xxx x12 xxx

xxx 12x xxx
xx2 xxx x1x
xx1 xxx x2x

xxx xxx xx1
xxx xx1 xxx
x1x xxx xxx 9 clues plus 6 forced

No of solutions = ?

Can anyone get all 9 2s as well

Regards
coloin
 
Posts: 2365
Joined: 05 May 2005
Location: Devon


Return to General