The New Sudoku Players' Forum

[gfroyle]

A new contributor who wishes to remain anonymous contacted me directly with a lot of new puzzles...

Old estimates of expected total numbers may need to be redone..

Cheers

Gordon

[JPF]

More than 5000 new puzzles posted !
It's about 5 years of my slow fishing party

Did he give you some clues on how he found them ?

Old estimates of expected total numbers may need to be redone..

JPF

[gfroyle]

Did he give you some clues on how he found them ?

This is a copy of part of the email from "anon17" ..

As for "how my code works" ... "coloin's" last few messages at "sudoku.com",
have the right basic idea.

These were mostly found using "{-1,1}{reduce}" test on a bunch of 18's
...18's that came from 19's produced using the same techniqe ... and so on.
I use a cache of 12000 puzzles, and start it out, containing one random puzzle.
After that, the code chooses a random "untested" puzzle from the cache,
and runs its tests on it, and moves on. Usually it just ends up making more
and more 18's (after a brief startup interval). When the cache fills up, I start
it all over again. Once and a while, of course ... one of the 18's reduces to
a 17. The 17's that get produced, get a {-2,+2}{reduce} test, run on them.
The "{reduce}" part, never works, of course!
In addition to that, I use one other method to make (mostly) 18's from 18's,
in conjunction with the {-1,+1} test. I look for small minimal unavoidable
sets in the solution grids (9 cells or smaller), and if they use 2 or more of the
"given" cells ... I change thier values to one of the "alternatives" for the
unavoidable set ... and check to see if the puzzle is valid. That test doesn't
produce as many 18's as the {-1,+1} test does ... but I think it improves
the "variety" of the 18's that get tested before the cache fills up.

[coloin]

Well done anon17

The {-1+1} on an 18 gives a non minimal puzzle - every so often.

I got it to find rapidly find 17s - which were not new.

The trick was to use different "varieties" as you say.
Certainly you dont use the 18s that can be made from "known" 17s with {-1+2} action.

I had planned to generate these and sift them from the test cache of 18s.

Interesting to see how easy/difficult it is to find new ones now !

C

[gsf]

A new contributor who wishes to remain anonymous contacted me directly with a lot of new puzzles...

ha
I have a script, tuned to the old trickle, that updates a local copy of the 17 db one puzzle at a time
which up to now has been more efficient than downloading the entire db and merging
if anon17 keeps it up may have to re-tune that script
any hint from anon17 on the 17 discovery rate?

[gfroyle]

I received the following message from anon17 with a request to post to sudoku.com (no, I don't know why he wants or needs anonymity).

To answer some questions ...

1) (Current, average) rate of producing new 17's:
One every 175000 18's tested.

About the "rate": It will depend on the cache size that
is used. I've been using a size of 12000, since I found
that dropping it from 60000 to 12000, nearly doubled the
production rate (at the time). A different size, might
work better now. When I first made that change, though,
I tinkered with the size for a few days, and for sizes
of 8000, 12000, 15000 and 20000, the normal fluctuation
(and continual decrease) in the production rate, was
enough to mask any differences.

2) My current rate of producing new 17's:
-- 50 a day (and dropping)
-- around 90-100 a day averaged over the past month

3) My rate of testing 18's:
101/sec, on 4 machines with the equivalent computing power
(for the task at hand) of 2.9 of my "hot rod" machine, which
is a 2.4Ghz/100Mhz AMD 64.

That will be difficult to believe, I would anticipate.
Even more difficult: 7.03s per 17, to do {-2,+2} tests,
on the "hot rod" machine.
For a clue to how it's done: in the full {-1,+1} test
(on an 18) the solver is called around 18*52 times, and
in the full {-2,+2} test (on a 17), it is called around
(17*16/2)*1467 times.
The solver is pretty fast too ... completing around 30000
calls per second, "for the task at hand", again.

4) My plans: run for a few more days, entering puzzles by hand
on Gordon's "sudokuid" page ... and then fall back into the
woodwork. But then I may just submit my "24 hours later"
finds, as "witness", and see how you guys do for a while,
with fewer 17's left to find. If I really do find 50 today, that
should put Gordon's list at around "20 to go, to make 47000".
And to sound a familiar chord: I'll predict that they won't
be as easy to find as they have been in the recent past
(using current methods).
-- Yeah, I'll go with the 2nd option
-- I have some empathy for Red Ed's (one time) comment
about electric bills, now that I've had my "ego boost".

