The New Sudoku Players' Forum

[Moschopulus]

Yes it was given by dukuso here
http://forum.enjoysudoku.com/viewtopic.php?t=605&postdays=0&postorder=asc&start=86
on page 6.

I call these sets (9,2) unavoidable sets - they have 9 clues and we need 2 of them.

[coloin]

Here is an interesting collection of 29 17-hint puzzles... what do they have in common?

http://www.csse.uwa.edu.au/~gordon/sudokupat.php?cn=3

Very interesting set of 29 - which all have the same finishing solution.

However I think you could add a few more as the 16 grid which has two solutions looks and behaves equivalently to the above grid.

Gordon - When making all your 17s - I understand how you pick the final clues - but how do you decide which clues to use first ?

Do you know what the spread of the minimal number of clues for a particular grid is ?
ie
16 - 0 in 6*10^21 grids at the moment
17 - 1 in 10000 grids?
18 - ? most grids ..........? can almost all grids be expressed as an 18 ?
19 - canonical grid - it has been proven that an 18 doesnt exist for this grid but that a 19 does exist. This is a very symetrical paired grid which you would expect to be difficult to express with a small number of initial clues.

There is also another posting on the maximum number of nessesary clues - which is relevant to this thread. Can anyone clarify the spread issue. Are there some grids which cant be reduced to these minimal clue numbers i.e 18 ?

Regards

[coloin]

I have been trying hard to get grids down to minimal numbers - not successfully however.

Gfroyle has been turning out 17s - and despite their high frequency of occurrance a 16 has not turned up. Pessimism has set in and the quest for a 16 remains elusive.

The reason for the pessimism is highighted in Guenter's comments and work. The reasoning that if there is a 16 in any of the many grids it will have at least 65 [if not more] 17s inherent in it [[65=81-16] different superfluous clues]. It could also have 15 good clues and 2 not so good. [etc] . *

Also the frequency analysis of the 17s found already would tend to indicate that the grid is unimportant in finding a 16.

I think the fact that we havnt found a 16 [apart from the obvious !] is partly a reflection on the methodology - and this is confirmed by the fact that there was a similar distribution pattern of "gangsters" in Gfroyle's grids and a large random selection of grids.

The method of getting the 17s which G&G have been using - correct me if I am wrong - is to put in several initial clues randomly [This would explain the distribution !] which initially specifically generate a few more clues - and then fill in up to 17 clues which close the grid down and solve it uniquely. There may be a bit of juggling around with the final clues which may generate more 17s.

The choice of grid has to be important as quite clearly there are grids which stop at 18 clues and dont have a 17.[Guenter has shown elegantly that the repeating canonical grid cant have an 18 but has many 19s]. I am awaiting comments on this one.

I have been concentrating on the grid pattern of Gfroyles "29" - as I have assumed that there is more chance of finding a 16 in this grid. I am slightly reassured that this is the right grid because if there is a 16 in it it will have multiple 17s in it. [see above *]

+---+---+---+
|639|241|785|
|284|765|193| note 3/1 pair in B1&B2
|517|983|624|
+---+---+---+
|123|857|946|
|796|432|851| note the triple pair chain 2/9 in B4B5B6
|458|619|237|
+---+---+---+
|342|178|569|
|861|594|372|
|975|326|418|
+---+---+---+

I have been unsuccessful in getting anywhere near a de novo 17 with my method of clue insertion - I have partioned the grid into various box combinations and chosen what I percieved as valuable clues.I had used initial grid clues to reduce the combinations by 9!*72^2 , the presence of a pair and a triple pair chain is helpful in a way. However what I ended up with was a puzzle with 16 clues which had 800000 solutions. The individual effect of removing each one of the clues was :

11360461 sol
29820932 sol
10879133 sol
7709851 sol.
5917131 sol.
34483389 sol.
12036106 sol.
16392913 sol.
7960039 sol.
6379603 sol.
25390869 sol.
24701373 sol.
20010151 sol.
38160965 sol.
4138355 sol.
38014612 sol.

so they all were pretty good clues on their own - but not synergistic enough in combination.

