Minimum number of clues

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

Postby Moschopulus » Mon Jan 02, 2006 3:26 pm

coloin wrote:Are there other "such maximal collections" of size 14 in this grid ?


Yes, probably lots of them. You need a max clique program that prints all the max cliques if you want them all.

I did an exhaustive search (using CHECKER) in this grid

439286157176593284258147396381754629795632841624918735542371968867429513913865472

for a 17. There is exactly one 17-puzzle in the grid:

000006050070000200008100000300054000000000801000000700540000060000020000000800000

It took about 36 hours.
Moschopulus
 
Posts: 256
Joined: 16 July 2005

Postby coloin » Wed Jan 04, 2006 4:45 pm

Thanks for that.
Moschopulus wrote:Yes, probably lots of them. You need a max clique program that prints all the max cliques if you want them all.


I can understand that there are many maximal collections.......

There will indeed be "lots" in the "SF" grid
Code: Select all
Unavoid sf grid
Found 287 unavoidable sets (16 of size 4 or 6).
The maximum # of disjoint unavoidable sets (max clique number -- MCN) is 9.

Code: Select all
Unavoid mcn14 grid
Found 239 unavoidable sets (24 of size 4 or 6).
The maximum # of disjoint unavoidable sets (max clique number -- MCN) is 14.


But there will be a much less number of maximal collections in the mcn grid of 14 - and there are less sets to include........

Questions
1 - will there be more than 3^3 and less than 6^6 ?
2 - will there be some sets which are in every maximal collection - if there are this would reduce the total significantly

we know that a valid 17 clue puzzle hits a clue in every unavoidable set in the grid......therefore every one of the sets in a maximal collection have a clue hit in them....but is the reverse the case?

3 - if all the maximal collections in the grid have a hit in every set - does this mean the grid is solved ?
coloin
 
Posts: 2365
Joined: 05 May 2005
Location: Devon

Postby Moschopulus » Thu Jan 05, 2006 2:36 am

coloin wrote:2 - will there be some sets which are in every maximal collection - if there are this would reduce the total significantly

I doubt it very much. Perhaps for some grids. SF has only two unavoidables of size 4 so it's possible they are in every maximal collection, but I would still be doubtful.

we know that a valid 17 clue puzzle hits a clue in every unavoidable set in the grid......therefore every one of the sets in a maximal collection have a clue hit in them....but is the reverse the case?

3 - if all the maximal collections in the grid have a hit in every set - does this mean the grid is solved ?

You're asking if every unavoidable is in some maximal collection. Again I doubt it, there are probably some large ones of size about 30 that are too big to be in a maximal collection.
Moschopulus
 
Posts: 256
Joined: 16 July 2005

Postby coloin » Thu Jan 05, 2006 8:59 am

Thanks
coloin wrote:3 - if all the maximal collections in the grid have a hit in every set - does this mean the grid is solved ?

Yes I think you are right-it cannot be true in every case. But it is true that if they dont have a hit in every set it wont be solved !

However I think that all large unavoidables over 20 clues wont get in a maximal collection - especially not a collection of MCN size 14. [size restriction never mind clue restriction]

Having said that however......the MCN 14 grid would be the grid to analyse these maximal collections. [large MCN, only one 17 clue puzzle]

I think this grid, with such a high MCN, is unusual in that it actually has a 17. It must have a low number of maximal collections.........bear in mind that at least 11 of the clues in each maximal collection must be in a disjointed set.

It is still attractive to postulate that grids which contain a lower than average number of maximal collections are more likely to have 17 or 18 clue puzzles.
coloin
 
Posts: 2365
Joined: 05 May 2005
Location: Devon

Postby coloin » Mon Jan 09, 2006 3:53 pm

Ok ......Regarding this MCN 14 grid
I have looked at the possibility of a lowish number of minimal collections. Yes there are many.......a minimal collection as found with unavoid is
Code: Select all
{16,19,36,39}       
{17,18,87,88}     
{22,23,82,83}               
{27,29,97,99}             
{46,48,56,58}               
{62,63,72,73}               
{75,78,95,98}               
{11,14,31,35,84,85}       
{13,15,25,28,33,38}         
{42,49,52,57,77,79}         
{43,45,53,59,65,69}         
{44,47,51,54,61,67}         
{64,66,81,86,91,94}         
{21,24,32,34,71,76,92,96}   = 72 clues used out of 81


