The New Sudoku Players' Forum

[Mathimagics]

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

[dobrichev]

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

[Mathimagics]

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?

[Mathimagics]

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!!

[dobrichev]

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.

[Mathimagics]

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]

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

[Mathimagics]

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:

[ deleted attachment ] MCN16-Part1-sudz.txt
[ deleted attachment ] MCN16-Part2-sudz.txt

[dobrichev]

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.