The New Sudoku Players' Forum

[coloin]

I agree with your sentiments.

However I feel that The SF grid whilst having 29 17 clue solutions did represent a likely candidate for a 16 - I think that I have underestimated Gfroyles determined and valient efforts to find a 16 in this grid.

He has used a backtracking alorigrithm which if you take into consideration the large number of unavoidable sets must mean that he has fully investigated the grid - I didnt want to believe it at first but I do now. Perhaps Gfroyle can [re] confirm this.

I think the plan now must be to find another grid - Gfroyle seems to be the only one who can generate 17s with any effect - so I reckon his methods are good.

Regards

[gfroyle]

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.

I am not sure that an exhaustive search for any grid is feasible at the moment... the number of possible 16-clue subsets of the 81 cells is C(18,16) = 33594090947249085 and so a naive search is out of the question. Even if we had 1000 participants, each of whom could process 1000 grids per second, then according to my calculation it would take about 1000 years. We could knock it down to a year if we had a million participants, or could do a million grids a second.

Of course, a large proportion of those grids need not be tested because for one reason or another we know that they cannot be sudokus. These reasons would include things like having two empty rows/cols in the same 3x9/9x3 band, or missing 2 or more of the numbers. I feel sure that these restrictions will not help much. There is one avenue that I can't see my way through - if we could somehow accumulate much larger sets that are NOT uniquely completable, then EVERY 16-clue subset of those is automatically no good and need not be considered.. But I can't even begin to see how to do the bookkeeping required to keep track of all of those..

The other approaches, using minimum hitting sets (aka set cover) might be feasible, except that none of us know of any decent implementations of minimum hitting set...

At the moment, I can't think of any other approach, but of course, cleverness will always beat a naive approach or search... if you have some super clever technique in mind, then please let us know!

Cheers

Gordon

[dukuso]

look at this:
http://www.research.att.com/~gsf/sudoku/

this suggests, that the ratio of 17s/16s shouldn't be very large,
maybe some hundred.




>>solving Gordon's strangely familiar starts by filling in
>>the 6 missing ones.
>>
>>The pattern is this:
>>
>>...x.xx..
>>..1......
>>.........
>>.x....x..
>>.........
>>....1....
>>.......1.
>>.x.x.....
>>.........
>>
>>the ones are forced and you get this:
>>
>>...x.xx.1
>>..1......
>>...1.....
>>1x....x..
>>......1..
>>....1....
>>.......1.
>>.x.x.1...
>>.1.......
>>
>>
>>you might try to fix this pattern in your search.
>>Include 6 more "x" and search for a 22-clue puzzle
>>with that pattern, 6 ones can be removed then for a 16.
>

>>I generated 20000 locally minimal sudokus with this
>>pattern : average number of clues=23.38 (23.88 is for random generation)
>>and 42 20s (5 for random)

that's 420000 20s for a calculation with 2e8 sudokus as on the ATT-page.
8000 expected 19s , 100 expected 18s , 1 expected 17, 0.005 expected 16s
maybe more

>>Maybe we can get this 23.38 further down a bit with a larger pattern.
>>
>>
>>
>>this is the strangely familiar I used:
>>
>>...6.73..
>>2.1.....5
>>.........
>>.3....8..
>>7...2....
>>....1....
>>..5....1.
>>.7.8.....
>>...3.....
>>
>>
>>with solutions:
>>
>>594687321
>>281439765
>>367152498
>>139564872
>>758923146
>>426718539
>>845276913
>>673891254
>>912345687
>>
>>549687321
>>281934765
>>367152948
>>134569872
>>758423196
>>926718534
>>895276413
>>673841259
>>412395687

[Moschopulus]

The other approaches, using minimum hitting sets (aka set cover) might be feasible, except that none of us know of any decent implementations of minimum hitting set...

Thanks for your post. I certainly wasn't thinking of all C(81,16) subsets!

