No grids with MCN > 16

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

No grids with MCN > 16

Postby Mathimagics » Tue Jul 23, 2019 6:23 pm

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: 123456789457189236689237145214573698376918452598624371731892564842365917965741823
16: 123456789457189236689237145214573698376918452598624371731892564842765913965341827
16: 123456789457189236689237145214573698376918452598624371731892564845361927962745813
16: 123456789457189236689237145214573698376918452598624371731892564845761923962345817
16: 123456789457189236689237145214573698376918452598624371731892564862345917945761823
16: 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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1264
Joined: 27 May 2015
Location: Canberra

Re: MCN <= 16 (all grids?)

Postby dobrichev » Tue Jul 23, 2019 7:32 pm

Could you describe in details how you "full MCN calculation performed on each"?
dobrichev
2016 Supporter
 
Posts: 1707
Joined: 24 May 2010

Re: MCN <= 16 (all grids?)

Postby Mathimagics » Tue Jul 23, 2019 8:44 pm

Hi Mladen,

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?
User avatar
Mathimagics
2017 Supporter
 
Posts: 1264
Joined: 27 May 2015
Location: Canberra

Re: MCN <= 16 (all grids?)

Postby Mathimagics » Tue Jul 23, 2019 10:35 pm

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!!
User avatar
Mathimagics
2017 Supporter
 
Posts: 1264
Joined: 27 May 2015
Location: Canberra

Re: MCN <= 16 (all grids?)

Postby dobrichev » Wed Jul 24, 2019 6:08 am

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: 1707
Joined: 24 May 2010

Re: MCN <= 16 (all grids?)

Postby Mathimagics » Wed Jul 24, 2019 6:52 am

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 ...
User avatar
Mathimagics
2017 Supporter
 
Posts: 1264
Joined: 27 May 2015
Location: Canberra

Re: MCN <= 16 (all grids?)

Postby Mathimagics » Wed Jul 24, 2019 7:41 pm

Another interesting thing about the grids is that only 187 (of the 222,278 found) have non-trivial automorphisms.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1264
Joined: 27 May 2015
Location: Canberra

Re: No grids with MCN > 16

Postby Mathimagics » Fri Jul 26, 2019 9:37 am

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
(154.74 KiB) Downloaded 7 times

MCN16-Part2-sudz.txt
(248.94 KiB) Downloaded 4 times
User avatar
Mathimagics
2017 Supporter
 
Posts: 1264
Joined: 27 May 2015
Location: Canberra


Return to General