What I need to do [but didnt]was to pick initial clues - not on their value of reducing the total solutions but on their value in reducing solution totals early on. The analysis of this is effectivly impossible as my excelent solver packs in effectivly at 200 million solutions, quite apart from time considerations. Gfroyle does this by filling the grid early on which picks 9 of one number and the rest of the clues are choosen carefully.

So where are we now.......well the fact that there are many 17s in gfroyles 29er series grid would indicate that this one is still a good one to look in. [I think there are more than 29 as the 16er with two solutions is effectivly this grid and there are at least 36 [9+9 *2] ways to make a 17er from the nearly "16er" .Possibly there are more.]

I can only hope that the reason that we havnt been able to reduce it from 17 to 16 is that we arnt able to go far enough back in clue removal and analyse the effect of multiple clue insertion. I am sure Gfroyle has tried very hard to do this and analysed what would appear to be the "super clues" in this grid. They may only be a proportion of the clues which are common to all the 29 that Gfroyle published [above]. Also we havnt optimized our initial clue insertion - which is difficult / impossible.

If there is a 16 out there - and I would be pleased to find one - all we need to do is find a combination of 16 clues which only occur in that grid [and not in the other 6e21] - this will be a uniquely solvable grid. We have done it for 17 clues - is the line drawn at 17 ?

I think a better method of chosing the initial clues has to be devised - and I am working on one.

Regards

[dukuso]

> gfroyle wrote:
> Here is an interesting collection of 29 17-hint
> puzzles... what do they have in common?
>
> http://www.csse.uwa.edu.au/~gordon/sudokupat.php?cn=3
>
>
> Very interesting set of 29 - which all have the same finishing
> solution.
>
> However I think you could add a few more as the 16 grid which
> has two solutions looks and behaves equivalently to the above
> grid.
>
> Gordon - When making all your 17s - I understand how you pick
> the final clues - but how do you decide which clues to use
> first ?
>
> Do you know what the spread of the minimal number of clues for
> a particular grid is ?
> ie
> 16 - 0 in 6*10^21 grids at the moment
> 17 - 1 in 10000 grids?
> 18 - ? most grids ..........? can almost all grids be
> expressed as an 18 ?

if my estimate of 5e5 nonequivalent 17s is correct,
then there should be only about 5e7 or 5e8 18s
out of 5e9 S-classes

> 19 - canonical grid - it has been proven that an 18 doesnt
> exist for this grid but that a 19 does exist. This is a very
> symetrical paired grid which you would expect to be difficult
> to express with a small number of initial clues.
>
> There is also another posting on the maximum number of
> nessesary clues - which is relevant to this thread. Can anyone
> clarify the spread issue. Are there some grids which cant be
> reduced to these minimal clue numbers i.e 18 ?

I give some statistics below



> I have been trying hard to get grids down to minimal numbers -
> not successfully however.
>
> Gfroyle has been turning out 17s - and despite their high
> frequency of occurrance a 16 has not turned up. Pessimism has
> set in and the quest for a 16 remains elusive.
>
> The reason for the pesimism is highighted in Guenter's
> comments and work. The reasoning that if there is a 16 in any
> of the many grids it will have at least 65 17s inherent in it
> [[65=81-16] different superfluous clues].
>
> Also the frequency analysis of the 17s found already would
> tend to indicate that the grid is unimportant in finding a 16.
>
>
> I think the fact that we havnt found a 16 is a reflection on
> the methodology - and this is confirmed by the fact that there
> was a similar distribution pattern of "gangsters" in Gfroyle's
> grids and a large random selection of grids.

why is it a confirmation ? I'd argue that this shows that Gordon's
method is not so much biased as he thinks.

> The method of getting the 17s which G&G have been using -
> correct me if I am wrong - is to put in several initial clues
> randomly [This would explain the distribution !] which
> initially specifically generate a few more clues - and then
> fill in up to 17 clues which close the grid down and solve it
> uniquely. There may be a bit of juggling around with the final
> clues which may generate more 17s.

fastest for me is to start from a full grid and remove
clues at random as long as there is still one solution

