The New Sudoku Players' Forum

[Moschopulus]

Some stats on the MCN.

MCN= max clique number = number of unavoidables in a maximal set of pairwise disjoint unavoidables

I took 13919 grids which have a 17 (from gfroyles list), and I took 13919 grids chosen completely at random (using dukuso's program).

Here are the MCNs.(*)

[MCN, number of grids that have a 17, number of random grids]

[4, 0, 0],
[5, 0, 0],
[6, 15, 0],
[7, 130, 2],
[8, 1146, 194],
[9, 3879, 1442],
[10, 5254, 4217],
[11, 2753, 4828],
[12, 672, 2451],
[13, 69, 690],
[14, 1, 88],
[15, 0, 7],
[16, 0, 0]

mean [9.83,10.74]
variance [1.12,1.22]

blue=random grids, red=grids with 17



(*) Actual MCNs may vary. These MCNs are calculated from a selection of unavoidable sets, not from *all* unavoidable sets. However the selection is chosen in the same way each time. It consists of all unavoidables of sizes 4 and 6, and a few others of a certain type.

[edit, added: The mean MCN of the known grids with more than 4 17s is 9.55.]

[DanO]

This is the kind of unavoidable set that will sneak up and bite you just when you thought you had everything locked down. You move things around to cover 1 and another pops up somewhere else

Code: Select all

+-------+-------+-------+
| . . 6 | . . . | . 9 . |
| 4 . 9 | . . . | . 3 . |
| 3 . 7 | . . . | . 6 . |
+-------+-------+-------+
| . . 4 | 7 . . | . . . |
| 7 . . | . . . | . 4 . |
| . . . | 4 . . | . 7 . |
+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+


[Moschopulus]

Could someone please post the grid that wolfgang calls NU23, dukuso calls sfb. I can't find it, only references to it.

What is the grid most likely to contain a 16 ? Is it this one?

Obviously this is a matter of opinion. Is it the grid with the highest number of 17s next to SF?

[dukuso]

Could someone please post the grid that wolfgang calls NU23, dukuso calls sfb. I can't find it, only references to it.

What is the grid most likely to contain a 16 ? Is it this one?

Obviously this is a matter of opinion. Is it the grid with the highest number of 17s next to SF?

sfb:
.......1..2..5.....4.......8..1.9.........2.....3......6..7.5.23.....4..1...8....

it's the only grid with a proven 17 and no 2-unavoidables


not the highest number of 17s, only 3 17s.
Some have 20 or such. If you need them, I can search

[gfroyle]

From analysis of my list of 17s, these are the top 5 most fertile complete grids (in the sense of containing multiple different 17s).

Code: Select all

639241785284765193517983624123857946796432851458619237342178569861594372975326418
873692451649517328521348976132976845498125637765483192954761283386254719217839564
438926751796451382251738469123687945647593218589214673362175894914862537875349126
236195478487263159591487632123759864759648321648321795314972586872516943965834217
481972365296534178537168942123697584658241793749385216314726859965813427872459631


The number of 17s (that I know of) in these grids is 29, 20, 14, 12 and 11 respectively.

I find it interesting that SF (with 29 x 17s) is so far ahead of the pack...

Cheers

Gordon

[kjellfp]

it's the only grid with a proven 17 and no 2-unavoidables

I thought that a k-unavoidable was an unavoidable with exactly k different symbols.

Well, given two different symbols, isn't the set of all cells in the grid with these symbols a 2-unavoidable? And either this set or some subset will be a minimal 2-unavoidable.

So there are at least 36 2-unavoidables in any grid (36 ways to pick the two symbols).

Or do I misunderstand something...

[coloin]

Ive been looking at dukosos "sfb" recently too !

This is the backbone

Code: Select all

+---+---+---+
|...|...|.1.|
|.2.|.5.|...|
|...|...|...|
+---+---+---+
|...|1..|...|
|...|...|2..|
|...|...|...|
+---+---+---+
|...|.7.|5.2|
|...|...|4..|
|1..|...|...|
+---+---+---+


These 10 clues give 7 more clues [not 6 ]

Code: Select all

 
+---+---+---+
|...|...|.1.|
|.21|.5.|...|
|...|.1.|.2.|
+---+---+---+
|...|1..|...|
|.1.|...|2..|
|...|...|1..|
+---+---+---+
|...|.71|5.2|
|...|...|4.1|
|1..|...|...|
+---+---+---+


Interestingly it has no two clue unavoidables of size 4 or 6.

Can you see why this is so ?

The pairs are kept on separate rows - where possible - therefore there are no small unavoidables !

This is achieved in a large proportion of the grid by ensuring that the clues in a minicolumn are distributed over different columns in the adjacent box. This happens with all the columns of B3B6B9.

Code: Select all

+---+---+---+
|589|732|614|
|621|854|379|
|743|916|825|
+---+---+---+
|835|129|746|
|417|568|293|
|296|347|158|
+---+---+---+
|968|471|532|
|372|695|481|
|154|283|967|
+---+---+---+


Maybe there are other starting "backbones" which give 17s in this grid ?

[Moschopulus]

Thanks guys.

MCN's of Gordon's Top 5 are 8, 12, 11, 11, 10.
The first one is SF.
I will run through the second one with MCN = 12 over the weekend.

The MCN of the sfb grid is 8.

I thought that a k-unavoidable was an unavoidable with exactly k different symbols.

Well, given two different symbols, isn't the set of all cells in the grid with these symbols a 2-unavoidable? And either this set or some subset will be a minimal 2-unavoidable.

Yes, you are correct. I think dukuso means that all 36 of these 2-unavoidable sets are minimal, and he doesn't count them.

[dukuso]

yes, "proper" or "non-trivial" 2-unavoidables , so to say.

[coloin]

Unavoidables, clue generation and minimum number of solutions.

A new clue is generated when it cant be in an unavoidable set which isnt already covered by definite clues. This is done by "covering " the 8 other spaces which would be in the same unavoidable set as this clue. This is the common pattern of 3 clues in a box in many of Gfroyles 17s.

Code: Select all

+---+---+---+
|...|24.|7..|
|.8.|...|.9.|
|.1.|...|...|
+---+---+---+
|...|8..|..6|
|7..|...|...|
|4..|...|2..|
+---+---+---+
|3..|.7.|...|
|...|...|..2|
|...|..6|.18|
+---+---+---+


The 7 is insereted in r8c8 - the 2,1& 8 in box 9 would be in the set. The other unknown clues in box 9 cant make an unavoidable set with the 7 in box 9 because of the 7s in c7 and r7 preclude it.
This is a good way ---- but not nessesarily the best way to achieve clue separation and therefore maximum set coverage.

What we need is 16 of the most "diverse" clues in set coverage - not nessessarily clue generators. Of course if ALL the sets are covered all the other superfluos clues will be inserted on insertion of the final [16th ?]clue. Perhaps this means using all nine clues in all the boxes..... and perhaps a maximum of 2 of any particular clue number.

In any completable [minimal] puzzle ALL the sets are covered by all of the clues.
The 17 numbers cover All the sets and then it is solved uniquely.
If there are 17 disjointed sets then it cant be done in 16 clues.

The Sf apparently cant be done in 16 - therefore there must exist extra set[s] which cant be covered by any combination of 16 clues.

Sets have to be at least 4 clues in them. Next size up is 6 clues.

The most [completely] disjointed sets a grid can have is 20 - this is very unlikely to happen.[You need 20 different 4 sets of numbers][4*20=80]

Does this mean that all sudoku grids can be reduced to at least 20 clues - or 19 ?

15 different 4s and 3 different 6s give 18 sets possible - this cant be done in 17 clues.

With 18 and 19 clues the chances of hitting all the sets are much improved - so much so that I think all grids can be done in 19 - apart from the grid which has 20 - which I believe wont happen !


with no 4 set unavoidables the maximum sets possible will be 13 [78] [This is the SFB]

Only 2 4s in the grid means that there can only be 12 6s give a total of 14 completly disjointed sets possible. [80][this is the SF - EDIT which actually has only 9]. Gfroyle did allude to this months ago.

With 5 "4 set" unavoidables the maximum disjointed sets possible are 15.

This would explain the wide range of MCN in all the 17s. If you cover all the sets then it is solved.
Of course you are more likely to cover them all if you have less to cover as in the SF and the SFB [perhaps].

With 11 "4 set" the maximum number of sets is 17 [80] [This is Mosch's grid - which actually has 14.] I think someone got many 19s in this grid - which surprised many.

I have a new method which attempts to separate the clues to try for more efficient clue coverage [if it is possible] of all the unavoidable sets....await results ! If I get a new 17 then there will be mileage in this method.

[Moschopulus]

In any completable [minimal] puzzle ALL the sets are covered by all of the clues.
The 17 numbers cover All the sets and then it is solved uniquely.
If there are 17 disjointed sets then it cant be done in 16 clues.

I doubt very much if any grid has MCN = 17.

The Sf apparently cant be done in 16 - therefore there must exist 17 disjointed sets.

No, SF has MCN = 8.

[Moschopulus]

Number 2 in the top 5 does not have a 16.

Number 2 has MCN = 12.
I ran the program over the weekend and it searched the grid exhaustively in about 40 hours.
The running time is inversely proportional to the MCN.

[DanO]

This grid has come up a number of times in this thread and generally been stated to require a minimum of 18 clues.

Code: Select all

+-------+-------+-------+
| 1 2 3 | 4 5 6 | 7 8 9 |
| 4 5 6 | 7 8 9 | 1 2 3 |
| 7 8 9 | 1 2 3 | 4 5 6 |
+-------+-------+-------+
| 2 3 1 | 5 6 4 | 8 9 7 |
| 5 6 4 | 8 9 7 | 2 3 1 |
| 8 9 7 | 2 3 1 | 5 6 4 |
+-------+-------+-------+
| 3 1 2 | 6 4 5 | 9 7 8 |
| 6 4 5 | 9 7 8 | 3 1 2 |
| 9 7 8 | 3 1 2 | 6 4 5 |
+-------+-------+-------+

It in fact requires a minimum of 27 clues as I will demonstrate.

This subgrid is 1 of 9 disjoint sets in the above grid.

Code: Select all

+-------+-------+-------+
| 1 . . | 2 . . | 3 . . |
| 2 . . | 3 . . | 1 . . |
| 3 . . | 1 . . | 2 . . |
+-------+-------+-------+

And has the following unavoidable sets

Code: Select all

+-------+-------+-------+
|>1<. . | 2 . . | . . . | A
| 2 . . | . . . | 1 . . |
| . . . | 1 . . | 2 . . |
+-------+-------+-------+
+-------+-------+-------+
| 1 . . | . . . | 3 . . | Bx
| 2 . . | 3 . . | . . . |
| . . . | 1 . . | 2 . . |
+-------+-------+-------+
+-------+-------+-------+
| 1 . . | 2 . . | 3 . . | C
| 2 . . | 3 . . | 1 . . |
| . . . | . . . | . . . |
+-------+-------+-------+
+-------+-------+-------+
| 1 . . | 2 . . | 3 . . | D
| . . . | . . . | . . . |
| 3 . . | 1 . . | 2 . . |
+-------+-------+-------+
+-------+-------+-------+
| 1 . . | . . . | 3 . . | E
| . . . | 3 . . | 1 . . |
| 3 . . | 1 . . | . . . |
+-------+-------+-------+
+-------+-------+-------+
| 1 . . | 2 . . | . . . | Fx
| . . . | 3 . . | 1 . . |
| 3 . . | . . . | 2 . . |
+-------+-------+-------+
+-------+-------+-------+
| 1 . . | 2 . . | . . . | G
| 2 . . | 3 . . | . . . |
| 3 . . | 1 . . | . . . |
+-------+-------+-------+
+-------+-------+-------+
| 1 . . | . . . | 3 . . | H
| 2 . . | . . . | 1 . . |
| 3 . . | . . . | 2 . . |
+-------+-------+-------+

+-------+-------+-------+
| . . . | 2 . . | 3 . . | Ix
| 2 . . | . . . | 1 . . |
| 3 . . | 1 . . | . . . |
+-------+-------+-------+
+-------+-------+-------+
| . . . | . . . | . . . | J
| 2 . . | 3 . . | 1 . . |
| 3 . . | 1 . . | 2 . . |
+-------+-------+-------+
+-------+-------+-------+
| . . . | 2 . . | 3 . . | K
| 2 . . | 3 . . | . . . |
| 3 . . | . . . | 2 . . |
+-------+-------+-------+
+-------+-------+-------+
| . . . | 2 . . | 3 . . | L
| . . . | 3 . . | 1 . . |
| . . . | 1 . . | 2 . . |
+-------+-------+-------+

A through H are all covered by the selection of R1C1 (or equivalently, any cell of the sub-grid. It can be seen by inspection that no single cell covers all of the remaining unavoidable sets I through L.

Therefore, each of the 9 subgrids will require 3 clues for a total of 27 in the full grid.

Here is a 30 clue Sudoku for the above grid.

Code: Select all

+-------+-------+-------+
| 1 2 . | . . 6 | . 8 . |
| . 5 . | 7 . . | . . 3 |
| . . 9 | . 2 . | 4 . . |
+-------+-------+-------+
| . 3 . | 5 . . | . . 7 |
| . . 4 | . 9 . | 2 . . |
| 8 . . | . . 1 | . 6 . |
+-------+-------+-------+
| . . 2 | . 4 . | 9 . . |
| 6 . . | . . 8 | 3 1 . |
| . 7 8 | 3 . . | . . 5 |
+-------+-------+-------+

[Edit - Sets B, F and I (marked with x) are invalid unavoidable sets so R2C4=3 or R3C7=2 each cover the remaining sets]

[coloin]

I doubt very much if any grid has MCN = 17.

you may well be right - I was theorizing on the limits of what was potentially possible - as a proof

The Sf apparently cant be done in 16 - therefore there must exist 17 disjointed sets.

No, SF has MCN = 9.

yes you are right again...what I meant was that there must always be a set or sets which cant be covered by the 16 clues - no matter what combination of clues. This set[s] will be disjointed wrt the 16 clues. [I will edit.]

BTW the M in MCN refers to maximum......but you say this isnt quite so ?

I hadnt got round to looking at the number 2 grid ] [with 20 17s] It doesnt look good for a 16 in Gfroyles girds. Hope rests with the SFb at present.

[kjellfp]

Therefore, each of the 9 subgrids will require 3 clues for a total of 27 in the full grid.

Sorry, but F (as well as some others) is not unavoidable.

You need two clues for these 9-cells unavoidables. The clues must be of different symbols, on different rows, and different columns. Like 1 in r1c1 and 3 in r2c4. But your method can be used to prove that no 17 exists for this grid.

I think there is a 19 and no 18 (off the top of my head, could be wrong).