The New Sudoku Players' Forum

[Havard]

The discussion here seems to be on whether n=3 gives only one equivalence class for the family of all 17s. My guess is no.

I did a -3+3 on two 17 clue sudoku that was closed with a -2+2. No other sudoku came out of that, so if your question is wether you can arrive at all the 17 from doing +3-3 on one, then the answer is no.

Havard

[gsf]

It seems we are talking about equivalence classes of 17s, based on {-n+n} operations.For a fixed n, say that two 17s are directly n-related if there is a {-n+n} changing the first into (a puzzle isomorphic to) the other. Puzzles are n-related if they are related by the equivalence class generated by directly n-relation.

almost
to get closure the {-n+n} op may have to be applied multiple times (notated {-n+n}xm for m times, {-n+n}x1 means {-n+n})
so two puzzles are in the same {-n+n} equivalence class if one can be derived from the other by {-n+n}xm for some m>=0 (m=0 for the identity)

here's a simple example (for all readers) to get a handle on closure and equivalence classes

given the integers modulo 8 { 0 1 2 3 4 5 6 7 } and the operator (n+2),
(n+2) partitions the set into two equivanence classes, { 0 2 4 6 } and { 1 3 5 7 }

[ronk]

to get closure the {-n+n} op may have to be applied multiple times (notated {-n+n}xm for m times, {-n+n}x1 means {-n+n})
so two puzzles are in the same {-n+n} equivalence class if one can be derived from the other by {-n+n}xm for some m>=0 (m=0 for the identity)

if I specify {-n+n}xM and if closure is obtained for some m < M
does execution terminate early?

is there a significant difference in total execution time
between running {-n+n}x1 twice and running {-n+n}x2 once?

[gsf]

to get closure the {-n+n} op may have to be applied multiple times (notated {-n+n}xm for m times, {-n+n}x1 means {-n+n})
so two puzzles are in the same {-n+n} equivalence class if one can be derived from the other by {-n+n}xm for some m>=0 (m=0 for the identity)

good questions

if I specify {-n+n}xM and if closure is obtained for some m < M
does execution terminate early?

each round of {-n+n} may produce new and old puzzles
new puzzles are sent to the next round
closure is reached when a round produces no new puzzles
so if that happens for #rounds<M the execution can terminate early

is there a significant difference in total execution time
between running {-n+n}x1 twice and running {-n+n}x2 once?

first, by definition, {-n+n}x1{-n+n}x1 is equivalent to {-n+n}x2
however, if the {-n+n}x1 are done in separate processes, it may run slower
than an {-n+n}x2 done in a single process because the single process implementation
can remember and prune intermediate (possibly pseudo) puzzles from previous iterations

so, e.g., with my solver, this

Code: Select all

sudoku -go{-2+2}x2 puzzle.dat

would probably run faster than

Code: Select all

sudoku -go{-2+2} puzzle.dat | sudoku -go{-2+2}

[coloin]

I did a -3+3 on two 17 clue sudoku that was closed with a -2+2. No other sudoku came out of that, so if your question is wether you can arrive at all the 17 from doing +3-3 on one, then the answer is no. Smile

Thanks for that havard....exceptions always turn up.....although at the time I remember you wrote no "new" 17s "popped" out.....

......just as there will possibly be an exception to JPFs theory

It is possible [theoretically] to have an 18puzzle which when subjected to {-2+1} which will provide 2 17puzzles - but these 2 17puzzles can differ by 4 clues !!!

any observations on the range of B?

By successive {-1+2}{-1+1}xlots I made 10035 18puzzles from a single [remote {2+2}] 17puzzle.

These theoretically provide [x136] 1364760 16subpuzzles
Canicalizing there are actually only 1261014 essentially different 16subpuzzles

So by producing more 18puzzles with a {-1+1} most of the time [93%] you are making new 2-offs in the {-2+1} function to find 17s.

Incidently 31 17puzzles were made...none new

As time goes by, gsfs program continually brings in new 17s....any thoughts when it will stop ?

C

[JPF]

Some thoughts now that zebras and butterflies disappeared for a while

In the same way, one should keep a 1off2on list of 18's from gordons list in order to reduce the amount of 18's that get searched for 17, and I think that was your point JPF? If anyone is interested I could generate such a list.

Yes, in some way.
My point was that doing a {-2+1} on a 18, which is a long process, does not take into account the fact that the set G of the actual 17s is almost closed for the 2 operators {-1+1} and {-2+2}.
So can we eliminate a 18 only by a quick check with G?

