17-clue and 18-clue Sudoku update

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

Postby coloin » Wed Aug 15, 2007 6:52 pm

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:idea:

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
coloin
 
Posts: 1638
Joined: 05 May 2005

Postby Havard » Wed Aug 15, 2007 9:52 pm

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

Postby daj95376 » Wed Aug 15, 2007 10:15 pm

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 ???
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby gfroyle » Thu Aug 16, 2007 2:10 am

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)
gfroyle
 
Posts: 214
Joined: 21 June 2005

re: Lars Petter Endresen's new 17s

Postby Pat » Thu Aug 16, 2007 3:39 pm

Havard wrote:
JPF wrote:
ronk wrote: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 ??
User avatar
Pat
 
Posts: 3448
Joined: 18 July 2005

Postby gsf » Thu Aug 16, 2007 5:06 pm

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

Re: re: Lars Petter Endresen's new 17s

Postby Lars Petter Endresen » Thu Aug 16, 2007 5:14 pm

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
Lars Petter Endresen
 
Posts: 7
Joined: 03 June 2007
Location: NORWAY

Postby coloin » Thu Aug 16, 2007 6:11 pm

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
Last edited by coloin on Fri Aug 17, 2007 6:59 am, edited 1 time in total.
coloin
 
Posts: 1638
Joined: 05 May 2005

Re: re: Lars Petter Endresen's new 17s

Postby daj95376 » Thu Aug 16, 2007 6:15 pm

Lars Petter Endresen wrote: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.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby gsf » Thu Aug 16, 2007 6:46 pm

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

Postby JPF » Thu Aug 16, 2007 10:46 pm

I wrote: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
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby Lars Petter Endresen » Sun Aug 19, 2007 7:29 pm

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
Lars Petter Endresen
 
Posts: 7
Joined: 03 June 2007
Location: NORWAY

Postby Mauricio » Tue Aug 21, 2007 11:34 pm

coloin wrote: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.
Mauricio
 
Posts: 1174
Joined: 22 March 2006

Postby coloin » Wed Aug 22, 2007 1:49 am

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
coloin
 
Posts: 1638
Joined: 05 May 2005

Postby gfroyle » Thu Aug 23, 2007 11:50 am

gsf wrote: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
gfroyle
 
Posts: 214
Joined: 21 June 2005

PreviousNext

Return to General