5) Regarding coloin's questions about "{-1,+2} and {-1,+2}{-1,1}":
Yes, I think it's true that it isn't a good idea to run it/them
on the full spread of known 17's. I had some luck running a
{-1,+2}({-1,+1}+{2nd method})({-1,+1}+{2nd method}) test on some
of my "late finds". Being "harder to find" (on average), they
tended to produce a lot fewer 18's in the {-1,+2} stage, and
thereby shorten the time spent "per 17". I think that most of
the "hits" came on the 2nd {-1,+1}, but that may have been only
because (probably) there were more 18's being tested in that
stage. I think I tested around 4500 17's like that, and got
around 40 "hits". But the last 165 that I tested, produced
zero hits. Someone might have good luck, if they were to look
for 17's where the {-1,+2} test produces less than 100-150 18's,
and run with them. I saw a few of the "broad spectrum" 17's,
producing 1000 or more 18's in the {-1,+2} stage ... and
400-500 was "not uncommon".

6) There are a couple more things I probably should have mentioned
in my initial "code description":
a) I'm using a "prescreen list" of 17's that have "been
through the works", to avoid repeating old tests.
For the {-2,+2} tests, that would be very important,
unless your game is to try to produce {-2,+2} closures
before you run out of cache!
b) I add the puzzles to the cache, in a "canonical form",
and perhaps unfortunately, I only add "minimal" puzzles.
With that being true, before spending the time to do a
"reduce" test, the code can first canonicalize the 18's
(... usually 18's), and check for them in the cache.
If it finds one in the cache, then since it's minimal,
it won't reduce, and the code can move on. While that may
sound attractive, there's a drawback to it all, too.
An 18 that reduces a (new) "17", never gets tested as a
(non-minimal) 18, and that may end up meaning that a good
opertunity to find an additional (new) 17, has been lost.
My {-1,+2}{-1,+1}{-1,+1} experiments, were a twisted attempt
to compensate for being in that situation. (Don't try to
figure out "how it might compensate for it". I'm not sure
it even makes sense).

7) Last comments: I've been "lurking" at sudoku.com, for close to
two years now, and have always been impressed by the quality of
the discussion. I'll keep lurking, and listening. I hope that
nobody faults me for not volunteering source code or binaries
(or for "falling back into the woodwork"). I'll be more
entertained by the evolution of the conversation, that I hope
I've spurred on.

Cheers,
"anon17"

[coloin]

Anon17 certainly has tried hard to find many 17s......but despite the apparent 30 to 60 increase in speed in his programs we will never really be sure we have them all !

Although we are certainly miles furthur on than we were last week!

I get the impression that I cant possibly compete with with what anon17 has done. ! Although I see Gfroyle has made some more.

Actually he has done us all a favour, I would have long got tired before we reached the 47000 mark that we nearly are at present.

So........

Here is another method I have dreamt up

It is simple, probably doesnt work, but if it does it might mean we get more of these 17-critter puzzles.

Here is the plan

Our set of around 47000 puzzles can be canonicalized according to the "minlex of gsf" namely

Code: Select all

+---+---+---+
|123|456|789|
|45.|...|...|
|...|...|...|
+---+---+---+
|2..|...|...|
|...|...|...|
|...|...|...|
+---+---+---+
|...|...|...|
|...|...|...|
|...|...|...|
+---+---+---+

or

Code: Select all

12345678945................2.....................................................

Now here I present two consequetive 17s from my 41651 sample, numbered by numerical order.

Code: Select all

1413  #  000000009000700000700203000000000000694000000000000270002500000010090304000060000
1414  #  000000009000700000700203000000000000694000000000000270310090004002000000000560000

Code: Select all

+---+---+---+
|...|...|..9|
|...|7..|...|
|7..|2.3|...|
+---+---+---+
|...|...|...|
|694|...|...|
|...|...|27.|
+---+---+---+
|..2|5..|...|
|.1.|.9.|3.4|
|...|.6.|...|
+---+---+---+ #1413

Code: Select all

+---+---+---+
|...|...|..9|
|...|7..|...|
|7..|2.3|...|
+---+---+---+
|...|...|...|
|694|...|...|
|...|...|27.|
+---+---+---+
|31.|.9.|..4|
|..2|...|...|
|...|56.|...|
+---+---+---+#1414

The first 10 clues are common, and unlikely though it is , it is possible for there to be a new 17-puzzle "between" these two puzzles.

But we have to add 7 clues over 28 spaces, which is a big ask as there are an awful lot of ways to add those 7 clues........but do not give up yet !

There will be significant clue option reductions

1
the puzzle has to solve to the minlex pattern
12345678945................2.....................................................