In the thread "grid not containing a 16" I posted the method. You basically find all the hitting sets. It took about 20 hours to show that grid has no 16. I was planning on using the same program, with suitable modifications of course. It would take "somewhat longer" for the SF grid since it does not have as many disjoint unavoidable sets. I haven't estimated how much longer it would take. The program could probably be made more efficient too. But anyway, given the low level of interest, it's not even worth figuring those things out.

[gfroyle]

In the thread "grid not containing a 16" I posted the method. You basically find all the hitting sets. It took about 20 hours to show that grid has no 16.

Your grid with no 16 was cleverly chosen because the unavoidable sets had such a large mutually disjoint subcollection; the grid with 29 17s does not have this nice property, which makes the enumeration of the hitting sets extremely difficult. I think I computed several thousand unavoidable sets and there was only a maximum of 11 or 12 mutually disjoint ones. I couldn't even figure out a decent algorithm to compute the 16-clue hitting sets in this situation, regardless of the time it would take..

Cheers

gordon

[coloin]

So potentially there is a chance that there is still a 16 in the SF grid to be found................

Well I will continue to try

Mosch. whats the next move ?

I have a program which given 12 clues can run through all the other clues to confirm/not confirm there is a 16.

But it is the 12 clues which are the problem !

Regards

[dukuso]

about 70& of Gordon's 17s have 3 ones and the other 6 ones are
forced. (upto isomorphism)

I think, in all these we can remove 7 clues, 3 of which are ones
and the other ones are still forced.

Upto isomorphism this gives a set of about 300 puzzles with
10 clues, 3 of which are ones and all the 6 other ones
are forced.

By starting from these 300 and filling in 7 other clues at random
we should get most of the existing 17-clues-sudokus.


How many possibilities are there ?

at most 300*C(65,7)*8^7 = 7.4e15

assuming we can check 1e6 of these per second
then it would take us
7.4e9 seconds or 235 years to generate (probably)
about 70% of all 17-clue-puzzles.

With >2e4 existing 17s we should find one 17 every
4 days, when we randomize the search.
The number of 17s found per 4 days should give an
estimate for the total number of existing 17s


Of course, we can reduce the search further by eliminating isomorphs
on 11,12,13,.. clues with breadth first.
Puzzles with 2 empty rows,columns,2 missing symbols
can be eliminated too.



-Guenter

[coloin]

I thought the recent entries warranted more attention by more interested parties.

To recap:

The minimum number of clues needed for a valid sudoku puzzle is 17.
For several months we have been debating the possibility of finding a 16 clue puzzle.....research has concluded that there potentially are 16 clue puzzles.

Taking a valid grid and randomly removing clues to a minimum commonly gives 24 or 25 clues......but producing puzzles [by random removal] with less clues than this is fairly difficult.

The most promising grid perhaps is a grid which has 29 different 17 clue puzzles.

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

this is number 2 of the 29 [2/29]
---24-7--
-8-----9-
-1-------
---8----6
7--------
4-----2--
3---7----
--------2
-----6-18

The following numbers in the completed grid are "related" in that at least one of each set [there are 16] is required for unique completion.

I think this is the 16 clue hitting set refered to :
{12,16,32,36,} {27,29,41,43,55,59,65,68,71,74,83,87,94,98,}
{16,19,26,27,58,59,74,77,83,84,93,98,} {31,32,41,45,62,65,}
{16,17,24,27,41,46,51,59,65,69,74,75,} {32,33,83,88,92,98,}
{13,14,21,28,34,38,73,79,85,89,91,95,} {42,47,52,56,66,67,}
{11,15,23,25,53,54,61,64,} {37,39,48,49,72,78,82,86,96,97,}
{15,18,35,39,44,48,54,57,97,99,} {22,23,61,63,72,76,81,86,}
{11,17,33,37,51,53,} {24,25,46,49,64,69,75,78,82,88,92,96,}
{13,17,24,28,33,34,46,47,66,69,75,79,85,88,} {51,52,91,92,}