> The choice of grid has to be important as quite clearly there
> are grids which stop at 18 clues and dont have a 17.[Guenter
> has shown elegantly that the repeating canonical grid cant
> have an 18 but has many 19s]. I am awaiting comments on this
> one.
>
> I have been concentrating on the grid pattern of Gfroyles "29"
> - as I have assumed that there is more chance of finding a 16
> in this grid. I am slightly reassured that this is the right
> grid because if there is a 16 in it it will have multiple 17s
> in it.
>
> 639.241.785
> 284.765.193
> 517.983.624
>
> 123.857.946
> 796.432.851
> 458.619.237
>
> 342.178.569
> 861.594.372
> 975.326.418
>
> I have been unsuccessful in getting anywhere near a de novo 17
> with my method of clue insertion - I have paritioned the grid
> into various box combinations and chosen what I percieved as
> valuable clues.I had used initial grid clues to reduce the
> combinations by 9!*72^2 , the presence of a pair and a triple
> pair chain is helpful in a way. However what I ended up with
> was a puzzle with 16 clues which had 800000 solutions. The
> effect of removing each one of the clues was
>
> 11360461 sol
> 29820932 sol
> 10879133 sol
> 7709851 sol.
> 5917131 sol.
> 34483389 sol.
> 12036106 sol.
> 16392913 sol.
> 7960039 sol.
> 6379603 sol.
> 25390869 sol.
> 24701373 sol.
> 20010151 sol.
> 38160965 sol.
> 4138355 sol.
> 38014612 sol.
>
> so they all were pretty good clues on their own - but not good
> enough.
>
> What I need to do [but didnt]was to pick initial clues - not
> on their value of reducing the total solutions but on their
> value in reducing solution totals early on. The analysis of
> this is effectivly impossible as my excelent solver packs in
> effectivly at 200 million solutions, quite apart from time
> considerations. Gfroyle does this by filling the grid early on
> which picks 9 of one number and the rest of the clues are
> choosen carefully.
>
> So where are we now.......well the fact that there are many
> 17s in gfroyles 29er series grid would indicate that this one
> is still a good one to look in. [I think there are more than
> 29 as the 16er with two solutions is effectivly this grid and
> there are at least 36 [9+9 *2] ways to make a 17er from the
> nearly "16er" .Possibly there are more.]
>
> I can only hope that the reason that we havnt been able to
> reduce it from 17 to 16 is that we arnt able to go far enough
> back in clue removal and analyse the effect of multiple clue
> insertion. I am sure Gfroyle has tried very hard to do this.
> We also havnt optimized our initial clue insertion.
>
> If there is a 16 out there - and I feel there must be - all we
> need to do is find a combination of 16 clues which only occur
> in that grid [and not in the other 6e21] - this will be a
> uniquely solvable grid. We have done it for 17 clues - is the
> line drawn at 17 ?
>
> I think a better method of chosing the initial clues has to be
> devised - and I am working on one.
>
> Regards



here is some statistics, starting from a full grid and generating 1e6
random locally minimal sudokus from it.


1) one grid from each G-class at random
2) Gordon's grid with 29 17s, used by Colin above
3) our canonical grid,(1,1,1-1,1,1)
4) random sudokus,

Code: Select all


clues , 1)     2)      3)      4)   
----------------------------------
17,     0       0       0       0
18,     0       0       0       0
19,     0     4.3       0       5
20,    59     182       0     254
21,  2428    6051      85    8268
22, 33966   61826    1775   80869
23,170727  227480   21648  273518
24,342620  352289  116766  364111
25,298349  248568  286836  209158
26,122691   86061  329853   56006
27, 25237   15908  185028    7284
28,  2733    1547   50469     505
29,   205      74    7040      22
30,   7.6     8.6     486       0
31,     0       0      12       0
32,     0       0     2.4       0
-------------------------------------
aver.24.38   24.10   25.72   23.88



[coloin]

Great stats....so by random generation - Gfroyle's grids [which have a 17] didnt get reduced below 19 clues and the canonical grid [which have a 19] also didnt get reduced below 21.

