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: 1481
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: 1777
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: 1481
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: 1481
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: 1777
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: 1481
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: 1481
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 27 times

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

Re: No grids with MCN > 16

Postby dobrichev » Mon Nov 04, 2019 12:36 pm

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


Return to General