## SudokuP: 12-clue Puzzle Search

For fans of Killer Sudoku, Samurai Sudoku and other variants

### Re: SudokuP: 12-clue Puzzle Search

Hi, blue!
blue wrote: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
Serg
2018 Supporter

Posts: 651
Joined: 01 June 2010
Location: Russia

### Re: SudokuP: 12-clue Puzzle Search

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.
blue

Posts: 854
Joined: 11 March 2013

### Re: SudokuP: 12-clue Puzzle Search

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 histogramMinClues 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
Serg
2018 Supporter

Posts: 651
Joined: 01 June 2010
Location: Russia

### Re: SudokuP: 12-clue Puzzle Search

Hi Serg,

Thanks.
The numbers all match.
blue

Posts: 854
Joined: 11 March 2013

### Re: SudokuP: 12-clue Puzzle Search

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 gridsMCB   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
2018 Supporter

Posts: 651
Joined: 01 June 2010
Location: Russia

### Re: SudokuP: 12-clue Puzzle Search

Hi, blue!
Code: Select all
`Processed 200000 randomly generated SudokuP gridsMCB 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
Serg
2018 Supporter

Posts: 651
Joined: 01 June 2010
Location: Russia

### Re: SudokuP: 12-clue Puzzle Search

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.
blue

Posts: 854
Joined: 11 March 2013

### Re: SudokuP: 12-clue Puzzle Search

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 gridsMCB    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
Serg
2018 Supporter

Posts: 651
Joined: 01 June 2010
Location: Russia

### Re: SudokuP: 12-clue Puzzle Search

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?

Mathimagics
2017 Supporter

Posts: 1284
Joined: 27 May 2015
Location: Canberra

### Re: SudokuP: 12-clue Puzzle Search

Hi, Mathimagics!
Mathimagics wrote:Well done!

Thanks.

Mathimagics wrote: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
Serg
2018 Supporter

Posts: 651
Joined: 01 June 2010
Location: Russia

### Re: SudokuP: 12-clue Puzzle Search

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

Mathimagics
2017 Supporter

Posts: 1284
Joined: 27 May 2015
Location: Canberra

### Re: SudokuP: 12-clue Puzzle Search

Hi, Mathimagics!
Mathimagics wrote: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
Serg
2018 Supporter

Posts: 651
Joined: 01 June 2010
Location: Russia

### Re: SudokuP: 12-clue Puzzle Search

Serg wrote: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 ..

Mathimagics
2017 Supporter

Posts: 1284
Joined: 27 May 2015
Location: Canberra

### Re: SudokuP: 12-clue Puzzle Search

Serg wrote: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,
blue

Posts: 854
Joined: 11 March 2013

### SudokuP: 12-clue Puzzle Search

.
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

Mathimagics
2017 Supporter

Posts: 1284
Joined: 27 May 2015
Location: Canberra

PreviousNext