The New Sudoku Players' Forum

[Serg]

Hi, blue!

Maybe Serg, having code that's completely independent from mine, can verify that the MinClues by band, and grid counts by MCB number, are correct?

I am standing away from this discussion. I tried to understand now key concepts ("MinClues by band", "MCB number"), but I wasn't managed to do it. In any way, I have no ready code for SudokuP grid checking.

Serg

[blue]

Hi Serg,

Thanks for considering it.

Mladen defined 'MinClues' for a (canonical) band, in terms of UA sets, and the size of the smallest set of cells that includes at least one cell from each UA set.

The number that's defined that way, would be the same, no matter how you transformed the band -- the UA sets would change, but the size of the smallest set, would remain constant.

An alternate way to define it, for a band that's part of a complete grid, is like this:

1. Make a 54-clue puzzle, by clearing all of the cells in the band.
2. Loop over clue counts ... N=0, N=1, etc.
3. For each N, loop over all combinations of N clues from the original band.
4. Stop as soon as you find a 54+N clue puzzle with a unique solution -- the original grid.
   The N value, at that point, is the 'MinClues' number for the band.

If you did that for all 3 bands in a grid, and added the results, you would have one candidate of 4, for the grid's MCB number.
Doing the similar thing for the 3 stacks, 3 p-bands, and 3 p-stacks, would give the other 3 candidates.
The grid's MCB number, then, is defined to be the largest of the 4 candidates.
It is invariant with respect to grid transformations.

Using that method, would take an eternity for the full catalog of grids, so it would be better to approach the problem using select grid transformations, a band canonicalization routine, and a MinClues lookup table ... a "map", really ... mapping canonical bands to MinClues values.

My calculations for the catalog of standard sudoku grids, are running now.
With luck, the results will show similar anomalies, and any worries will be put to rest.

Update: Bad news ... for me, I guess ... no such luck.

Thanks Again,
Blue.

[Serg]

Hi, blue!
Thank you for clarification!
I've done intermediate calculations - analyzed all 6585 ED SudokuP bands and got such MinClues distribution:

Code: Select all

MinClues by bands histogram

MinClues Bands
       0  2617
       1  2561
       2  1014
       3   363
       4    26
       5     2
       6     2

It would be nice to compare these numbers with yours.

Serg

[blue]

Hi Serg,

Thanks.
The numbers all match.

[Serg]

Hi, blue!
I've developed a program for MCB number calculation and run it on a sample of 205106 SudokuP ED grids (I don't store full list of SudokuP ED grids on my computer because of its huge size). I need about 10 hours to generate all 53 millions SudokuP ED grids. So, I'll have full grids list tomorrow, and I'll prepare full statistics. But partial (205106 SudokuP ED grids) statistics is also interesting. Here it is.

Code: Select all

Processed 205106 SudokuP grids

MCB   Bands
  0      31
  1     321
  2    1975
  3    7076
  4   14044
  5   17604
  6   19814
  7   22019
  8   23821
  9   21306
 10   22574
 11   11690
 12   16683
 13     280
 14   14671
 15      20
 16       1
 17       0
 18   11176

Not only 18-clue MCB peak is observed, but 14-clue and 12-clue peaks are visible.
I think to try use randomly generated grids, because ED grids are not random - they contain much more automorphic grids than randomly generated grids.

Serg

[Serg]

Hi, blue!

Code: Select all

Processed 200000 randomly generated SudokuP grids

MCB Bands
  0        0
  1        0
  2        9
  3      258
  4     2046
  5     8090
  6    20256
  7    32448
  8    39489
  9    33636
 10    30802
 11     6965
 12    15776
 13     1673
 14     5010
 15      286
 16       37
 17        0
 18     3219

18-clue MCB peak is observed, 14-clue and 12-clue peaks are visible too.

Serg

[blue]

Hi Serg,

Thanks for doing what you're doing.
It seems that the oddities are "real", and not a bug.

18-clue MCB peak is observed, 14-clue and 12-clue peaks are visible too.