This gives the "grid reference" for the clues in the grid, it includes all 81 clues, and some numbers occur in more than one set. I have a suspicion that there are more of these sets than the program that I have generates ?

It would appear that a 16 - if there is one in this grid - would come from a selection of these numbers.

The puzzle above [2/29] has these co-ordinates for clues
14,15,17
22,28
32
44,49
51
61,67
71,75
89
96,98,99.

just how many combinations of 16 numbers are there which includes all the numbers ?
....
4^2 * 6^4 * 8^2 * 10^2 * 12^4 * 14^2 = 539369039462400

possibly more if we hit two sets with with the same clue, and it is possible to cover all the sets with 8 clues - which explains why even Gfroyle cant do it !

The 29 puzzles always have a core number of these clues - in particular the 32,51 and 67.

The intriqing aspect of this problem - much more interesting than solving sudokus - is that there is a 16 out there somewhere ........but I am never going to find it.....

[udosuk]

On a side note, sorry if this has been discussed before and I missed it:

I remembered somebody claiming that the fewest clues for symmetrical puzzles are 18. But we could surely have a symmetrical one with 17 clues with 1 clue at the centre (R5C5). So is it proved that no 17-clue puzzle could be symmetrical?

(There could be all kinds of symmetry, as simple as 180 degree rotational... which is quite usual in newspaper puzzles...)

[coloin]

Hmm, looks like the sets we're interested in can be quite exotic. For example, in this nearly-completed grid ...

Code: Select all

639|241|785
284|765|193
5..|983|624
---+---|---
123|857|946
796|432|851
458|619|237
---+---+---
3.2|.78|.69
86.|.94|372
9..|326|.18

... you can have either of the following two ways of filling the gaps:

Code: Select all

...|...|...     ...|...|...
...|...|...     ...|...|...
.17|...|...     .71|...|...
---+---+---     ---+---+---
...|...|...     ...|...|...
...|...|...     ...|...|...
...|...|...     ...|...|...
---+---+---     ---+---+---
.4.|1..|5..     .1.|5..|4..
..1|5..|...     ..5|1..|...
.75|...|4..     .47|...|5..

Constructing sets like this is going to be a pain. Bleurrgghhh...

This quote from ages ago confirms my concern that there are many more sets in a grid than my program generates. What is going on here !

[dukuso]

but these sets should be rare.
So it might not be worth the effort to search for them

[coloin]

The sets may be rare......and the longer the chain is the probability that you havnt got a clue in them must get very small.

Having said that is it not true that every unique and solvable puzzle [17 clues and above] has a clue in every possible set combination ? - otherwise the puzzle would not have a unique solution / be solvable.

In Red Eds example above - which has a 4-number set - does every puzzle made from that grid have to include one from the 10 missing clues ? [I think - yes.]


turning the logic around -
Question - if you have a clue in each possible set does that mean the puzzle is solved ?

[I acknowledge that my program only picked out the 2 number unavoidable sets and that there will be considerably more 3 and 4 number sets in the grid]

[I admit that the longer chains may well not be worth bothering with as the chances of hitting them increase to very likely the more clues you insert.]

So who is able to come up with a program which spits out 16 numbers at a vast rate - potentially one of these group of clues has a unique solution.?

[dukuso]

>The sets may be rare......and the longer the chain is long the
>chances that you havnt got a clue in them must get very small.

? the bigger the set, the bigger the chances you have a clue in it

>Having said that is it not true that every unique and solvable
>puzzle [17 clues and above] has a clue in every possible set
>combination ?

yes. With set you probably mean what Moschopulos called "unavoidable set"

> - otherwise the puzzle would not have a unique solution / be solvable.
>
>Therefore this set cover has to be a valid method

it could just be slow in calculation time and hard to implement.

