The New Sudoku Players' Forum

[coloin]

Im not sure if we will ever be sure we will have caught and tagged all the 17s in the lake

But, after a few weeks off, and looking over gsfs excellent work its clear that almost all 17s have at least one 17 within 4*.

But the new ones that Lars has posted are interesting

Code: Select all

..57....9
.12......
.4..3....
.....42..
.........
3....2..6
8..57....
.........
......84.

Why have we not found these ones before - after what has been now a large random "trawl" !

The way these 17s are/were generated is to do a -2+1 on an 18. But we havent found/used any of these [many] 16clue sub puzzles that are in Lars puzzles before.....because....they are unusual........

All Lars' puzzles have 1 empty row [edit - plus spaces in the above and below rows in rows 7,8,9] in 2 of the horizontal shutes - therefore all the 16 sub puzzles have these 2 empty rows. This might explain why we havnt found/used them before

I am doing a run on 21,20,19,->18s with this feature......this Im confident will throw out new 17s...[if there are any that is]

C

[Havard]

OK, I'll try this guessing game too. Starting with 33,420 20s Lars generated 2,135 17s of which 58 were new. Then a 2-off/2-on run on these 58 yielded an additional 30 new 17s ... for a total of 88.

It was my interpretation

JPF

...and that is the right one!

Havard

[daj95376]

Then why did LPE say ...

In the table, n17 denotes the new Sudokus that was added to Gordon's list today.

... if he generated 88/146 new 17s ???

[gfroyle]

Code: Select all

mysql> select name, count(*) from sudoku17 where date(date) = '2007-08-14' group by name;
+----------------------+----------+
| name                 | count(*) |
+----------------------+----------+
| coloin               |        2 |
| Gordon Royle         |       18 |
| gsf                  |        4 |
| Jim Wilson           |        3 |
| JPF                  |       12 |
| Kohei Noshita        |        1 |
| Lars Petter Endresen |       97 |
+----------------------+----------+
7 rows in set (0.09 sec)


[Pat]

OK, I'll try this guessing game too.

Lars generated 2,135 17s,
of which 58 were new;
then a 2-off/2-on run on these 58
yielded an additional 30 new 17s
for a total of 88.

It was my interpretation

...and that is the right one!

thanks!

and gfroyle has also shown that 146 wouldn't fit,
hence 58+30=88 must be right.
so we are missing a column
for 17+2-2 puzzles produced

58 new out of 2,135
+ 30 new out of how many ??

[gsf]

What *I* want to know is more detail about the structure of the graph on the 17s... what are the degrees of the vertices (i.e. the number of neighbours that each puzzle/vertex has), which puzzles have the highest degree etc. (Could it even be that this graph is a scale-free graph in the Barabasi et al sense?)

I can see that at some stage I will have to compute this darn graph myself and just confirm your numbers....

here is a degree distribution plot for |G|=41596
the left and right (x,y) coordinates are (1,177) and (923,1)
177 vertices have degree 1, 1 vertex has degree 923
the vertex with highest degree 923 corresponds to puzzle #02222
there are 6,443,140 edges, and the (text) edge list data file size is 74Mi (12 bytes per edge)

[Lars Petter Endresen]

Dear Sudoku Gentlemen,

I am really sorry for the confusion. I found alltogether 88 new 17s, of with 58 were found without any 2 on/off search. Now, based on my list of initial 17s (all of them!), I have made another table (I hope to not confuse so much this time),

Code: Select all

        5    10    15    20    25    30   35   40

207   181   160   136   105    77    44   19    4
193   176   139   118    89    72    48   23   13
190   172   140   118    99    72    49   26   10
182   148   131   105    93    70    49   24    6
107    87    83    69    44    44    24   14    8
416   363   315   275   207   155   101   60   15
209   186   160   139   110    79    48   16    4
150   133   119   101    79    60    40   25   10
169   150   135   110    83    66    48   28    6
312   279   226   176   135    91    59   25    8


If we assume that the 17s I found are completely random, then we need to know how many are new as a function of the number of already found on Gordon's excellent list of all 17s. So, in the first column I have substracted the first 5000 on Gordon's list, then the next 10000 and so on. Now, can we conclude anything about how many 17s are left from this way of viewing my Sudoku experiment?

Have fun!

Yours Sincerely

Lars Petter Endresen

[coloin]

Thankyou Lars......it seems that my theory didnt work !
But gfroyle does show that many [significantly more ?] of your new puzzles have empty 2 rows !

Extending the theory with several thousand 18s devoid of "perimeter" clues gave me these only two puzzles......unfortunately not new either !

Code: Select all

+---+---+---+
|...|...|...|
|.6.|...|.8.|
|..1|27.|5..|
+---+---+---+
|..7|.2.|...|
|...|..6|.4.|
|.8.|...|.3.|
+---+---+---+
|..5|...|2..|
|.3.|..8|.6.|
|...|...|...|
+---+---+---+
             
