## Prime number of solutions for multiple solutions sudokus

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

### Prime number of solutions for multiple solutions sudokus

This is the question i would like to ask:

What is the maximum prime number of solutions a sudoku with multiple solutions might have?
I have found some with 3 and 5 solutions, but none with 7
Is there any possibility to find one with 11 solutions????

Posts: 23
Joined: 22 May 2006

Not easy to say.

I found the following by just removing a single clue from minimal sudokus:

Code: Select all
`#3206570041070200000090000050000000039500003000000080000019000805000001000000620300#5000000000902004080050900060000070000000008007000000053700000608040509000800300400#7206570041070200000090000050000000039500043000000080000019000005000001000000620300#11200570041070200000090000050000000039500043000000080000019000805000001000000620300#13206570001070200000090000050000000039500043000000080000019000805000001000000620300#19206570040070200000090000050000000039500043000000080000019000805000001000000620300#29000000000902004080050900060000070000000008007007000053700000608040509000800300000#31000000038042080000000500070205000000000040900008003010001000000000020007050006043#97000409008000000000600070025324000000097060010000000030500010200000000400062800000#109060000038042080000000500070205000000000040900008003000001000000000020007050006043#149000000000902004080000900060000070000000008007007000053700000608040509000800300400#347000000000902004080050900060000070000000008007007000053000000608040509000800300400#609000000000902004080050900060000070000000008007007000003700000608040509000800300400`

It is just as easy to find sudokus with non-prime number-of-solutions.

Ruud.
Ruud

Posts: 664
Joined: 28 October 2005

Ruud,

I think you meant 709 solutions for your last puzzle.
re'born

Posts: 551
Joined: 31 May 2007

### Re: Prime number of solutions for multiple solutions sudokus

sopadeajo wrote:What is the maximum prime number of solutions a sudoku with multiple solutions might have?
I have found some with 3 and 5 solutions, but none with 7
It's probably way over 125000: see here.
Red Ed

Posts: 633
Joined: 06 June 2005

Thanks for the answers.

No, the new question is: Can we find at least a Sudoku with prime number of solutions for the first 100 odd primes, that is from 3 to 547 solutions, all of them prime.
Any systematic method to do this?
Or just trying it?

Posts: 23
Joined: 22 May 2006

If you want to do this manually, I'd say: just try it. That's how I found the samples.

If you have a program that can count solutions, even better. Take a collection of minimal puzzles (e.g. Gordons 17 clue collection) and for each entry in the collection, create 17 puzzles by removing each of the clues.
Have a backtracking solver count the solutions, and compare it to your list of primes. You may even collect all the data, not only the primes, and make nice charts of solution count distributions.

But, to satisfy my curiosity, what is the scientific value of this data?

Ruud.
Ruud

Posts: 664
Joined: 28 October 2005

"You may even collect all the data, not only the primes, and make nice charts of solution count distributions.

But, to satisfy my curiosity, what is the scientific value of this data? "

I am not trying to collect data about sudokus with different prime solutions, and do not want to go below 17 clues.

What i am wondering is if there should be a method (17 clues or more), to find (without trying) puzzles with as many solutions as each of the first 100 primes.
That is : are we certain we can find a Sudoku with 101 (prime) solutions, and then 103 solutions,107,109,113,....? (17 clues or more)

And if so, do they have a pattern?

It is an interesting question, because this involves chains of cells with different possible values, the topology of them should be perhaps interesting.

I have not yet had time to study the topology of the chain of your 11 solutions one (manually)

And 11=5+3+3
or 11=5+2*3
or 11=4+4+3
or 11=2*2*2+3

.......????

In fact, it seems that there is a large variety of different chains of cells leading to 3,5, 7, 11, 13,... solutions.

This is what i am interested in, and maybe in finding some kind of patterns, in the topological distribution of prime number solutions in Sudokus with more than 1 solution.

But i am not an expert.

Posts: 23
Joined: 22 May 2006

sopadeajo wrote:No, the new question is: Can we find at least a Sudoku with prime number of solutions for the first 100 odd primes, that is from 3 to 547 solutions, all of them prime.
Yes, I told you above that this is possible.

Any systematic method to do this?
Or just trying it?
The latter.

This is what i am interested in, and maybe in finding some kind of patterns, in the topological distribution of prime number solutions in Sudokus with more than 1 solution.
That sounds far too hard to be worth even starting on.
Red Ed

Posts: 633
Joined: 06 June 2005

here is the minimal pattern for a 3 solutions sudoku, with 3 variables (numbers) a,b,c, using only 7 cells inside a 3*9 or 9*3 rectangle :

a,b-------a,b
------b----c
a,b--c----a,b

a,b means a or b. Each column a,b,c or b,c belongs to a different 3*3 square.

The minimal number of cells for a 3 solutions is 7.

What is the minimal number of cells for 5,7,11 solutions?

Can we extend a 3 solutions to a 3+2=5 solutions?

I have only found 5 solutions which are 2+2+1=5.

Posts: 23
Joined: 22 May 2006

Sorry , not had time to correct my previous message.

The minimum number of cells, to get a 3 solution-sudoku is 7, with 3 variables a, b,c, like this:

-a,b--------a,b-
------b,c---b,c-
-a,b--b,c---a,b,c-

