The New Sudoku Players' Forum

[ronk]

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.

My total stands at 288 ... and I don't understand the 360 yet either.

There are 12 permutations of digits 4, 7, and 9 in the center stack. If we figure out the 30 permutations in entwined stacks 1 and 3, we'll know where the factor 5 comes from.

[gsf]

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.

My total stands at 288 ... and I don't understand the 360 yet either.

There are 12 permutations of digits 4, 7, and 9 in the center stack. If we figure out the 30 permutations in entwined stacks 1 and 3, we'll know where the factor 5 comes from.

there are 360 lexicographically different solutions
but only 60 non-isomorphic solutions, each one representing 6 of the solutions

here is a representative for each of the 60 different solutions

478635921126794583953218647742586319569123874381947256617352498835479162294861735
478635921126479583953218647742586319569123874381947256617352498835794162294861735
478635921126749583953218647792586314564123879381497256617352498835974162249861735
478635921126974583953218647792586314564123879381497256617352498835749162249861735
478635921126794583953218647742586319569123874381947256614352798835479162297861435
478635921126479583953218647742586319569123874381947256614352798835794162297861435
478635921126794583953218674742586319569123847381947256617352498835479162294861735
478635921126479583953218674742586319569123847381947256617352498835794162294861735
478635921126794583953218674742586319569123847381947256614352798835479162297861435
478635921126479583953218674742586319569123847381947256614352798835794162297861435
478635921126497583953218647742586319569123874381974256617352498835749162294861735
478635921126497583953218674742586319569123847381974256617352498835749162294861735
478635921126947583953218647742586319569123874381794256617352498835479162294861735
478635921126947583953218674742586319569123847381794256617352498835479162294861735
478635921126749583953218647742586319569123874381974256617352498835497162294861735
478635921126749583953218674742586319569123847381974256617352498835497162294861735
478635921126479583953218647742586319569123874381794256617352498835947162294861735
478635921126479583953218674742586319569123847381794256617352498835947162294861735
478635921126974583953218647742586319569123874381497256617352498835749162294861735
478635921126974583953218674742586319569123847381497256617352498835749162294861735
478635921126749583953218647742586319569123874381497256617352498835974162294861735
478635921126749583953218674742586319569123847381497256617352498835974162294861735
478635921126974583953218647742586319569123874381749256617352498835497162294861735
478635921126974583953218674742586319569123847381749256617352498835497162294861735
478635921126794583953218647742586319569123874381479256617352498835947162294861735
478635921126794583953218674742586319569123847381479256617352498835947162294861735
478635921126497583953218647742586319569123874381749256617352498835974162294861735
478635921126497583953218674742586319569123847381749256617352498835974162294861735
478635921126947583953218647742586319569123874381479256617352498835794162294861735
478635921126947583953218674742586319569123847381479256617352498835794162294861735
478635921126497583953218647742586319569123874381974256614352798835749162297861435
478635921126497583953218674742586319569123847381974256614352798835749162297861435
478635921126947583953218647742586319569123874381794256614352798835479162297861435
478635921126947583953218674742586319569123847381794256614352798835479162297861435
478635921126749583953218647742586319569123874381974256614352798835497162297861435
478635921126749583953218674742586319569123847381974256614352798835497162297861435
478635921126479583953218647742586319569123874381794256614352798835947162297861435
478635921126479583953218674742586319569123847381794256614352798835947162297861435
478635921126974583953218647742586319569123874381497256614352798835749162297861435
478635921126974583953218674742586319569123847381497256614352798835749162297861435
478635921126749583953218647742586319569123874381497256614352798835974162297861435
478635921126749583953218674742586319569123847381497256614352798835974162297861435
478635921126974583953218647742586319569123874381749256614352798835497162297861435
478635921126974583953218674742586319569123847381749256614352798835497162297861435
478635921126794583953218647742586319569123874381479256614352798835947162297861435
478635921126794583953218674742586319569123847381479256614352798835947162297861435
478635921126497583953218647742586319569123874381749256614352798835974162297861435
478635921126497583953218674742586319569123847381749256614352798835974162297861435
478635921126947583953218647742586319569123874381479256614352798835794162297861435
478635921126947583953218674742586319569123847381479256614352798835794162297861435
478635921126479583953218647792586314564123879381794256617352498835947162249861735
478635921126749583953218647792586314564123879381974256617352498835497162249861735
478635921126497583953218647792586314564123879381749256617352498835974162249861735
478635921126947583953218647792586314564123879381794256617352498835479162249861735
478635921126794583953218647792586314564123879381479256617352498835947162249861735
478635921126479583953218647792586314564123879381947256617352498835794162249861735
478635921126974583953218647792586314564123879381749256617352498835497162249861735
478635921126794583953218647792586314564123879381947256617352498835479162249861735
478635921126947583953218647792586314564123879381479256617352498835794162249861735
478635921126497583953218647792586314564123879381974256617352498835749162249861735