I agree with gsf and coloin that the list of 18s ={-1+2}G will be large.
coloin mentionned 40000 x 250 =10^7. [edited, thanks to coloin]

other idea :
Why not trying a {-2+1} on 18 clues puzzles with more than 1 solution (2,3,..)?

What do we know about Gordons current list? Is it closed for n=1 or n=2?

Gordons current list G is supposed to be kept closed for n=1 and n=2, from time to time (by Havard and now by gsf, and maybe by others).
I did a full {-1+1} a week ago.

How many equivalence classes do we get?

I think it's an information which could be of interest.
More precisely, what are the properties of the 17s within classes with many equivalent.
gsf, how is it possible to list, for each 17 of G, the equivalents modulo {-1+1} and {-2+2} ?

Code: Select all

 sudoku -go{-1+1} G.dat

eliminates the duplicates.

And a completely different question: What is the biggest number N for which we have proven that there is no N-clue Sudoku puzzle. We all believe that N=16 is the maximum, and it's obvious that N must be at least 7. But what do we know?

That is a recurrent question.
see here
The results are still poor.

JPF

[coloin]

The discussion here seems to be on whether n=3 gives only one equivalence class for the family of all 17s. My guess is no.

Well it might well be no........but.....
My remote{-2+2} 17 puzzle

Code: Select all

000000001000070002003004000000000030010000540600020000000010007000500000004000890 #41145

had these two 14clue subpuzzles in common with 2 of the 30 other 17puzzles I made indirectly from it.

Code: Select all

000000000000000001000002030000000004001000005020006000000000060000040720005800000
000000001000000002000003000000000040001000530060020000000010007000500000300000080


Code: Select all

7..........4.....1.....293.........4..1.....5.2...6..........6.....4.72...58..... #41145
...........8.9...1.....2.3.........4..1..9..5.2...6..........6.....4.72...58..... #28138
........1....7...24....3..........4...1...53..6..2........1...7...5.....3.....98. #41145
.97.....1........2...4.3..........4...1...53..6..2........1...7...5.....3......8. #38166

Did you really get no 17s havard

If you still have it I could quickly scan a few puzzles for duplicate 14s.....

JPF its 10 million 18s.... - too many for my duplicate sorter !

C

[gsf]

so, e.g., with my solver, this

Code: Select all

sudoku -go{-2+2}x2 puzzle.dat

would probably run faster than

Code: Select all

sudoku -go{-2+2} puzzle.dat | sudoku -go{-2+2}

well once again I should have thought twice submitted once
the speed of the two methods could be affected by hw appointments as well as the input
{-2+2}x2 may require more memory than the two process equivalent
and a memory hog on some hw/os configurations may incur time penalties;
on a multiprocessor system each of the {-2+2}x1 could run on separate processors
and that might wash any duplicate work between the two

[gsf]

As time goes by, gsfs program continually brings in new 17s....any thoughts when it will stop ?

I have three burning up idle cycles
output is spotty, but fairly consistent over a week
anyone with idle cycles should jump in

this one

Code: Select all

sudoku -go{-2+1}x4{-1+1}x4{-2+1} 7..9..3...8..5...6..2....1...13..7...5..2..4......8...9...6.......7..5....4..1.8.

produced 13 new ones over 3 days
I'm running a separate {2}! ({-2+2} closure -- solver not posted yet) on those 13 to see if there are any in the neighborhood

[gsf]

More precisely, what are the properties of the 17s within classes with many equivalent.
gsf, how is it possible to list, for each 17 of G, the equivalents modulo {-1+1} and {-2+2} ?

I'm doing a small experiment to estimate how many cpu days we'll need to get the {-2+2} closure of the entire 17 catalog
if it looks tractable I'll try to set up a script so the work can be divided on volunteer processors

right now it looks like the average {2}* ({-2+2} closure) equivalence class size is ~4
but there's one with 100 and counting

[kjellfp]

almost
to get closure the {-n+n} op may have to be applied multiple times (notated {-n+n}xm for m times, {-n+n}x1 means {-n+n})

This is what I meant (assuming that the puzzles you get between are also valid Sudoku and not multi-solution puzzles).
I used the term directly n-related for {-n+n}x1. For only n-relation, I mentioned the equivalence relation generated by directly n-relation. That would implicitly mean that two 17s G and H are n-related if there is a sequence

G_0, G_1, G_2, ..., G_k

of 17s, where G_0=G, G_k=H and for every i<k, you get from G_i to G_(i+1) by a {-n+n}.