ways to fill in 14 from each set plus 3 others = 4^7*6^5*8*67*66*65 =3^14

Too difficult to intersect this with a few others I fear ! [Unless you pick a maximal set which is maximally different......]

Moving on........Looking at all the unavoidables in this grid :

There are only 70 with 14 clues or less.[using unav27]
5 of the 4sets would appear to be constant in any maximal collection and with a reduced number of 4sets there would be less maximal collections as there would be less room as more bigger sets need to be included. Fitting in the last set of the 14 is difficult !

There has to be a reducing number of maximal collections as there are many examples when the set count is MCN -1 but no examples [by definition] when set count is MCN +1. Unfortunatly I cant even begin to count the number of maximals.

coloin wrote:I think this grid, with such a high MCN, is unusual in that it actually has a 17.


I checked out the number of minimal 18s in this grid - I optimistically thought there might well be zero......but I only found 4 at the 16+2 level.
Code: Select all
...2.6.5..7.........81.....3...54.........8.1......7..54.....6.....2.......8....2
.....6.5..7...3.....81.....3...54.........8.1......7..54.....6.....2.......8....2
.....6.5..7.........81.....3...54........28.1......7..54.....6.....2.......8....2
.....6.5..7....2....81.....3..754.........8.1.........54.....6.....2.......8...7.


Normally in grids with one 17 there are 18s around many of the removed clues - more than 10 usually.

Maybe the grids that Gordon hasnt found with his program are grids with 17s and reduced number of 18s. If this is so there maybe scope for a 16 to be lurking out there which is so obscure that there are no minimal 17s. Unlikely I know.
Last edited by coloin on Mon Jan 09, 2006 1:47 pm, edited 2 times in total.
coloin
 
Posts: 2365
Joined: 05 May 2005
Location: Devon

Postby Moschopulus » Mon Jan 09, 2006 5:24 pm

SF has 29 17s that we know of.

If we remove a clue from 18 of these 29 we get a 16-clue pseudo-puzzle.

What do we get for the other 11?
Moschopulus
 
Posts: 256
Joined: 16 July 2005

16-puzzles with N solutions (from 17s in the SF-grid).

Postby Ocean » Tue Jan 10, 2006 7:22 pm

Moschopulus wrote:SF has 29 17s that we know of.

If we remove a clue from 18 of these 29 we get a 16-clue pseudo-puzzle.

What do we get for the other 11?


Here are those 16-puzzles that give minimum number of solutions, when removing one clue from each of the other eleven:

500000400000710003000020000000004620070000000010000000600002000000030010400000000 P10
500000400000710003000020000000004620070000000010000000600002000000030010400000000 P10
500000400000710003007020000000004600070000000010000000600002000000030010400000000 P218
500000470000710003000020000000004600070000000010000000600002000000030010400000000 P218
500080400000710003000000000000004600070200000010000000600002000000030010400000000 P1462
502000400000710003000000000000004600070000000010000000600042000000030010400000000 P10
502000400000710003000000000000004600070000000010000000600042000000030010400000000 P10
502000400000710003000020000000004600070000000010000000600002000000030010400000000 P10
502000400000710003000020000000004600070000000010000000600002000000030010400000000 P10
502000400000710003000400000000004600070000000010000000600002000000030010400000000 P10
502000400000710003000400000000004600070000000010000000600002000000030010400000000 P10

Actually, there are only 7 different (the pairs 1-2, 6-7, 8-9, 10-11 are identical).
Ocean
 
Posts: 442
Joined: 29 August 2005

Postby Moschopulus » Tue Feb 21, 2006 1:02 pm

Here is a word on how CHECKER could be speeded up, in case anyone is interested and has any ideas.

Recall how checker works:

1. Find some unavoidable sets,
2. Enumerate all hitting sets of size n, i.e., enumerate all sets of n clues that intersect all the unavoidable sets found in part 1,
3. Check if any of these hitting sets uniquely determines the grid.

In step 2 some hitting sets are enumerated twice. This means that checker could be speeded up if we can eliminate this duplication, but we could not see how to do this.

--------------

Let me explain. The cells are numbered 11 to 99, ij means row i, column j.

For an example, suppose we are looking for a 16 clue puzzle.