[Red Ed]

there are 360 lexicographically different solutions
but only 60 non-isomorphic solutions, each one representing 6 of the solutions

... the factor of 6 = 3! coming from the arbitrary order in which 7,8,9 are placed in the first row (say). But you knew that already.

If we figure out the 30 permutations in entwined stacks 1 and 3, we'll know where the factor 5 comes from.

The factor of 5 might be arbitrary in some sense. I mean, if you don't just leave out 7,8,9 but instead leave out *everything*, then you end up with a number of solutions that has 27704267971 as a prime factor. Try explaining that!

[ronk]

there are 360 lexicographically different solutions
but only 60 non-isomorphic solutions, each one representing 6 of the solutions

here is a representative for each of the 60 different solutions

If you please, what are the "solution representatives" when stack 2 is complete?

Code: Select all

 |..8|635|.21|
 |126|974|583|
 |.53|218|6..|
 |---+---+---|
 |..2|586|31.|
 |56.|123|8..|
 |381|497|256|
 |---+---+---|
 |61.|352|..8|
 |835|749|162|
 |2..|861|.35|


The factor of 5 might be arbitrary in some sense.

Suspect that's true, but would just like to understand the source in just one puzzle.

[Viggo]

Thank you for your help!

I can see now, that I was wrong.

I see it in this way:

For r268c456 we have got an isolated part of solutions - some kind of a "deadly swordfish". They will give a factor of 3*2*2=12 on the number of solutions. I hope you agree. We can then remove this part of the puzzle.

That leaves 30 solutions in the rest.

Code: Select all

I choose 4 (one of three) in r1c7 and
  I choose 7 (one of two) in r1c1 then r1c2, r3c1, r4c1 are fixed.
    I choose 4 in r4c2 then all remaining cells are fixed.
    ELSE I choose 7 in r4c2 then r5c3, r9c2, r4c9 are fixed.
      When I choose 7 in r7c3 then all except r35c89 are fixed leawing two solutions.
      Else I choose 9 in r7c3 then all except r35c89 are fixed leawing two solutions.
  ELSE I choose 9 in r1c1 then r1c2, r3c1, r4c1 are fixed (as before)
    I choose 4 in r4c2 then all remaining cells are fixed.
    ELSE I choose 9 in r4c2 then r5c3, r9c2, r4c9 are fixed.
      When I choose 7 in r7c3 then all except r35c89 are fixed leawing two solutions.
      Else I choose 9 in r7c3 then all except r35c89 are fixed leawing two solutions.
ELSE I choose 7 ... (three times almost as before)

So it makes 3*2*(1+4)=30 solutions. And 12*30=360 in all.

/Viggo

[gsf]

If you please, what are the "solution representatives" when stack 2 is complete?

Code: Select all

 |..8|635|.21|
 |126|974|583|
 |.53|218|6..|
 |---+---+---|
 |..2|586|31.|
 |56.|123|8..|
 |381|497|256|
 |---+---+---|
 |61.|352|..8|
 |835|749|162|
 |2..|861|.35|


Code: Select all

# print # solutions with possible equivalents
sudoku -a -f- -F%n m02.dat
# print representative from each equivalence class
sudoku -a -f%C%,%v m02.dat | sort | uniq -w81 | sed 's/.* //' | sort


there are 30 solutions and 30 classes

Code: Select all

478635921126974583953218647742586319569123874381497256614352798835749162297861435
478635921126974583953218647742586319569123874381497256617352498835749162294861735
478635921126974583953218647792586314564123879381497256617352498835749162249861735
478635921126974583953218674742586319569123847381497256614352798835749162297861435
478635921126974583953218674742586319569123847381497256617352498835749162294861735
498635721126974583753218649942586317567123894381497256614352978835749162279861435
498635721126974583753218649942586317567123894381497256619352478835749162274861935
498635721126974583753218649972586314564123897381497256619352478835749162247861935
498635721126974583753218694942586317567123849381497256614352978835749162279861435
498635721126974583753218694942586317567123849381497256619352478835749162274861935
748635921126974583953218647472586319569123874381497256614352798835749162297861435
748635921126974583953218647472586319569123874381497256617352498835749162294861735
748635921126974583953218674472586319569123847381497256614352798835749162297861435
748635921126974583953218674472586319569123847381497256617352498835749162294861735
748635921126974583953218674492586317567123849381497256614352798835749162279861435
798635421126974583453218679942586317567123894381497256619352748835749162274861935
798635421126974583453218679972586314564123897381497256617352948835749162249861735
798635421126974583453218679972586314564123897381497256619352748835749162247861935
798635421126974583453218697972586314564123879381497256617352948835749162249861735
798635421126974583453218697972586314564123879381497256619352748835749162247861935
948635721126974583753218649492586317567123894381497256614352978835749162279861435
948635721126974583753218649492586317567123894381497256619352478835749162274861935
948635721126974583753218694472586319569123847381497256614352978835749162297861435
948635721126974583753218694492586317567123849381497256614352978835749162279861435
948635721126974583753218694492586317567123849381497256619352478835749162274861935
978635421126974583453218679792586314564123897381497256617352948835749162249861735
978635421126974583453218679792586314564123897381497256619352748835749162247861935
978635421126974583453218697742586319569123874381497256617352948835749162294861735
978635421126974583453218697792586314564123879381497256617352948835749162249861735
978635421126974583453218697792586314564123879381497256619352748835749162247861935


