The New Sudoku Players' Forum

[Moschopulus]

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.

[coloin]

Thanks for that.

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 ?

[Moschopulus]

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.

[coloin]

Thanks

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]

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.

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.

[Moschopulus]

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?

[Ocean]

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).

[Moschopulus]

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.

[Ocean]

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...)

[Moschopulus]

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:

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]

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.

[sg]

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.