minimum number of solutions

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

minimum number of solutions

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

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

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

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

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

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