Is this a hopeful statistic ?

What I want to know is the minimal suduku puzzle for each grid.

Canonical - shown to be 19 clues.

Gfroyles and others - 17 clues.

Is it reasonable assumpion that a random grid can always be reduced to 18 clues somehow [if you were to try hard enough - like we are doing to find a 16] ?

Colin

[dukuso]

with an estimated 1e17 locally minimal sudokus per grid
and about one 19 per million l.m. sudokus and 100-1000
19s per one 18 the average grid should have
1e8 18s and 1e4-1e5 17s for a total of 1e15 17s
in contradiction to my earlier estimate of 5e5.

hmm....

[coloin]

Thats a yes !!!! You think most grids have at least an 18 !

It might be 17 going on 15 then.

You might have been he first to comment on the prospect of finding "fools gold" !

The case continues .......... I think I have a good method...........I just want to give it a workout first..........

Coundnt do it without your solver though.

[coloin]

I think the recent posts highlight the improbability / near impossibility we face in getting a 16.

The minimal grids generated do not approach the 19,18 and 17 grids we know are possible which implies that we cant say that 16s dont exist on the basis that they are difficult to find. With my methods [I use a program which counts the number of soluions] I dont think I have generated a grid below 20.

Gfroyle has generated many, not really sure how he does it but he uses clues early on which fill up the grid, then he fills in the rest. I think he removes clues which then give more slightly different grids.

Guenter generates them by a reduction method, but the yield is sparse despite the huge depth of search. - see his data.

If there is a 16 it will have masses of 17s based on it I think.

Recently Guenter increased a prediction of the number of 17s rather markedly.

I have come to the conclusion that a computor based number crunching job is needed as in Bertram's. [Where is he ?]

Initially we have to pick a grid - and Gfroyles 29er series ["strangely familiar" group] seems the best bet [Can Gfroyle please confirm that the 16er with 2 solutions is indeed this group also ?]

The trouble with picking what you think are good clues to start with is that they get devalued in their global effect on reducing the number of solutions by the insertion of subsequent clues. To negate this we have to pick our initial clues for their clue generating ability - and then analyse the synergistic effect of almost all the remaining number of clues.

There are a large number [guess 10^16] of options to fill in 12 clues.

It is possible to reduce the options a little

use only 8 clue numbers
fill all the boxes with at least one clue
no more than 3 clues in a box
at least 4 clues in a chute

Pairs and triple pairs and linked pairs are both a help and a hindrance.

Comments please

[gfroyle]

Gfroyle has generated many, not really sure how he does it but he uses clues early on which fill up the grid, then he fills in the rest. I think he removes clues which then give more slightly different grids.

My techniques are purely based on perturbing existing solutions to get new ones - making small changes in a known 17 by altering or moving a couple of numbers and then hoping that the result will still be uniquely completable.

I do construct some 18s directly, and then hope that they will contain some 17s, which then go into the perturbation process themselves and so on..

I can confirm that the 16 with 2 solutions is indeed a subgrid of the "strangely familiar" grid that contains 29 uniquely completable 17s. I can also confirm that with 25000+ 17s now on board, there is still no other grid that contains more than 20 uniquely completable 17s.

Cheers

gordon

[dukuso]

there are some uncertaineties about the ratios 20s/19s , 19s/18s etc.

Just trying to extend the 1.55,3.68,10.2,33.2,42.3, in a reasonable way
it seems not appropriate to put 10000 or higher for the next
3rd term.
But Gordon has 25000 17s and no 16.

Suppose it goes ..,42.3,200,2000,50000
that would give some million or billion 16s
and maybe 1e13 17s

Now make the other statistics counting the solutions for all 16s.

We have 0,0,0,9,0,2,24,... 16s with 1,3,5,7,9,11,13 solutions so far.

[coloin]

I get the feeling the search for the 16 is hotting up. I have a search plan in progress which I feel will give us more 17s and perhaps a 16.

Here is my recent work which failed in getting any worthwhile minimal puzzles but I feel is a step in the right direction.