[sopadeajo]

That leaves 30 solutions in the rest.

Here is your sudoku transformed with the 30 solutions (30 is a primorial=2*3*5, and the lowest composite product of 3 distint primes)

Code: Select all

008000001106970500003008600002506000000020800000497056600300008030040102000000000


Let r1c12=(4,7) or (4,9) or (7,9) in any order, and you´ll have 2*3 (5 solutions-sudokus).
With 3 variables (a,b,c)=(4,7,9) and 12 "undeterminated" cells.

Each of the 5 solutions are 5=1+4 solutions.




Now, try to prove or disprove with a counterexample, this conjecture:

Given a p(n) solutions-sudoku (p(n)=n-th prime), there is always an apropriate "undeterminated" cell, in which a new clue will produce a p(k) solutions-sudoku for all 1<=k<n.

If this is true, it would be a proof that there exists a prime number of solutions-sudoku, for every prime, up to the limit of the higher prime number of solutions-sudoku found (with at least 17 clues).

[Red Ed]

Given a p(n) solutions-sudoku (p(n)=n-th prime), there is always an apropriate "undeterminated" cell, in which a new clue will produce a p(k) solutions-sudoku for all 1<=k<n.

Clearly false. For any given multiple-solutions sudoku, there are no more than 9*81 = 729 ways of setting one extra clue. If your claim was true, it would imply that a p(731) = 5527 solution sudoku can't exist. But I told you earlier that we can construct sudokus with 1...125000+ solutions, e.g. this one with 5527:

Code: Select all

000026090050009040000000028500968000700014069000000000190003002000090030600000001

[sopadeajo]

Clearly false.

Not so clearly false, Red Ed.

If world clearly was green or blue, then clearly we would be living in a non red world.

I wrote:

Given a p(n) solutions-sudoku (p(n)=n-th prime), there is always an apropriate "undeterminated" cell, in which a new clue will produce a p(k) solutions-sudoku for all 1<=k<n.

I am talking, evidently, of a recursive operation.

Go adding clues *in some order*, such that one or several new clues added (in some order), will lead to all the preceding primes.

Repeat the operation in a different adding-order clues.

It is of course just a conjecture.

[sopadeajo]

Red Ed,

The first occurrance of a gap of 6 between primes is (for the upper prime):
29 (29-6=23).

Could you find a minimal-number of cells leading to a 29 solutions-sudoku?

How many clues must you add to get a 23 solutions???

Check in which order you must add clues (in different operations) to get all the 9 primes below 29.

[Red Ed]

Given a p(n) solutions-sudoku (p(n)=n-th prime), there is always an apropriate "undeterminated" cell, in which a new clue will produce a p(k) solutions-sudoku for all 1<=k<n.

I am talking, evidently, of a recursive operation.

Hmmm... the language barrier separated us there I think. To me, that was "evidently" non-recursive. But no matter.

The first occurrance of a gap of 6 between primes is (for the upper prime):
29 (29-6=23)

