17-clue and 18-clue Sudoku update

Everything about Sudoku that doesn't fit in one of the other sections

Postby Havard » Sat Jul 28, 2007 2:15 pm

JPF wrote:
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
Havard
 
Posts: 378
Joined: 25 December 2005

Postby gsf » Sat Jul 28, 2007 2:25 pm

Havard wrote: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
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby wintder » Sat Jul 28, 2007 2:41 pm

gsf wrote:
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.
wintder
 
Posts: 297
Joined: 24 April 2007

Postby gsf » Sat Jul 28, 2007 2:52 pm

wintder wrote:-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
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby wintder » Sat Jul 28, 2007 4:28 pm

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

You are saying, making a rule: ?
wintder
 
Posts: 297
Joined: 24 April 2007

Postby wintder » Sat Jul 28, 2007 4:35 pm

I don't see why 1 off, 1 on, on a valid puzzle, cannot
be a seed for all puzzles.
wintder
 
Posts: 297
Joined: 24 April 2007

Postby wintder » Sat Jul 28, 2007 4:51 pm

gsf wrote:
wintder wrote:-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


gsf wrote: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.
wintder
 
Posts: 297
Joined: 24 April 2007

Postby coloin » Sat Jul 28, 2007 5:29 pm

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,
gsf wrote: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
coloin
 
Posts: 2365
Joined: 05 May 2005
Location: Devon

Postby wintder » Sat Jul 28, 2007 7:34 pm

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"?
wintder
 
Posts: 297
Joined: 24 April 2007

Postby coloin » Sat Jul 28, 2007 7:47 pm

wintder wrote: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 !

wintder wrote: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
coloin
 
Posts: 2365
Joined: 05 May 2005
Location: Devon

Postby wintder » Sat Jul 28, 2007 7:54 pm

coloin wrote:
wintder wrote: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 !

wintder wrote: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....)
wintder
 
Posts: 297
Joined: 24 April 2007

Postby coloin » Sat Jul 28, 2007 8:19 pm

wintder wrote: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
 
Posts: 2365
Joined: 05 May 2005
Location: Devon

Postby coloin » Sat Jul 28, 2007 11:41 pm

JPF wrote: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
coloin
 
Posts: 2365
Joined: 05 May 2005
Location: Devon

Postby gsf » Sun Jul 29, 2007 8:28 am

wintder wrote:
gsf wrote: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
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby kjellfp » Mon Jul 30, 2007 2:03 pm

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?
kjellfp
 
Posts: 140
Joined: 04 October 2005

PreviousNext

Return to General