2
the 7 clue insertions by nature have to be with in minmax limits set by the 2 puzzles.
So the puzzle can have its first clue inserted at either a 2@r7c3 or a 3 @ r7c1
That leaves 6 clues to fill in to 24 spaces......and if there is one it is new.

If these insertions can be organized/calculated/iterated and processed easily and quickly we could be able to go through many [surly not all] of the gaps in our sample of 47000 puzzles. Of course many of the gaps are smaller than this and many are larger.

EDIT - Here are 2 "new" ones of anon17 in between 2 from the old list.......

Code: Select all

old  #  003000700000700102089000000000300000000090000060000004310000000000004006000005090
new  #  003000700000700102089000000004090050010000000000000000000000000000030094070102000
new  #  003000700000700102089000000040005000000000070000004090000000000800930000060000500
old  #  003000700000700102089000000260004000000000390000000000040100005000000000000830000

7 clues in common.....slightly bigger computation i expect

C

[JPF]

Actually, #1414 = {-2+2} #1413

(swap rows 7 and 8)

JPF

[coloin]

Yes, that is true, well spotted.....except the proviso was to fill the remaining clues in increasing minlex "fashion".

I'm not sure how easy it would be to code.....except the minlex ordering is I believe quick and easy. Many of the ways to insert the remaining 7 clues will be outside the minlex limits of the two puzzles.

BTW I found another 17 with my {-2+1} .......along with 4 others that are in anon17's additions.

C

[gsf]

there a strange coincidence in the ether
right around the time of anon17's additions my ~5/day processes dried up
I thought this meant that all hits by my processes were covered by anon17+previous_17s
but I checked the logs and there are only 2 anon17 hits

[JPF]

there a strange coincidence in the ether
right around the time of anon17's additions my ~5/day processes dried up
I thought this meant that all hits by my processes were covered by anon17+previous_17s
but I checked the logs and there are only 2 anon17 hits

Funny. I had the same feeling.
I made a long search, got around 300 17s.
No new 17.
Only 2 were from anon17.
The average number coming from anon17 "should have been" 300 x 5000/47000 = 32, assuming the number of anon17's addition = 5000

For this search my success ratio before any anon17' addition was = 2/300 = 0.7% wich was unusually low.

JPF

[coloin]

Well I think there has to be a statistical reason for this.

The numbers are

Code: Select all

900M  18s perhaps                                           
These include the "productive"                                               
47000 * 63 non-minimal 18s      [1 in 300]                               
47000 * ?250 minimal 18s          [1 in 90]                           
all "non-productive" other 18s [wont give us a 17 with a {-2+1}]

We generate a stack of 18s , if we are lucky there will be a few of the productive 18s - except there are an increasing number of non-productive 18s.

anon17 has been finding his 17s from a deeper search for non-minimal 18s rather than our shallower [because we cant process as many puzzles] {-2+1} search.

anon17 alludes to that his 17-puzzles dont have as many 18s within {-1+2}

Code: Select all

random puzzle #17338                                                             
030000004000010000000050000500300700080200000000000100600000510002408000000000070
581 18-puzzles    [~63 non-minimals and ~518 minimals}                                                               
                                                                                 
anon17 #45000                                                                   
100006070000090010040000000020000905000400000090000000000050200700300000800200000
181 18-puzzles  [63 non-minimals and 118 minimals]                                                                 
anon17 #45004
000204070810000009000000000002410000000000308050000000900080000300000040000000200
211 18-puzzles                                                                   


That would explain why you are tending not to get them with the {-2+1} method.

I am "searching" a 17-puzzle with only 122 total related 18-puzzles - see what the distribution will be.

I compared a few 14-subpuzzles ......and many of anon17s puzzles have 3* compatriates with just an equivalently sized selection from the main bunch. So many would appear not to be particularly remote........

C

[JPF]

Well I think there has to be a statistical reason for this.
...
That would explain why you are tending not to get them with the {-2+1} method.

It's probably true.
It can explain why gsf and I hit so few anon17s.

But what about the lack of new 17s ?
Maybe bad seeds ?

I wonder also why the number of 17s has been stuck at 46999 now for 1 day...

JPF

[wintder]

I am wondering.

Did anon17 decide to post when his results were stalling?

If so 47000 may be near the total.

[coloin]

If it was a statistical quirk....it would have reduced gradually - not abruptly, so there might be other things going on.

I will look at a few 18counts of the 17s that we found pre anon17

I am wondering

I am wondering if anon17 is gfroyles alter ego

If anon17 is still finding 50 a day....I dont think the end is near

C