If you look at a graph of "log(grid count)" for MCB=0,..16 (for my counts for full grid list, anyway), you can see a smaller peak at MCB=10, too !

(I haven't tried that for your "200000 grids" numbers, but I assume it's there too).

Cheers,
Blue.

[Serg]

Hi, blue!
I've done MCB number calculation for 53666689 ED SudokuP grids and got absolutely the same numbers as you. (Calculation took me 9 hours (alone notebook CPU core used).)

Code: Select all

Processed 53666689 SudokuP grids

MCB    Bands
  0      404
  1     8460
  2    80749
  3   465992
  4  1729441
  5  4263856
  6  7781962
  7 10245574
  8 10402287
  9  7907126
 10  6050227
 11  1248900
 12  2339518
 13   249346
 14   584224
 15    32255
 16     5926
 17        0
 18   270442

Serg

[Mathimagics]

Hi Serg!

Well done!

Can you make that data available? It would be useful to reproduce blue's table above for the 57,000 12-clue grids we have found so far.

53.67MB of data with only 20 different byte values should compress to very small file, I would think.

If you didn't save the data, could I have a copy of your program?

[Serg]

Hi, Mathimagics!

Well done!

Thanks.

Can you make that data available? It would be useful to reproduce blue's table above for the 57,000 12-clue grids we have found so far.

53.67MB of data with only 20 different byte values should compress to very small file, I would think.

If you didn't save the data, could I have a copy of your program?

What data do you mean?

Serg

[Mathimagics]

.
I would like to get the MCB value for each of the 53,666,689 grids. I'm assuming your grid catalog is in lex order, so would match mine.

[Serg]

Hi, Mathimagics!

I would like to get the MCB value for each of the 53,666,689 grids. I'm assuming your grid catalog is in lex order, so would match mine.

Unfortunately, my grid catalog isn't in lex order. I used rather complicated metric - minlex form for 9-digit template for "1" digit ("11 SudokuP grid equivalence classes), then minlex form for 9-digit template for "2" digit, etc.

I don't mind against sharing my code, but in this case one can hardly understand my code, because it was composed mainly from appropriate code pieces from my other programs. It would be faster if you will send me a list of SudokuP grids to process - I'll process it and send you result.

Serg

[Mathimagics]

It would be faster if you will send me a list of SudokuP grids to process - I'll process it and send you result.

Ok, thanks, that'll work. Send me a PM with an email address ..

[blue]

Hi, blue!
I've done MCB number calculation for 53666689 ED SudokuP grids and got absolutely the same numbers as you. (Calculation took me 9 hours (alone notebook CPU core used).)

Nice job Serg ! ... and much appreciated

Thanks again,
Blue,

[Mathimagics]

.
Thanks to Serg, we can now give our version of blue's table above for the 12C grids that we have found so far:

Code: Select all

 MCB |    grids |  12CG | 12CG/grids
-----+----------+-------+-----------
  0  |      404 |   388 |   96.0396%
  1  |     8460 |  5453 |   64.4563%
  2  |    80749 | 18262 |   22.6158%
  3  |   465992 | 19955 |    4.2823%
  4  |  1729441 |  9999 |    0.5782%
  5  |  4263856 |  2779 |    0.0652%
  6  |  7781962 |   467 |    0.0037%
  7  | 10245574 |    35 |    0.0004%
  8  | 10402287 |     2 |           
  9  |  7907126 |     0 |           
 10  |  6050227 |     0 |           
 11  |  1248900 |     0 |           
 12  |  2339518 |     0 |           
 13  |   249346 |     0 |           
 14  |   584224 |     0 |           
 15  |    32255 |     0 |           
 16  |     5926 |     0 |           
 17  |        0 |     0 |           
 18  |   270442 |     0 |           
-----+----------+-------+-----------
     | 53666689 | 57340 |    0.1068%


[ EDIT ] Regarding the MCB = 18 "anomaly", not sure if it's relevant, but the MC grid has MCB = 18