The New Sudoku Players' Forum

[blue]

Canonical bands:

By definition all the 416 bands are compatible with sudokuP .

That is true, and each of them has (many) extensions to a complete grid.
With SudokuP, though, there are 6585 "minlex canonical" bands ... or "band types".

The larger number, is due to there only being 2*6^3 transformations (as opposed to 6^5), that can be used in canonicalization.
The factor of 2, comes from the "F" transformation ... mapping bands to bands.
For the uninitiated, F swaps mini-rows 2 & 4, 3 & 7, and 6 & 8 ... separately, in each band, when it's applied to a full grid (or puzzle).

The canonical grid catalog:

When the minlex canonical grids are listed in minlex order, the list splits into sections with the same (minlex) canonical band, in the band 1 position.
As it was with standard Sudoku, the "would be" sections for some of the 6585 canonical/minlex band types, are "empty".
Those bands don't have any extension to a minlex canonical grid.
The number of non-empty sections, is 5067, and the first empty section, would be for canonical band index #3312.
Again, as it was with standard Sudoku, near the beginning of the list, the "same band 1" sections are large ... and near the end, they're small.
The first section, contains 1,268,254 grids. It completely covers Mathimagics' first (1M grid) "interval", from above. The 2nd section contains 3,440,695. The last interval that Mathimagics described ... grids 53000001-53666690 ... contains 4012 complete, non-empty, "same band 1" sections, and part of another.

'MinClues' values for SudokuP bands:

In 2011 -- is it really that long ago ! -- Mladen published a table of information about (standard) Sudoku bands -- Bands and low-clue puzzles.
Of particular interest here, is the "MinClues" column.
It shows the (genuine) minimum number of clues that are needed to hit every unavoidable set in the band.
(The MinClues number is >= the "MCN" number for the "in band" UA sets).
For a puzzle with a given grid as its solution, each band must contain a number of clues that's >= the MinClues value for its "band type".
Note: As was definitely not the case with standard Sudoku, many of the bands -- 1718 of them -- have "MinClues=0".
(For standard Sudoku, the values were always >= 2).

There's a (zipped) file attached below.
The file lists, for each band type (in minlex order):

The 27 cell values for the band.
The number of canonical grids having the band in the band 1 position.
A running subtotal of the above -- from the subtotal, you can tell where the "same band" sections fall, in Mathimagics' "interval" scheme.
The "MinClues" value for the band.

spb-data.zip

(52.87 KiB) Downloaded 196 times

[blue]

Related to the above post ...

Below is a copy of Mathimagics' table from this post, showing how the grids that where "known at the time, to contain a 12-clue puzzle", is distributed by "inverval", in the canonical grid catalog.

Two columns have been added.
One, (MB1C), shows the average of the MinClues value for band 1, across the interval.
Another, (MB1Cr), shows that number, divided by the average over the entire catalog.

As can be seen by that last column ... intervals where the MinClues average is small, contain larger numbers of "12C grids", and vica-versa.

Hidden Text: Show