>Question - if you have a clue in each set does that mean the
>puzzle is solved ?

no. There are probably easy counterexamples.
Also, since any latin square can be made a subsudoku in some sudoku,
this would also solve the problem of critical sets in latin squares ..
So it can't be ;-)

>[I acknowledge that my program only picked out the 2 number
>unavoidable sets and that there will be considerably more 3
>and 4 number sets in the grid]

I think, these are rare compared to 2-symbol-u.sets

>[I admit that the longer chains may well not be worth bothering
>with as the chances of hitting them increase to very likely the
>more clues you insert.]

that's what I meant above.

>So who is able to come up with a program which spits out 16
>numbers at a vast rate - potentially one of these group of
>clues has a unique solution.?

depends on how vast, how much time is spent for the task,
how many 16s do exist, if any.

[coloin]

Thanks G
So......

How does an 18 clue puzzle define a 81 cell sudoku. [The concensus is that most grids have an 18 in them somewhere]
You get 8 clues which by and large "hit" the majority of the unavoidables in the grid.
You then get 5 more clues which inherently generate 5 furthur clues.....all these clues hit almost all the remaining unavoidables.
The last 5 clues are selected as they solve the grid against the 100 million or so other grids which still fit the above pattern. The fact that there is only one place for every addittional clue confirms that all the unavoidables have been hit.


The starting grid for a 17 clue puzzle is just slightly more obtuse [how?] The clues are hand picked and just a trifle more efficient.
[Note these 17s have been hand generated - are generally easy to solve - so there is room for more devious solving techniques to be employed which will result in a 16 - maybe]

So I think the unavoidables are useful up to a point........then there becomes just too many and over size 16 .....which as we seem to think this makes them sitting ducks for a selection of 15 plus clues.

So how do we pick the unavoidables in the first case ?
Well Gfroyles SF series of 29 puzzles have a large number of clues in common. Despite knowing this we havnt been able to reduce it to 16.

Dukuso has examined the SF grids and has generated statistics on 1e6 locally minimal puzzles generated by randomly removing successive clues from the completed grid

clues,
---------------------
17, 0
18, 0
19, 4.3
20, 182
21, 6051
22, 61826
23, 227480
24, 352289
25, 248568
26, 86061
27, 15908
28, 1547
29, 74
30, 8.6
31, 0
32, 0
-------------------
average 24.10

What I would like to know is what the clue distribution is in these ?

Or perhaps better/easier the frequency of the first clue [ie non minimal]that gives multiple solutions.[average 30 in randoms][around 28 in the SF]

If there is a 16 in the grid there will be many puzzle grids with a significant extra number of these 16 clues.

For example the frequency of the two sets of length 4 in the SF
{12,16,32,36,} - the 3/1 and 1/3 in Boxes 1&2
{51,52,91,92,} - the 7/9 and 9/7 in boxes 4&7

If this is different from 25% then the more frequent clue is the more valuable. [This will effectivly tell us which clue is envolved in more other conjoint unavoidable sets]

If the 1 in Box1 and the 7 in box4 turn out to be the best [as expected] then we can move forward by making that clue unremovable and go on to analyse other [significantly disjointed] unavoidable sets.

3 set numbers which are disjoint from other similar 6-chain sets in the grid.
{24,25,64,65,74,75}
{18,19,58,59,98,99}

The SF grid for reference

6 3 9 2 4 1 7 8 5
2 8 4 7 6 5 1 9 3
5 1 7 9 8 3 6 2 4

1 2 3 8 5 7 9 4 6
7 9 6 4 3 2 8 5 1
4 5 8 6 1 9 2 3 7

3 4 2 1 7 8 5 6 9
8 6 1 5 9 4 3 7 2
9 7 5 3 2 6 4 1 8

Has this already been done ?
I know wolfgang has assessed the clues wrt to their rookeries
http://forum.enjoysudoku.com/viewtopic.php?t=1527&start=30

