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????

45 posts
• Page **1** of **3** • **1**, 2, 3

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????

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????

- sopadeajo
**Posts:**23**Joined:**22 May 2006

Not easy to say.

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

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

Ruud.

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

- Code: Select all
`#3`

206570041070200000090000050000000039500003000000080000019000805000001000000620300

#5

000000000902004080050900060000070000000008007000000053700000608040509000800300400

#7

206570041070200000090000050000000039500043000000080000019000005000001000000620300

#11

200570041070200000090000050000000039500043000000080000019000805000001000000620300

#13

206570001070200000090000050000000039500043000000080000019000805000001000000620300

#19

206570040070200000090000050000000039500043000000080000019000805000001000000620300

#29

000000000902004080050900060000070000000008007007000053700000608040509000800300000

#31

000000038042080000000500070205000000000040900008003010001000000000020007050006043

#97

000409008000000000600070025324000000097060010000000030500010200000000400062800000

#109

060000038042080000000500070205000000000040900008003000001000000000020007050006043

#149

000000000902004080000900060000070000000008007007000053700000608040509000800300400

#347

000000000902004080050900060000070000000008007007000053000000608040509000800300400

#609

000000000902004080050900060000070000000008007007000003700000608040509000800300400

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

Ruud.

- Ruud
**Posts:**664**Joined:**28 October 2005

It's probably way over 125000: see here.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

- Red Ed
**Posts:**633**Joined:**06 June 2005

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.

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.

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.

- sopadeajo
**Posts:**23**Joined:**22 May 2006

Yes, I told you above that this is possible.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.

The latter.Any systematic method to do this?

Or just trying it?

That sounds far too hard to be worth even starting on.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.

- 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.

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.

- sopadeajo
**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?

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?

- sopadeajo
**Posts:**23**Joined:**22 May 2006

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: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.

- Code: Select all
`--- ab --- | --- --- --- | --- ab ---`

--- ad --- | ad --- bc | --- bc ---

--- abd --- | ad --- bc | --- abc ---

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.

- 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?

- sopadeajo
**Posts:**23**Joined:**22 May 2006

No, 10 cells appears to be the minimum, e.g. with the unspecified cells solved by any of the 5 permutations of this:sopadeajo wrote:Do we need more than 10 "undeterminated" cells for a 5-solution sudoku?

- Code: Select all
`...|...|...`

...|.37|2..

...|.2.|7..

---+---+---

..3|.6.|...

..6|.73|...

...|...|...

- 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:

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

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

45 posts
• Page **1** of **3** • **1**, 2, 3