Code: Select all

   # of 12C grids = 50821

   N       12C    %12C     %Pool  MB1C  MB1Cr
  ===========================================
  00:        0                    6.00   2.36
  01:        0                    4.54   1.78
  02:        0                    4.00   1.57
  03:        0                    4.00   1.57
  04:        1                    3.71   1.46
  05:        3                    3.75   1.47
  06:        2                    3.28   1.29
  07:       13    0.03%    0.03%  3.00   1.18
  08:       56    0.11%    0.14%  3.00   1.18
  09:       94    0.18%    0.38%  3.07   1.21
  10:       68    0.13%    0.37%  2.61   1.02
  11:      192    0.38%    0.32%  2.06   0.81
  12:       62    0.12%    0.23%  2.78   1.09
  13:      810    1.59%    2.02%  2.23   0.88
  14:      593    1.17%    1.66%  1.62   0.64
  15:     1915    3.77%    3.97%  1.74   0.68  *
  16:      222    0.44%    0.60%  1.57   0.62
  17:      744    1.46%    2.37%  1.21   0.48
  18:      765    1.51%    2.60%  1.73   0.68
  19:     3036    5.97%    6.06%  1.01   0.40
  20:     2797    5.50%    4.81%  0.81   0.32
  21:     4238    8.34%    7.72%  0.83   0.33
  22:     5661   11.14%    8.08%  0.13   0.05  **
  23:     2941    5.79%    3.18%  2.24   0.88  ***
  24:       24    0.05%    0.08%  2.61   1.02
  25:       34    0.07%    0.26%  2.82   1.11
  26:       77    0.15%    0.43%  2.67   1.05
  27:       80    0.16%    0.22%  2.84   1.11
  28:       17    0.03%    0.14%  3.00   1.18
  29:      496    0.98%    2.20%  2.75   1.08
  30:        7    0.01%    0.08%  3.00   1.18
  31:       36    0.07%    0.23%  2.79   1.10
  32:      312    0.61%    0.81%  2.38   0.94
  33:      151    0.30%    0.48%  2.32   0.91
  34:      351    0.69%    1.20%  2.11   0.83
  35:      291    0.57%    1.08%  2.34   0.92
  36:      159    0.31%    0.46%  2.73   1.07
  37:       83    0.16%    0.56%  2.87   1.13
  38:      125    0.25%    0.77%  2.80   1.10
  39:       33    0.06%    0.24%  2.99   1.18
  40:      792    1.56%    2.47%  2.47   0.97
  41:       35    0.07%    0.30%  3.00   1.18
  42:     1414    2.78%    3.60%  1.81   0.71
  43:     1161    2.28%    2.85%  1.90   0.74
  44:       95    0.19%    0.69%  2.60   1.02
  45:      614    1.21%    1.91%  2.23   0.87
  46:     1252    2.46%    2.96%  1.69   0.67
  47:      595    1.17%    1.69%  2.14   0.84
  48:      725    1.43%    2.17%  2.66   1.05
  49:       23    0.05%    0.19%  3.56   1.40
  50:      367    0.72%    2.04%  3.03   1.19
  51:     3705    7.29%    7.80%  2.08   0.82
  52:     3259    6.41%    6.61%  2.66   1.05
  53:    10295   20.26%   10.92%  1.38   0.54  ******

There's an oddity: The "22" interval has MB1Cr = 0.05 -- the smallest among all intervals.
It does contain a large number of the "12C grids", but it doesn't seem to be as large as might be expected, given its MB1Cr value.

[blue]

MCB number:

We can rename this.
I had in mind "minimum clues using band method", for the acronym.

Given what I saw in the table in the last post, I decided to compute a new number for each grid ... the MCB number.
More or less, it's the sum of the "MinClues" number for the bands ("band types") in some transformed form for the grid.
If we apply a transformation that maps bands to bands, that sum won't change.
We can transpose the grid, though ... mapping stacks to bands ... and form the sum for that configuration.
If it's larger ... we'ld want to use that, for the MCB number.

P-bands and p-stacks:

The diagram should be self-explanatory.

Code: Select all

+-------+-------+-------+    +-------+-------+-------+
| x x x | x x x | x x x |    | x . . | x . . | x . . |
| . . . | . . . | . . . |    | x . . | x . . | x . . |
| . . . | . . . | . . . |    | x . . | x . . | x . . |
+-------+-------+-------+    +-------+-------+-------+
| x x x | x x x | x x x |    | x . . | x . . | x . . |
| . . . | . . . | . . . |    | x . . | x . . | x . . |
| . . . | . . . | . . . |    | x . . | x . . | x . . |
+-------+-------+-------+    +-------+-------+-------+
| x x x | x x x | x x x |    | x . . | x . . | x . . |
| . . . | . . . | . . . |    | x . . | x . . | x . . |
| . . . | . . . | . . . |    | x . . | x . . | x . . |
+-------+-------+-------+    +-------+-------+-------+
          p-band                      p-stack

P-band #1, shown above, contains all cells at box positions 1,2 or 3.
P-stack #1, also shown above, contains all cells at box positions 1,4 or 7.

The F transformation (above), maps stacks to p-bands and vica-versa.
The (related) G transformation, maps bands to p-stacks and vica-versa.
[ G is like F, but it swaps mini-columns within stacks. ]

For what follows, the E transformation is "more useful", maybe.
[ E swaps rows 2 & 4, 3 & 7, and 6 & 8, and columns 2 & 4, 3 & 7, and 6 & 8. ]
It maps (b)-bands to p-bands and vica versa, and (b)-stacks to p-stacks and vica-versa.

MCB finalized:

With the above in mind, we can also apply the E transformation to the grid, and look at the sums for bands and stacks in the result.
The "final" MCB number, then, would be defined to be the largest of the 4 sums.