40 36 23 | 53 88 56 | 36 61 71
22 71 40 | 48 61 39 | 48 52 29
41 134 42| 63 49 80 | 68 20 22

51 34 47 | 60 57 40 | 68 77 53
88 73 63 | 26 39 15 | 17 25 40
59 43 45 | 91 62 62 | 94 94 57

51 39 30 | 57 31 49 | 64 30 30
47 27 29 | 63 77 45 | 29 45 50
79 66 32 | 60 55 41 | 52 63 61

The 134 in r3c2 is the 1
The 88 in r5c1 is the 7 - not quite so dominant.

But we sort of know that already.

Maybe once we put in selected clues that are unmovable - the clue rate will come down and the best clues of the unavoidable sets to pick will become more obvious. Once we select a clue as "in" then I think this will affect the frequencies for the whole grid.

If this works - perhaps we are just going to replicate Gfroyles work - it might be a reliable/easy way to proceed in other grids.

Final point

There is one avenue that I can't see my way through - if we could somehow accumulate much larger sets that are NOT uniquely completable, then EVERY 16-clue subset of those is automatically no good and need not be considered.. But I can't even begin to see how to do the bookkeeping required to keep track of all of those..

? This could be done in a few seconds - hopefully

Regards

[dukuso]

hi Coloin,

that 16-clue thing seems to annoy you quite a bit.
You wanted to give it low priority, but still...

Gordon wasn't updating his list for some time, I don't know whether
he is still searching. Last time he said he got more and more instances
which he already had.


>How does an 18 clue puzzle define a 81 cell sudoku. [The concensus

naked/hidden singles, locked candidates,turbofish,...

>is that most grids have an 18 in them somewhere]
>You get 8 clues which by and large "hit" a large number of the
>unavoidables in the grid.
>You then get 5 more clues which inherently generate 5 furthur
>clues.....these almost certainly hit almost all the unavoidables.
>The last 5 clues are selected as they solve the grid against
>the 100 million or so other grids which still fit the above pattern.
>The fact that there is only one place for every addittional clue
>confirms that all the unavoidables have been hit.

I don't follow this 8+5+5 partition
you can hit some unavoidables while "fulfilling" other tasks

>The starting grid for a 17 clue puzzle is just slightly more
> obtuse [how?] The clues are hand picked and just a trifle more efficient.
>[Note these 17s have been hand generated - are generally easy
>to solve - so there is room for more devious solving techniques
>to be employed which will result in a 16 - maybe]
>
>So I think the unavoidables are useful up to a point........then
>there becomes just too many and over size 16 .....which as we
>seem to think this makes them sitting ducks for a selection of
>15 plus clues.
>10 clues hitting a 16 set = 0.090 probability of missing
>15 clues hitting a 16 set = 0.025 probability of missing
>
>So how do we pick the unavoidables in the first case ?
>Well Gfroyles SF series of 29 puzzles have a large number [14] of
>clues in common. Despite knowing this we havnt been able to reduce
>it to 16.
>
>Dukuso has examined the SF grids and has generated statistics on
>1e6 locally minimal puzzles generated by randomly removing successive
>clues from the completed grid

less than 1e6 here. And then extrapolated, you can see this by the 4.3 for 19s

>clues,
>---------------------
>17, 0
>18, 0
>19, 4.3
>20, 182
>21, 6051
>22, 61826
>23, 227480
>24, 352289
>25, 248568
>26, 86061
>27, 15908
>28, 1547
>29, 74
>30, 8.6
>31, 0
>32, 0
>-------------------
>average 24.10
>
>What I would like to know is what the clue distribution is in these ?

huh, they are scattered all over the board...

>Or perhaps better/easier the frequency of the first clue
>[ie non minimal]that gives multiple solutions.[average 30
>in randoms][around 28 in the SF]