+---+---+---+
|...|...|...|
|.4.|...|...|
|...|68.|7..|
+---+---+---+
|..7|..3|5..|
|...|4.1|.2.|
|..6|...|...|
+---+---+---+
|..5|.7.|8..|
|.1.|..2|.4.|
|...|...|...|
+---+---+---+

Continuing to search around.........

Code: Select all

+---+---+---+
|...|.9.|6..|
|.4.|8..|...|
|...|6..|...|
+---+---+---+
|..7|...|5..|
|...|4.1|.2.|
|..6|...|...|
+---+---+---+
|..5|.1.|...|
|.1.|..2|.4.|
|...|...|.8.|
+---+---+---+

did find this new one.....but not extraordinary

gsf please explain to us what your excellent graph means !

C

[daj95376]

Now, can we conclude anything about how many 17s are left from this way of viewing my Sudoku experiment?

Yes, we can conclude that the last column adds up to 84.

[gsf]

gsf please explain to us what your excellent graph means !

note: two graphs in context, I'll call the (x,y) plot a plot to differentiate
Gordon had some questions about the structure of the graph G/12 (better notation anyone?) where
two puzzles (vertices) are connected by an edge if they share a 12 clue subgrid;
for |G|=41596, G/12 is connected, i.e., there is a path from any puzzle (vertex) to every other puzzle (vertex)
the plot is #puzzles (vertices) y with degree x
this gives a hint at the structure of G/12, but I don't know what that means w.r.t. to the 17 search
although the dip at the upper left looks interesting
at the dip there are fewer puzzles with low degree than a smoothed version of the curve would suggest

[JPF]

I don't remember, what is the MLE of the number of fishes in that case .

For those interested in that estimator, see here.

Obviously, the fishing is biaised, as most of the 17s are not uniformly picked in the lake.
but...

JPF

[Lars Petter Endresen]

Hello,

The estimated number of 17s left seems to be reduced as the number of 17s found increase. This is seen if we plot the estimated number of 17s as a function of the number of 17s already found, according to the formula (new/found+1)*total. Based on the previous table we get,

Code: Select all

   5     10     15     20     25     30     35     40    est

9372  17729  24855  30145  34300  36377  38213  40773  42388
9560  17202  24171  29223  34326  37461  39171  42694  45642
9526  17368  24316  30421  34474  37737  39789  42105  45088
9066  17198  23654  30220  34615  38077  39615  41319  44936
9065  17757  24673  28224  35280  36729  39579  42991  45897
9363  17572  24916  29952  34315  37284  40048  41442  44347
9450  17656  24976  30526  34450  36890  37679  40766  42171
9433  17933  25100  30533  35000  38000  40833  42667  45723
9438  17988  24763  29822  34763  38521  40799  41420  45080
9471  17244  23462  28654  32292  35673  37804  41026  43150
                                                  min  42171
                                                  max  45897
                                                  avg  44442


The estimate in the last column is based on simple curve fitting to the formula "total=a*tanh(b*n)", with a = 44442 as the best estimate!

Obviously, this analysis does take into account the fact that some 17s may be difficult to find.

Best Regards,

Lars Petter Endresen

[Mauricio]

Extending the theory with several thousand 18s devoid of "perimeter" clues gave me these only two puzzles......unfortunately not new either !

I extended your search, and found something interesting.

So far there are only 31 17's puzzles with that property (devoid of perimeter), with those 31 I generated 1020 18's keeping the property, and then I did a 1off/1on that kept the property, generating a total 133722 puzzles (the 1off/1on was done until closure). Those sudokus are in only 2 1off/1on equivalence classes, one of those two almost covers them all and a miniclass of 55 members(those 55 are children of a sudoku discovered by Lars).
Just minimalizing that list gave no new 17's.

If someone is interested in those 133722 sudokus, they are here.

[coloin]

Thanks for extending that line of enquiry......
It explains why i didnt find any.....it looks as if Lars was searching using an empty row filter !

I too have been generating 18s using a {-1+1} on existing 18s.........but i am suspicious that if repeated too often subsequent 18s produced have a low yield of new 17s.

On a similar line to JPF

Does this mean that if Z is the set of known 17s which are closed to 2*
Then all the 18s made from [Z]{-1+2}x1{-1+1}x1 will not yield a new 17.

Taking an average 17 puzzle
{-1+2} gives 700 [min and non-min] 18s which gives some 4000 18s with a furthur {-1+1}.

This is starting to be a significant amount of the total number of 18s [?10^9] Any idea how we can avoid making these ?

C

[gfroyle]

here is a degree distribution plot for |G|=41596
the left and right (x,y) coordinates are (1,177) and (923,1)
177 vertices have degree 1, 1 vertex has degree 923

Nice picture... but not quite the clear power-law decline that we might have hoped for...

One thing though - you say that the left-hand point is (1,177) but there is clear red line going well above 200 at x=1 or x=0; is this an artifact of your plotting program or is there some mistake...

Cheers

Gordon