The New Sudoku Players' Forum

[Havard]

The idea is to save time in screening the 18s.
There is no need to look at C(18,2)x65xp (1<=p<=9) puzzles if we can quickly say that one of the 18 17s is in G.

I don't know if it's practically true.

JPF

There is definately a point to what you are saying.
When searching for a 39, I have been trying to make as many 38 as I possibly can. Now, in order to find one 38 you need on average 250 37. To find a 37 you need on average 8 36, and to find a 36 you need on average 8 35's. That means roughly 16000 35 per 38. Now I have so far found 136 minimal 38. By doing a "reverse" 2off1on on the list of 38's three times, I get a massive list of 35's that I then can exclude from all the 35's I am making. This then prunes the search a lot, allowing me to already at the 35 stage get rid of a lot of puzzles that are not needed.

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.

Havard

[gsf]

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.

that 18 list would be large

I think the point is to impose additional requirements on adding a 17 to the catalog
and use those requirements to prune 18's -- a space time tradeoff
the 18's would still get generated, but the first {-2+1} 17 would determine if the 18 had any new 17's

[wintder]

there exits 17 clue puzzles that have only 1 puzzle in the {-1+1} closure
e.g.

Code: Select all

sudoku -go{-1+1}x99 000405000003000090000008000040000000000060030500001000000000001800002500009030004

produces only the input puzzle

-1 +1 from any 17 can generate all 17s.

You just have to keep going.,

closure is a word that you are misapplying.

[gsf]

-1 +1 from any 17 can generate all 17s.

You just have to keep going.,

closure is a word that you are misapplying.

closure depends on the definition of the operator
the {-1+1} operator used in this thread is constrained to generate valid puzzles
with that constraint closure has this meaning:
for any given puzzle, at some point, {-1+1} applied to that puzzle and all derived puzzles,
will cease to derive more puzzles -- at that point the set of derived puzzles is the closure

the {-1+1} operator applied to the set of all 17 clue puzzles will partition the puzzles into
disjoint sets, and the number of sets will be > 1

[wintder]

OK, from a 17, 17 off 17 on will get them all.

You are saying, making a rule: ?

[wintder]

I don't see why 1 off, 1 on, on a valid puzzle, cannot
be a seed for all puzzles.

[wintder]

-1 +1 from any 17 can generate all 17s.

You just have to keep going.,

closure is a word that you are misapplying.

closure depends on the definition of the operator
the {-1+1} operator used in this thread is constrained to generate valid puzzles
with that constraint closure has this meaning:
for any given puzzle, at some point, {-1+1} applied to that puzzle and all derived puzzles,
will cease to derive more puzzles -- at that point the set of derived puzzles is the closure

the {-1+1} operator applied to the set of all 17 clue puzzles will partition the puzzles into
disjoint sets, and the number of sets will be > 1

closure depends on the definition of the operator

Which I might understand with your source code. Most readers here would not.


http://www.bartleby.com/62/53/C0265300.html

An exception would be cool.

[coloin]

Easy......

I think JPF is correct. Nice extrapolation.

The 17s which are in the set of 17s which can be {-2+2} toured is finite

Most of these have been found [I found one new one in the set recently]

As JPF says the 18s that they come from {-2+1} cant provide a new 17 [not in this {-2+2} tour]

40000 17s gives 250 minimal {-1+2}18s per 17 on average,

that 18 list would be large

thats 10 million 18s which will provide a 17 with a {-2+1} process.

When you take a list of different 18s you need in the region of 200 18s to get a 17 using a {-2+1} method.

That works out at 2 billion different 18s.....which is about right.

I expect all 17 puzzles to be tourable {-3+3}.....as I have not found a remote 17 which doesnt. However the {-3+3} tour isnt practical....

For this not to occur there would have to be a puzzle which didnt share at least one 14clue subpuzzle with any of the other 14clue subpuzzles in the 40000 other 17clue puzzles.

There are 5 times as many 14clue as 15clue sub puzzles in a 17 clue puzzle
17 clue - 1 puzzle
16 clue - 17 ways to remove 1 clue
15 clue - 17*16/2 ways to remove 2 clues = 136
14 clue - 17*16*15/6 ways to remove 3 clues = 680

So thats 5x as many 14clue subpuzzles in one 17puzzle and 5x as many 14cluesubpuzzles in the other 40000 17puzzles to find an equivalent.

I think the best way to find new 17s is to search as many 18s as possible !!!...

C

[wintder]

So, there are zebras and butterflies in the 17 family and they cannot propagate from one to the other?

We are now looking for 17s that cannot be made to be other 17s?

I'm not very sure that I get this.

All 17s currently found are in one "family"?

[coloin]

So, there are zebras and butterflies in the 17 family and they cannot propagate from one to the other?

yes

you have to take gsfs example - it doesnt have any 17s near it within {-1+1} distance...most dont - although one 17puzzle I know has 18 other 17puzzles near it !

All 17s currently found are in one "family"?

possibly they all exist within {-3+3} of at least one other......but I could be wrong.

C

[wintder]

So, there are zebras and butterflies in the 17 family and they cannot propagate from one to the other?

yes

you have to take gsfs example - it doesnt have any 17s near it within {-1+1} distance...most dont - although one 17puzzle I know has 18 other 17puzzles near it !

All 17s currently found are in one "family"?

possibly they all exist within {-3+3} of at least one other......but I could be wrong.

C

Cool, along with finding new 17s there is a quest (possible) to genetically type them!

The down side is that there can be a 17 that needs 16 off 16 on from other 17s.

Any guess on how far back one would need to go from a valid 17?


4 off 4 on? (Not that current computers would, just wondering....)

[coloin]

The down side is that there can be a 17 that needs 16 off 16 on from other 17s.

No its usually possible to find 8 or 9 "equivalent" clues in any two 17puzzles

So it should be possible to find 14 equivalent clues from any one 17puzzle [680 chances] and at least one of the other 40000 17puzzles [680 chances].

There are many more [possibly 10x] more 15clue subpuzzles than 14clue subpuzzles. This explains we we have many [?5000] remote 17s which dont join in the [-2+2] tour.

C

[coloin]

The idea is to save time in screening the 18s.

If you have done a {-2+1} search on a collection of 18s

Does it follow that the new 18s generated by a subsequent {-1+1} on this collection can be disregarded. ?

Therefore you would be best searching alternate collections of new 18puzzles generated by {-1+1}

C

[gsf]

closure depends on the definition of the operator

Which I might understand with your source code. Most readers here would not.
http://www.bartleby.com/62/53/C0265300.html
An exception would be cool.

its this closure: http://en.wikipedia.org/wiki/Closure_%28mathematics%29
and you don't need the code
the definition was already given above
but I'll emphasize the important part just one more time
(its important because it makes analysis using the operator tractable with commodity hw)
{-m+n}: derive puzzles by first removing all combinations of m clues, then adding all combinations of n clues,
and finally verifying that each grid resulting from the addition of n clues, is valid

[kjellfp]

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.

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.

What do we know about Gordons current list? Is it closed for n=1 or n=2? How many equivalence classes do we get?

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?