I generate a random permutation of 81 and then try to remove
clues in that order.

>If there is a 16 in the grid there will be many puzzle grids
>with a significant number of common clues. All the 17s in the
>29 series had many common clues

hmm. I could just count the frequencies for the 81 cells,
independent of the number of clues in a particular sudoku

>For example the frequency of the two sets of length 4 in the SF
>{12,16,32,36,} - the 3/1 and 1/3 in Boxes 1&2
>{51,52,91,92,} - the 7/9 and 9/7 in boxes 4&7
>
>If this is different from 25% then the more frequent clue is the
>more valuable. [This will effectivly tell us which clue is envolved
>in more other conjoint unavoidable sets][And we know one of therse
>clues has to be in the last 16!]

that might work.., though unlikely. Anyway, here are the frequencies
for this sf:

594687321
281439765
367152498
139564872
758923146
426718539
845276913
673891254
912345687


frequencies for removed cells with 1e5 trials (clues frequencies
are 1e5 - these)
69037 68966 68983 68898 68973 68921 69083 68941 68643
68775 69155 69003 69090 68877 69057 69097 68968 68951
68804 69014 68844 69085 69052 69107 68973 68974 69260
68590 69001 69140 68782 69015 69295 69077 68803 69317
69007 69285 68928 68877 68922 69235 69158 68962 68691
68989 68966 69189 68831 69210 69143 69215 68844 68736
69264 69127 68873 68892 68736 69008 68740 69121 69259
69118 69075 68818 69058 69230 68921 69152 69096 69182
69199 69322 68856 69013 69190 69031 69047 68765 68873

Doesn't look good.


>If the 1 in Box1 and the 7 in box4 turn out to be the best
>[as expected] then we can move forward by making that clue
>unremovable and go on to analyse other [significantly disjointed]
>unavoidable sets.
>
>3 set numbers which are disjoint from other similar 6-chain sets
>{24,25,64,65,74,75}
>{18,19,58,59,98,99}
>
>The SF grid for reference
>
>6 3 9 2 4 1 7 8 5
>2 8 4 7 6 5 1 9 3
>5 1 7 9 8 3 6 2 4
>
>1 2 3 8 5 7 9 4 6
>7 9 6 4 3 2 8 5 1
>4 5 8 6 1 9 2 3 7
>
>3 4 2 1 7 8 5 6 9
>8 6 1 5 9 4 3 7 2
>9 7 5 3 2 6 4 1 8

sorry, I should have taken this one.


>Has this already been done ?
>I know wolfgang has assessed the clues wrt to their rookeries
>http://forum.enjoysudoku.com/viewtopic.php?t=1527&start=30
>
>40 36 23 | 53 88 56 | 36 61 71
>22 71 40 | 48 61 39 | 48 52 29
>41 134 42| 63 49 80 | 68 20 22
>
>51 34 47 | 60 57 40 | 68 77 53
>88 73 63 | 26 39 15 | 17 25 40
>59 43 45 | 91 62 62 | 94 94 57
>
>51 39 30 | 57 31 49 | 64 30 30
>47 27 29 | 63 77 45 | 29 45 50
>79 66 32 | 60 55 41 | 52 63 61
>
>The 134 in r3c2 is the 1
>The 88 in r5c1 is the 7 - not quite so dominant.
>
>But we sort of know that already.
>
>Maybe once we put in selected clues that are unmovable -
>the clue rate will come down and the best clues of the
>unavoidable sets will become more obvious. If we select
>the 1 in r3c2 then I think this will affect the frequencies
>for the whole grid.

OK, I started it. Waiting for another 1e5 sudokus...

...absolutely the same result as before. The 24,25 clue-sudokus are
dominant and with these at least it doesn't matter whether we
fix the 1 in r3c2.

>If this works - perhaps we are just going to replicate Gfroyles
>work - it might be a reliable way to proceed in other grids.
>
Regards, Guenter.