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

Postby sopadeajo » Tue May 23, 2006 1:06 am

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????
sopadeajo
 
Posts: 23
Joined: 22 May 2006

Postby Ruud » Tue May 23, 2006 1:55 am

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.
Ruud
 
Posts: 664
Joined: 28 October 2005

Postby re'born » Tue May 23, 2006 5:09 am

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

Postby Red Ed » Tue May 23, 2006 6:19 am

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

Postby sopadeajo » Tue May 23, 2006 11:58 pm

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?
sopadeajo
 
Posts: 23
Joined: 22 May 2006

Postby Ruud » Wed May 24, 2006 12:40 am

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

Postby sopadeajo » Wed May 24, 2006 2:23 am

"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.
sopadeajo
 
Posts: 23
Joined: 22 May 2006

Postby Red Ed » Wed May 24, 2006 6:34 am

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

Postby sopadeajo » Wed May 24, 2006 5:14 pm

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
 
Posts: 23
Joined: 22 May 2006

Postby sopadeajo » Sat Jun 03, 2006 3:59 pm

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?
sopadeajo
 
Posts: 23
Joined: 22 May 2006

Postby Red Ed » Sun Jun 04, 2006 8:36 am

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

Postby sopadeajo » Mon Jun 05, 2006 4:43 pm

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

Postby Red Ed » Tue Jun 06, 2006 3:50 pm

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

Postby Viggo » Tue Jun 06, 2006 5:48 pm

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

Postby Red Ed » Tue Jun 06, 2006 6:09 pm

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

Return to General