## No grids with MCN > 16

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

### No grids with MCN > 16

I have run a scan of the ED grid catalog with a view to establishing whether any have MCN > 16 and found none. If the methodology outlined below holds water, and my coding is ok (hmmm ... always a worry!), this result is definitive.

I did find 222,278 grids with MCN = 16 (and there are probably more, see below for more details).

Here are a few from band 32, if someone could confirm these I'd be grateful:

Code: Select all
`16: 12345678945718923668923714521457369837691845259862437173189256484236591796574182316: 12345678945718923668923714521457369837691845259862437173189256484276591396534182716: 12345678945718923668923714521457369837691845259862437173189256484536192796274581316: 12345678945718923668923714521457369837691845259862437173189256484576192396234581716: 12345678945718923668923714521457369837691845259862437173189256486234591794576182316: 123456789457189236689237145214573698376918452598624371731892564862745913945361827`

The methodology was basically this:

• for each grid compute MCN4 = max clique size using only UA4's
• if an MCN = 17 exists, it would need MCN4 > 10, since 10 UA4's + 7 UA6's can't be mutually disjoint. Further, an initial scan that calculated just MCN4 was done, and this revealed that there is no grid with MCN4 > 13. So the feasible combinations for the hypothetical MCN=17 are limited to (11+6), (12+5), (13+4)
• the grids with MCN4 > 10 were then checked (see table below for the grid counts involved), and a full MCN calculation performed on each, and this found that 222,278 of those grids had MCN = 16, but none had MCN = 17

The ED grid counts by MCN4:
Code: Select all
`      11          31,610,628      12           2,044,701      13              18,432      ----------------------                  33,673,761`

Now perhaps somebody has already done this (!), but I haven't actually come across a definitive statement about the impossibility of an MCN = 17 grid.

And how complete is my MCN=16 grid count? Well, obviously I need to look at the much larger pools of grids with MCN4 = 8, 9, and 10 (the only applicable cases) to do that, and that is my next task. I will do some sampling meanwhile to get an estimate of how many there might be.

Cheers
MM
Last edited by Mathimagics on Fri Jul 26, 2019 9:04 am, edited 1 time in total.

Mathimagics
2017 Supporter

Posts: 1481
Joined: 27 May 2015
Location: Canberra

### Re: MCN <= 16 (all grids?)

Could you describe in details how you "full MCN calculation performed on each"?
dobrichev
2016 Supporter

Posts: 1777
Joined: 24 May 2010

### Re: MCN <= 16 (all grids?)

The MCN calculation is done with a conventional "find maximum clique" algorithm for graphs - here the graph has a vertex for each UA (UA4's only for MCN4 calculation, UA4's + UA6's for "full" MCN) and an edge for every pair of UA's that are disjoint.

The search tree is aggressively "pruned" - we add a UA to the search chain only if it doesn't result in the total size of the UA's exceeding 81 cells.

I find UA4's by pattern checking, but for UA6's I use the grids "symbol cycle" structure (just like Pittenger's RLS generator). This produces the same UA6 sets as GridChecker.

I use bm128's for UA6 sets as that makes building the "disjoint table" quicker.

Have I left anything out?

Mathimagics
2017 Supporter

Posts: 1481
Joined: 27 May 2015
Location: Canberra

### Re: MCN <= 16 (all grids?)

And how complete is my MCN=16 grid count? Well, obviously I need to look at the much larger pools of grids with MCN4 = 8, 9, and 10 (the only applicable cases) to do that, and that is my next task. I will do some sampling meanwhile to get an estimate of how many there might be.

Sampling some millions of candidates couldn't find anything at all, so I checked the grids with MCN4 = 11, 12, 13 and counted how many MCN=16 grids came from each (I should have done that before!):

Code: Select all
`            MCN=16 Grid     MCN4   Candidates    MCN=16 found     ---------------------------------       8            9           10           11    31,610,628             0  !!      12     2,044,701       219,974      13        18,432         2,304      ------------------------------            33,673,761       222,278            `

Since not a single grid with MCN4 = 11 turned out to be MCN = 16, I think that the count is final!!

Mathimagics
2017 Supporter

Posts: 1481
Joined: 27 May 2015
Location: Canberra

### Re: MCN <= 16 (all grids?)

Mathimagics wrote:UA4's only for MCN4 calculation, UA4's + UA6's for "full" MCN

Not entirely full because, for example, 13*4 + 10 + 10 + 9 = 81.
dobrichev
2016 Supporter

Posts: 1777
Joined: 24 May 2010

### Re: MCN <= 16 (all grids?)

Yes, that's certainly feasible (however improbable).

The MCN4 = 12 and MCN4 = 13 grids should both be checked for cases like that before the MCN = 16 count can be considered final. I will do that ...

Mathimagics
2017 Supporter

Posts: 1481
Joined: 27 May 2015
Location: Canberra

### Re: MCN <= 16 (all grids?)

Another interesting thing about the grids is that only 187 (of the 222,278 found) have non-trivial automorphisms.

Mathimagics
2017 Supporter

Posts: 1481
Joined: 27 May 2015
Location: Canberra

### Re: No grids with MCN > 16

only 187 (of the 222,278 found) have non-trivial automorphisms.

blue fortunately looked there too, and he found 14 more than that. That led to the identification of a tiny misprint in my MCN16 code, a loop control clause that had "<" where it should have been a "<=". (Thanks!)

I have rerun the job, looking again at each grid with MCN4 = 11, 12, and 13, and have found 109 new cases all up, so the MCN=16 count is now 222,396. Note that, as before, we have NOT yet considered using UA's > 6 when calculating the MCN.

The MCN=16 grids, when SUDZ compressed, fit into two small files:

MCN16-Part1-sudz.txt

MCN16-Part2-sudz.txt

Mathimagics
2017 Supporter

Posts: 1481
Joined: 27 May 2015
Location: Canberra

### Re: No grids with MCN > 16

It would be interesting to see MCN at pencilmark level.

Replacing given/non-given by forbidden/non-forbidden value for a cell the space increases 8 times (from 81 to 648 bits since we are interested only in the UA value permutation not matching the examined solution).
This disjoins UA sharing same cell with different value.
dobrichev
2016 Supporter

Posts: 1777
Joined: 24 May 2010