I did a -3+3 on two 17 clue sudoku that was closed with a -2+2. No other sudoku came out of that, so if your question is wether you can arrive at all the 17 from doing +3-3 on one, then the answer is no.

That was my question, yes. So the family of 17s is not {-3+3}-connected. Interresting, by the way, this means that there is a {-2+2}-equivalence class which is the same as a {-3+3}-class.

These classes interrest me when looking for 16s. I had the second post in this thread, where I discussed whether 16s did exist. There I assumed that the 17s found where pretty randomly distributed among the entire family of 17s, and therefore 16s don't exist as they produce several 17s, with none found. I now change this attitude a bit. It's still correct that a 16 would produce 65 different 17s, but they are all {-1+1}-related, so that might be an equivalence class not found yet. Though I don't think there is a 16, I'm still hoping.

I think it's an information which could be of interest.
More precisely, what are the properties of the 17s within classes with many equivalent.
gsf, how is it possible to list, for each 17 of G, the equivalents modulo {-1+1} and {-2+2} ?

I don't think that should be difficult. Start with a 17, get its related ones, etc. Then mark them all in a bitmap grid, and repeat with the next uncovered 17.

[coloin]

Yes it should be possible to map them all.......a bit of a tangled web though

gsf with your program.....
Can we not do it by mapping the duplicate [canonicalized] 16subpuzzles of G
then
Purge these duplicates
then
Map the duplicate 15subpuzzles ?


Some new ones - all not in the {-2+2} large group

Code: Select all

.........45...9......2....1.....4.....1....27.......9...2..........453..9.6..3...
...4.6.8........23.........27........3..2....9.....5....5........65..4......3..7.
.2...6.........1.....1..5....9..........24..6.8...7..2..19........5......4......7

.2......9.571...6......7..........5.3....8.1.9.8.......................8.4.62....
.2......9.574...6......7..........5.3....8.1.9.8.......................8.4.62....
.2......9.57.1..6......7..........5.3....8.1.9.8.......................8.4.62....
.2......9.571...4......7..........5.3....8.1.9.8.......................8.4.62....
.2......9.57.1..4......7..........5.3....8.1.9.8.......................8.4.62....

Any good reason why we havnt found [until now] this secluded batch of 5 all within their own{-1+1} ?

C

[gsf]

Yes it should be possible to map them all.......a bit of a tangled web though

gsf with your program.....
Can we not do it by mapping the duplicate [canonicalized] 16subpuzzles of G
then
Purge these duplicates
then
Map the duplicate 15subpuzzles ?

well that's the insight I needed
I used my solver to generate a file from G containing lines of Gi,Sij
where Gi is puzzle i from G and Sij are the minlex 15-clue subgrids for Gi
that took ~5 min
a 30 line ksh script reads this data and lists the equivalence classes as lines of
Gi,i,Ci
where Ci is the equivalence class label for puzzle index i
(implemented using the smallest j for Gj in the class)
that took ~4 min

so the equivalence classes are easy to derive
but this does not guarantee that all {-2+2} members are represented in each class
that would take the longer computation of generating each class by applying {-2+2}* to one member of each class

I'll see if generating the {-3+3} classes is feasible later today
then I'll post the data
the largest class has 489 elements
I'm running -go{-2+2}* (I'll post that version of the solver with the data) on that class to double check

[gfroyle]

so the equivalence classes are easy to derive
but this does not guarantee that all {-2+2} members are represented in each class
that would take the longer computation of generating each class by applying {-2+2}* to one member of each class

Seems too fast to me....

Let me clarify my understanding of what is happening

(1) Given a puzzle P, you can generate the list of 136 15-clue pseudo-puzzles - call that L(P)

(2) Two puzzles P and Q are DIRECTLY {-2+2} related if and only if L(P) and L(Q) contain at least one pseudo-puzzle in common

But now I cannot see how you can quickly compute equivalence classes from this information ... essentially we need to know all the DIRECT relationships (which seems to require checking L(P_i) against L(P_j) for all i \not= j)....

I'm sure I have missed something, probably obvious...

gordon

[coloin]

It will be a tangled web......

With canicalization gsf can get the 17-puzzles [that we know of] within the same {-n+n} easily.

I had always pictured the interconnecting puzzles which tour the {-2+2} operation as a very large group.

Each puzzle will have its own {-1}{-2}and ?{-3} conjoins.

This will be a computational exercise which I can only guess gsf is possibly getting to grips with !!

C