The New Sudoku Players' Forum

[dukuso]

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 ?

[gfroyle]

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

[angusj]

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

Closer, but still no cigar (ie 596 solutions) .

[Pi]

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

[gfroyle]

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

[coloin]

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