Below, is a breakdown of all grids by MCB number, and some numbers related to the collection of "12C grids" that I have on hand.

Code: Select all

 MCB |    grids |  12CG | 12CG/grids
-----+----------+-------+-----------
  0  |      404 |   382 |   94.5545%
  1  |     8460 |  4992 |   59.0071%
  2  |    80749 | 14943 |   18.5055%
  3  |   465992 | 15235 |    3.2694%
  4  |  1729441 |  7290 |    0.4215%
  5  |  4263856 |  1941 |    0.0455%
  6  |  7781962 |   290 |    0.0037%
  7  | 10245574 |    20 |    0.0002%
  8  | 10402287 |     0 |           
  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 | 45093 |    0.0840%

As can be seen, the correlation between low MCB numbers, and the likelihood that a grid has a 12-clue puzzle, is very pronounced.
Unfortunately, there's also a correlation between low MCB numbers, and long CPU times, when it comes to (definitive) testing, for whether a grid has a 12-clue puzzle

For Mathimagics: The six grids in your recent post in the other thread, are all "MCB=0" grids.

------

I've been doing sampling in each MCB class -- different sample counts in each class -- to come up with a good estimate for the number of grids with 12-clue puzzles ... "12C" grids.
It's nearly finished to the point where I want to stop.
The "MCB=3 class", is taking a long time

[Mathimagics]

.
Interesting!

Seems that either way you approach it, grids most likely take longest times to test ...

The MCB = 18 entry seems anomalous? grid counts have strictly bell-shape until that point ...

[blue]

OK, the job has finished.

The estimate is: 70659 grids, plus or minus 1972
(Round that how you like ... "70700 +/- 2000" ?).

Code: Select all

 MCB |    grids |  12CG | 12CG/grids | (hits/tries) %estimate |  12CG_estimate
-----+----------+-------+------------+------------------------+---------------
  0  |      404 |   382 |   94.5545% | (   390/404)  96.5347% |   390    exact (*)
  1  |     8460 |  4992 |   59.0071% | (   221/300)  73.6667% |  6232 +/-  422
  2  |    80749 | 14943 |   18.5055% | ( 1348/5000)  26.9600% | 21770 +/-  993
  3  |   465992 | 15235 |    3.2694% | (2107/40000)   5.2675% | 24546 +/- 1020
  4  |  1729441 |  7290 |    0.4215% | ( 710/90000)   0.7889% | 13643 +/- 1000
  5  |  4263856 |  1941 |    0.0455% | ( 75/100000)   0.0750% |  3198 +/-  723
  6  |  7781962 |   290 |    0.0037% | ( 15/150000)   0.0100% |   778 +/-  394
  7  | 10245574 |    20 |    0.0002% | (  5/500000)   0.0010% |   102 +/-   90
  8  | 10402287 |     0 |            |                        |     ?        ?
  9  |  7907126 |     0 |            |                        |     ?        ?
 10  |  6050227 |     0 |            |                        |     ?        ?
 11  |  1248900 |     0 |            |                        |     ?        ?
 12  |  2339518 |     0 |            |                        |     ?        ?
 13  |   249346 |     0 |            |                        |     0    exact
 14  |   584224 |     0 |            |                        |     0    exact
 15  |    32255 |     0 |            |                        |     0    exact
 16  |     5926 |     0 |            |                        |     0    exact
 17  |        0 |     0 |            |                        |     0    exact
 18  |   270442 |     0 |            |                        |     0    exact
-----+----------+-------+------------+------------------------+---------------
     | 53666689 | 45093 |    0.0840% |                0.1317% | 70659 +/- 1972

(*) 390 = 382 + (8 of 22)

The error estimates for each "slot", are calculated using the math for an infinite pool of grids, and the given sample size and "hit" count.
The fact that the grid counts are finite, should mean that the error estimates are slightly high.
The error estimate for the final sum, is the square root of the sum of the squares of the individual errors ... standard math, for statistically independent "experiments".

Edit: When I updated the "12CG_estimate" column for the "last to finish" results (MCB=3,6), I forgot to update the "(hits/tries) %estimate" columns, too.

[blue]

The MCB = 18 entry seems anomalous? grid counts have strictly bell-shape until that point ...

It does at that ... interesting.
I'll do a bug check.

[blue]

I didn't see anything glaring in the code.