a,b and c are in the same 3*9 or 9*3 rectangle.

Each column (row) a,b b,c a,b,c belongs to a different 3*3 box.

these are the solutions:
-a-----------b-
-------b-----c-
-b-----c-----a-

-b-----------a-
-------b-----c-
-a-----c-----b-

-b-----------a-
-------c-----b-
-a-----b-----c-

I could not find less than 10 cells to get a 5 solution-sudoku, with 3 variables a,b,c.

-a,b---|---------|--a,b-
-a,d---|a,d-b,c-|--b,c-
-a,b,d-|a,d-b,c-|--a,b,c-

- means 0,1 or 2 blank cells

a,b,d a,d b,c a,b,c are in a same column

| means a different box

a,b and c are in the same 3*9 or 9*3 rectangle.

Minimum number of cells tor a 7 solution-susoku?

Posts: 23
Joined: 22 May 2006

sopadeajo wrote:I could not find less than 10 cells to get a 5 solution-sudoku, with 3 variables a,b,c.

-a,b---|---------|--a,b-
-a,d---|a,d-b,c-|--b,c-
-a,b,d-|a,d-b,c-|--a,b,c-

- means 0,1 or 2 blank cells

a,b,d a,d b,c a,b,c are in a same column

| means a different box

a,b and c are in the same 3*9 or 9*3 rectangle.
That would be a clearer if you used the 'code' formatting button to put things in proportional font. I think this is a better picture:
Code: Select all
`--- ab  --- | --- --- --- | --- ab  ------ ad  --- | ad  --- bc  | --- bc  ------ abd --- | ad  --- bc  | --- abc ---`
Unfortunately, the particular arrangement I've shown here (which I hope mirrors your original) doesn't seem natural to me because there's no 'b' option in r2c2, despite there being 'b' options elsewhere in row 2, in column 2 and in box 1: so that's not a pattern you can get by pencilmarking any set of clues.

A more natural question would be: what is the most number of clues you can place in a grid to be left with N solutions?

Equivalently: what's the fewest number of cells you can fill in such that there are N permutations of those cells that have the same row, column and box memberships? I prefer this way of stating the problem because you only need to show a few cells --- not a whole grid --- when exhibiting answers. And you only need to show one of the N permutations.

Finally, for keen people: consider the graph where vertices = valid permutations on those N cells and edges are present whenever two permutations differ by a minimal unavoidable set. What do these graphs look like for various N ? For example, the N=6 permutations of this ...
Code: Select all
`.a.|...|.b..d.|a.b|.c..b.|d.c|.a.`
... have the following graph:
Code: Select all
`*----*----*     |    |     |    |     *----*----*`
Red Ed

Posts: 633
Joined: 06 June 2005

Code: Select all
`-ab--|---|-ab--abd--|bc-ad|-abc--abd--|bc-ad|-abc-`

You are right, Red Ed.
This is in fact a 6 solution-sudoku with 4 variables (a,b,c,d), and only 10 "undeterminated" cells.

Here is an example to solve, choosen such that (a,b,c,d)=(1,2,3,4)
Code: Select all
`000000060090710040000003001040000200010052000003640080030009407000000500007080009`

If you add a 2 to c1r7--->4 solutions
Remove it, and add a 2 to c4r8-->3 solutions
Remove it, and add a 2 to c8r8--->2 solutions
Remove it , and add a 2 to c1r9--->1 solution

So , adding a clue in the apropriate cell, we get 4,3,2,1 solutions.
But i cannot see the way to get a 5 solution-sudoku.

Do we need more than 10 "undeterminated" cells for a 5-solution sudoku?

Posts: 23
Joined: 22 May 2006

sopadeajo wrote:Do we need more than 10 "undeterminated" cells for a 5-solution sudoku?
No, 10 cells appears to be the minimum, e.g. with the unspecified cells solved by any of the 5 permutations of this:
Code: Select all
`...|...|......|.37|2.....|.2.|7..---+---+---..3|.6.|.....6|.73|......|...|...`
whose graph is:
Code: Select all
`*----*----*     |    |     |    |     *----*`
Red Ed

Posts: 633
Joined: 06 June 2005

It seems that more editors know something about combinatorics in this thread. Hopefully you can answer this question for me:

I have got this solution grid:

Code: Select all
` *-----------*  |798|635|421|  |126|974|583|  |453|218|679|  |---+---+---|  |972|586|314|  |564|123|897|  |381|497|256|  |---+---+---|  |617|352|948|  |835|749|162|  |249|861|735|  *-----------* `

Then I remove all 4, 7 and 9 from the grid - like this:

..8635.21126...583.532186....258631.56.1238..381...25661.352..8835...1622..861.35

When I enter this sudoku in the solver, "Simple Sudoku", then I get 360 solutions. However, when I investigate this problem myself, then I get:

3*2*2*3*2*2=144 solutions.

I don't believe that a factor above 3 can be pressent in this case. Am I right or wrong?

/Viggo
Viggo

Posts: 60
Joined: 21 April 2006

Viggo wrote:I don't believe that a factor above 3 can be pressent in this case. Am I right or wrong?
Sorry, you're wrong in this case. My solver also says there are 360 solutions.
Red Ed

Posts: 633
Joined: 06 June 2005

Next