In step 2, checker finds a max clique (a maximal set of pairwise disjoint unavoidables). Let's suppose a max clique here has 12 sets. Checker orders the 12 sets, chooses one clue from each of these 12 unavoidables, and adds 4 further clues, in all possible ways, and then sees if the result is a hitting set for all unavoidables found in step 1. If yes, go to step 3.

So checker generates all possible 16-tuples in a systematic way. It only became apparent to us later that some 16-tuples are generated twice, as follows.

Suppose that from step 1 we have unavoidable sets {12,13,42,43} and {41,42,71,72}. Suppose also that the first of these sets is not part of the max clique checker uses, but the second set is. And suppose that no other unavoidable in the max clique contains any of 12,13,42,43.

Checker will choose each of 41,42,71,72 when forming possible hitting sets, as one of the 12 clues. In that order.

(I know there are lots of other clues hanging around, but lets just stick to these cells for this example)

First, when choosing 41, each of 12, 13, 42, 43, could (and must) be chosen as one of the final 4 clues.

Second, when choosing 42, the first unavoidable is already hit, so when choosing the final 4 clues, each of 12, 13, 43, 41, 71, 72 could be chosen as one of the final 4 clues. Actually 41 is not chosen since {41,42} arose in the previous step. Anyway, the point is that in particular, {42,71} is chosen.

Third, when choosing 71, each of 12, 13, 42, 43, could (and must) be chosen as one of the final 4 clues. Again {71,42} will be chosen.

And so, the problem is that {42,71} arises twice with this method. To eliminate all such duplication might speed checker up by a considerable factor, but we cannot see how to do this in a simple way. The duplication of {41,42} is easy enough to take into account, but this type of duplication is more difficult.

We would be very grateful to receive any ideas on how to get around this.
Moschopulus
 
Posts: 256
Joined: 16 July 2005

Postby Ocean » Tue Feb 21, 2006 8:26 pm

Moschopulus wrote:Second, when choosing 42, the first unavoidable is already hit, so when choosing the final 4 clues, each of 12, 13, 43, 41, 71, 72 could be chosen as one of the final 4 clues. Actually 41 is not chosen since {41,42} arose in the previous step. Anyway, the point is that in particular, {42,71} is chosen.


Here is a simple suggestion... :

I think that - instead of picking the {42,71} pair (when the first unavoidable is already hit), it is safe to drop this choice immediately. Any possible choice (of pairings with 42) either occured before or will occur later - so it will be a duplicate. Skip the 42, and move on to 71. (Of course, the pair {71,42} can then not be dropped by a similar argument...)
Ocean
 
Posts: 442
Joined: 29 August 2005

Postby Moschopulus » Wed Feb 22, 2006 3:51 pm

Ocean wrote:I think that - instead of picking the {42,71} pair (when the first unavoidable is already hit), it is safe to drop this choice immediately. Any possible choice (of pairings with 42) either occured before or will occur later - so it will be a duplicate. Skip the 42, and move on to 71. (Of course, the pair {71,42} can then not be dropped by a similar argument...)


Thanks for your suggestion. It seems like that would work. It's hard to say if the result will be faster overall without trying it. We will experiment when we have time.

Also I have noted your suggestions elsewhere:
Ocean wrote:Without knowing the inner part of checker, here are two different suggestions - not necessarily trivial - 1. Is it possible to select some specific orders of which puzzles are tested, in such ways that early hits are more likely? .... 2. Is it possible to 'check out' large groups of puzzles (instead of testing each one, but still guaranteeing there is no hit in that group)?


These are interesting, and I would like to pursue the random searching aspect, but again, time is short.
Moschopulus
 
Posts: 256
Joined: 16 July 2005

Sudoku DG

Postby Moschopulus » Thu Feb 23, 2006 10:53 pm

I just made a post about the minimum number of clues in sudoku disjoint groups over on the "Sudoku Variants" forum.

That seems like the right place, and besides, this thread is too long.
Moschopulus
 
Posts: 256
Joined: 16 July 2005

Postby sg » Thu Mar 02, 2006 2:04 pm

I posted elsewhere some results of an enumeration in the 2X2 toy model, which you might find interesting since it has some relevance to this thread.
sg
 
Posts: 22
Joined: 14 February 2006

Previous

Return to General