The New Sudoku Players' Forum

[sopadeajo]

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

[Ruud]

Not easy to say.

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.

[re'born]

Ruud,

I think you meant 709 solutions for your last puzzle.

[Red Ed]

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.

[sopadeajo]

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?

[Ruud]

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.

[sopadeajo]

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

[Red Ed]

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.

[sopadeajo]

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.

[sopadeajo]

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?

[Red Ed]

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

*----*----*
     |    |
     |    |
     *----*----*

[sopadeajo]

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?

[Red Ed]

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

*----*----*
     |    |
     |    |
     *----*

[Viggo]

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

[Red Ed]

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.