SudokuP: 12-clue Puzzle Search

For fans of Killer Sudoku, Samurai Sudoku and other variants

Re: SudokuP: 12-clue Puzzle Search

Postby Serg » Thu Jul 19, 2018 7:41 pm

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: 607
Joined: 01 June 2010
Location: Russia

Re: SudokuP: 12-clue Puzzle Search

Postby blue » Thu Jul 19, 2018 9:06 pm

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: 708
Joined: 11 March 2013

Re: SudokuP: 12-clue Puzzle Search

Postby Serg » Fri Jul 20, 2018 10:13 pm

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
Serg
2018 Supporter
 
Posts: 607
Joined: 01 June 2010
Location: Russia

Re: SudokuP: 12-clue Puzzle Search

Postby blue » Fri Jul 20, 2018 10:31 pm

Hi Serg,

Thanks.
The numbers all match.
blue
 
Posts: 708
Joined: 11 March 2013

Re: SudokuP: 12-clue Puzzle Search

Postby Serg » Sun Jul 22, 2018 5:29 pm

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
2018 Supporter
 
Posts: 607
Joined: 01 June 2010
Location: Russia

Re: SudokuP: 12-clue Puzzle Search

Postby Serg » Sun Jul 22, 2018 11:00 pm

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
Serg
2018 Supporter
 
Posts: 607
Joined: 01 June 2010
Location: Russia

Re: SudokuP: 12-clue Puzzle Search

Postby blue » Mon Jul 23, 2018 7:11 am

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: 708
Joined: 11 March 2013

Re: SudokuP: 12-clue Puzzle Search

Postby Serg » Mon Jul 23, 2018 5:58 pm

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
Serg
2018 Supporter
 
Posts: 607
Joined: 01 June 2010
Location: Russia

Re: SudokuP: 12-clue Puzzle Search

Postby Mathimagics » Mon Jul 23, 2018 6:33 pm

Hi Serg!

Well done! 8-)

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

Re: SudokuP: 12-clue Puzzle Search

Postby Serg » Mon Jul 23, 2018 7:34 pm

Hi, Mathimagics!
Mathimagics wrote:Well done! 8-)

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: 607
Joined: 01 June 2010
Location: Russia

Re: SudokuP: 12-clue Puzzle Search

Postby Mathimagics » Mon Jul 23, 2018 9:10 pm

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

Re: SudokuP: 12-clue Puzzle Search

Postby Serg » Mon Jul 23, 2018 9:55 pm

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: 607
Joined: 01 June 2010
Location: Russia

Re: SudokuP: 12-clue Puzzle Search

Postby Mathimagics » Mon Jul 23, 2018 10:09 pm

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

Re: SudokuP: 12-clue Puzzle Search

Postby blue » Tue Jul 24, 2018 8:19 am

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: 708
Joined: 11 March 2013

SudokuP: 12-clue Puzzle Search

Postby Mathimagics » Tue Jul 24, 2018 12:21 pm

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

PreviousNext

Return to Sudoku variants