No it isn't: 23 = 17 + 6 is the first such gap. But that doesn't matter either, let's go with the flow. Here's a probably-minimum set with 29 permutations (we'll call it "29-permutable"):

Code: Select all

....8..2.528.6..3.3.6.2..8.852.................................265...............

Removing a single cell leads to 1-off subsets with the following number of permutations:

Code: Select all

 8@0,4 : 15
 2@0,7 : 15
 5@1,0 : 5
 2@1,1 : 6
 8@1,2 : 6
 6@1,4 : 11
 3@1,7 : 16
 3@2,0 : 16
 6@2,2 : 11
 2@2,4 : 6
 8@2,7 : 8
 8@3,0 : 14
 5@3,1 : 12
 2@3,2 : 6
 2@7,0 : 14
 6@7,1 : 18
 5@7,2 : 9

Notice there's no 1-off subset with more than 18 permutations. Therefore there are no strict subsets of any size that are 23-permutable. This disproves your conjecture.

A simpler counterexample is provided by this 11-permutable set, with each of its 1-off subsets being 2- or 5-permutable. Therefore it cannot have any 7-permutable subsets.

Code: Select all

...........................15...9.3.23..15.9.9...23.1............................

[sopadeajo]

sopadeajo wrote:
The first occurrance of a gap of 6 between primes is (for the upper prime):
29 (29-6=23)
No it isn't: 23 = 17 + 6 is the first such gap. But that doesn't matter either

Again the language, Red Ed.

What i meant was: between consecutive primes.....(19 ia a nice not sum of 2 squares prime).

I´ll have a look at this tomorrow.

[Red Ed]

Oops, yes, my mistake. Understood the question, just not paying attention.

I'm still confident of my counterexamples, though!

[sopadeajo]

Here is the set of distint number of permutations for the 1-off subset: S-1, of your 29-permutable set with 17 cells and 5 variables :

S-1={5,6,8,9,11,12,14,15,16,18}.

I am not certain if S-1 is complete. Aren´t there more elements missing from elements of the 29-permutable set in different positions???

Note that we get 50% of them that are multiple of 3.

So a 3 permutation structure appears too often.

For example: removing 6 in r8c2-->18 permutations, do not lead (by removing another cell ) to 17 or 13 permutations, because this 18 is mostly a 6*3 permutation.

Removing 6 in r8c3 (in a different 29-permutation), with 11 permutations ,is a 11=2+3+2*3. So you can obtain 5, by removing another number in the appropriate cell, but not 7=3+4=2+5 or 7=2+2+3.


I do believe that there is a different 29-permutable set, probably with more cells (or maybe not), which will lead to much more prime permutations.

In fact your 29-permutable set is not unique, neither your 11-permutable; and so your disproof is invalid.

Note too, that the minimal prime permutation of S-1, is 5=17% of 29.
So ,for the first 4 digits prime: 1009, we could probably reach a minimal 30% prime permutation with just 1 element off, and go on removing to find the lowest primes.


Nethertheless, i restate my conjecture to a nice question:

What is the maximal n , such that a p(n)-permutable set, will lead to p(k) permutable sets for all 1<=k<n, by removing 1 or more of the elements of the set, in successive operations ?(readd the element, if needed).
We´ll call them :n- Fully Prime Permutable Sets (n-FPPS)

Your 5-permutable (probably minimal) set, leaded to 3 and 2.
So, n>=3.
.
Could you try to build a 4-FPPS from a 3-FPPS, and then a 5,6,..,10?

I am not sure if a n-FPPS must be built from a n-1 one, or if this condition is not necessary.

[Red Ed]

In fact your 29-permutable set is not unique, neither your 11-permutable; and so your disproof is invalid.

What?!?! Go and re-read your own conjecture. "Given a p(n) solutions-sudoku ..." -- I gave you a 29-permutable set. It didn't have a 23-permutable subset. So your conjecture is false.

But ... I realise that my discussion of permutable sets, and subsets of them, is not quite the same thing as talking about partially-completed grids and the effect of adding extra clues. For example, consider a grid with 64 clues filled in that has 29 solutions. Each possible way of filling in the remaining 17 cells is a 29-permutable set (a.k.a. an unavoidable set). If we want to know if any single extra clue can be added to the grid to get 23 solutions then we can't just focus on one of those 29-permutables and start dropping cells, as I had been doing, but instead try enough of the 29-permutables that all the possible single-cell/value combinations are considered. If I do this with the 29-permutable that I exhibited earlier then I get more p-permutable possibilities than originally reported. But I still don't get anything above 18-permutable, so no way of adding any number of clues to get 23 solutions.

The same goes for the 11-permutable I showed: I can get 3- and 6-permutables (previously I only found 2- and 5-permutables), but nothing above that ... so no way of adding any number of clues to get 7 solutions.

That was rather long-winded, but I thought I should own up to my oversight.

Now, this ...

What is the maximal n , such that a p(n)-permutable set, will lead to p(k) permutable sets for all 1<=k<n, by removing 1 or more of the elements of the set, in successive operations ?(readd the element, if needed).

I need to be careful before attempting to answer that, by restating the question in my own words. Please tell me if this is equivalent to your question ...

• define a set of clues to be n-FPPS if it is p(n)-permutable and it contains at least one p(k)-permutable subset for each k=1,...,n-1
• we seek the maximum n such that there exists at least one n-FPPS set of clues

...