Here is a cunning Plan to pick initial clues - i did this ages ago but got distracted into combining clues from the other [8] "B12347/B5689" combinations.

This is Gfroyles strangly familiar grid

639241785
284765193 note 3/1 pair in B1&B2
517983624
123857946
796432851 note the triple pair chain 2/9 in B4B5B6
458619237
342178569
861594372
975326418


It can be broken down into two combinations

639241xxx
284765xxx
517983xxx
xxxxxxxxx
xxxxxxxxx
342178xxx
861594xxx
975326xxx this has 245952 solutions

the other half

xxxxxx785
xxxxxx193
xxxxxx624
123857946
796432851
458619237
xxxxxx569
xxxxxx372
xxxxxx418 this has 2925 solutions


If you add 5 clues
639241x8x
284765xxx
517983xxx
xxxxxxx46
xxxxxxxxx
xxxxxx2x7
342178xxx
861594xxx
975326xxx this has one solution - I dont think you will better 5 clues.


The other combination is better - if you add only 3 clues
x3xxxx785
xxxxxx193
xxx9xx624
123857946
796432851
458619237
xxx1xx569
xxxxxx372
xxxxxx418 this also has one solution - I am sure you cant better 3 clues


-3-----8-
---------
---9-----
-------46
---------
------2-7
---1-----
---------
--------- Of course this doesn't solve but it might be a good 8 clues to start from as what we need from the next 8 clues is for them to define completly either of the two partitions or both !........now how do we get the next 8 clues...............

...............unfortunatly the plan failed because any furthur clues added deminished the effect of these 8 clues. Shame - I thought it was neat.

Colin

[coloin]

This might be better but as yet I havnt solved it.

Using one of the above combinations in Gfroyles strangely familiar grid

x3x xxx nnx
xxx xxx nnn
xxx 9xx nnn

nnn nxn xxx
nnn nnn xxx
nxn nnn xxx

xxx 1xx xnn
xxx xxx nnn
xxx xxx nnn

One clue is ommitted from each box - it is self filling if you have the others
Box 6 is self-filling if the others are filled.

But if you can work out a way of inserting a minimum number of clues to define all the "n"s in the above grid then you will have a unique grid.

The following additional numbers are essential if the clue number omitted is "5". .

x3x xxx nnx
xxx xxx nnn
xxx 9xx nnn

nnn 8x7 xxx
nnn nnn xxx
nx8 nnn xxx

xxx 1xx xn3
xxx xxx nnn
xxx xxx 4nn

So you only have to define [27-1 = 26] "n"s.

So that is with 8 clues can you define these 26 out of 27 of the "n"s ?

Of course you can put your 8 clues anywhere in the grid.

Which is why I havnt succeeded !

6*72*71*.......67*66 = 6*72!/66! = 674952082560

The 6 is for the triple pair system in B456 one of which clues you must include.

Perhaps we should try this in a grid with more pairs ?

I think we will have a 16 soon !

[Moschopulus]

6*72*71*.......67*66 = 6*72!/66! = 674952082560

The 6 is for the triple pair system in B456 one of which clues you must include.

This "triple pair system" is an unavoidable set. gfroyle posted more unavoidable sets earlier in this thread, so maybe using these will cut down the number of choices further.

[coloin]

You are so right

I cant believe I have missed as many unavoidable sets in this grid as I have - and for so long !

That changes the prospects for the whole grid and the essential numbers will be changed. The computations will be reduced.

I need to revaluate this.

But maybe the method is right.

[Moschopulus]

It might be possible to do an exhaustive search for a 16 in the SF (Strangely Familiar) grid by distributing the computation and having many people participate. Each person would do a little piece of the program on their computer. At the end we put them all together and we will either have found a 16 or proved that none exists in that grid.

Would people be interested in doing this?

On the one hand, its a lot of work and trouble just for one grid. On the other hand, there is a lot of discussion about a 16 in SF and people seem to think it is the most likely candidate we have at the moment. So wouldn't it be nice to know the answer?

As someone said, "If we can know, it would be intolerable not to know".