The arrays were all properly dimensioned, and there were checks in place, to verify that the calculated MCB number was in the 0-18 range.
I did check that all of the grids in my "MCB=18" file, had a transformation that left all 3 bands with one of the two types that are listed as having MinClues = 6.

On closer inspection, I see that "strictly bell shaped" wasn't true.
Look at the MCB=11-vs-12 and MCB=13-vs-14 counts.

[Mathimagics]

Ok, for "strictly" read "generally"

MCB=18 still sticks out like a sore thumb ...

[Mathimagics]

We now have 54,345 12C grids ...

Shall I update my table, or wait for more?

[blue]

We now have 54,345 12C grids ...

Shall I update my table, or wait for more?

If you're asking whether I might like to send puzzles and/or grids ... I wouldn't.
After spoiling the party for 11-clue puzzles, I'ld rather stand back and let you guys have the fun here.

I have 230148 puzzles on 45093 grids (from months ago).
My guess would be that they're almost entirely a subset of what you guys have already found.
Anyway that's my story, and I'm sticking with it

Cheers.

[Mathimagics]

.
I only meant my interval table vs 12CG's above ... but I see that's irrelevant anyhow ...

Can I easily extract grid v MCB from the zip file?

[blue]

MCB=18 still sticks out like a sore thumb ...

It does !

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 ?

[blue]

.
I only meant my interval table vs 12CG's above ... but I see that's irrelevant anyhow ...

"Mostly" irrelevant

FWIW, the column with your 12CG counts, looked a lot like a (MCB) column in a table that I have, that shows #'s of grids with a particular MCB, in each of your catalog intervals. It had a correlacton coefficient of 0.95, with the MCB=2 column. Your "pool" grid counts, had the same, for the MCB=3 column.

Can I easily extract grid v MCB from the zip file?

No. The numbers in it, that are related to the minlex catalog, were just there to look at ... not useful for anything, I think.
The file was mostly to provide "MinClues" numbers for whatever use someone might have in mind.

If you had a routine to canonicalize a band, you could set up a lookup "table" to get MinClues numbers for the bands, and use the canonicalization routine with outlined procedure, to calculate the MCB number for a grid ... and add it as a tag, to your grids database, like Mladen was suggeting. My code took about an hour, to do the calculations for the full catalog.

[coloin]

Thanks blue
That is just the post we needed to cap this fruitless search !
Picking the best one of the 4 was neat
It was fun making the new puzzles - and thanks to mathimagics for his work and enthusiasm

Is there any extrapolations back to 17/18 clue normal sudoku space ?
I woke up in a sweat thinking that we could "morph" each ED normal sudoku grid in BCR/CBR/CRB

[blue]

TIs there any extrapolations back to 17/18 clue normal sudoku space ?

That's an interesting question. The 11-clue puzzles, despite the low counts, show the same pattern ...

Code: Select all

 MCB |    grids | 11CG | 11CG/grids |
-----+----------+------+------------+
  0  |      404 |    3 |    0.7426% |
  1  |     8460 |    5 |    0.0591% |
  2  |    80749 |    3 |    0.0037% |
  3  |   465992 |    1 |    0.0002% |

  #15449135 MCB=3 (B1)
  #22504781 MCB=2 (B2)
  #22979593 MCB=1 (B3)
  #23068647 MCB=1 (B4)
  #23201464 MCB=2 (B5)
  #23201702 MCB=2 (B6)
  #53380826 MCB=1 (B7)
  #53541837 MCB=1 (O5)
  #53557072 MCB=0 (O2,O4) 2a,4p
  #53624261 MCB=1 (O1,O3)    2p
  #53658889 MCB=0 (B8)    2a,2p
  #53658890 MCB=0 (B9)    2a,2p

  a = automorphisms
  p = puzzles

I'll do the similar calculations for 17's and standard sudoku grids, and post the results in Mladen's "Bands and low-clue puzzles" thread.
(On the other hand, maybe he's already on it !)

What's encouraging, is that the counts in the "grids" column in the (short) table above, sum to only ~1% of the total.

Side note: the MCB number would only be the max of two sums, rather than 4 ... but there are 9 ways to partition a grid into "B12347/B5689".

---

That is just the post we needed to cap this fruitless search !
Picking the best one of the 4 was neat
It was fun making the new puzzles - and thanks to mathimagics for his work and enthusiasm

If that means the party's over, then kick me to the curb and drop a piano on my head.