## UA Set for a Given Grid

Everything about Sudoku that doesn't fit in one of the other sections

### UA Set for a Given Grid

A couple of months back, I asked blue how many MUA's (minimal UA's) might exist for a given target grid, and how long it might take to find them all with a random-reduction search method.

To paraphrase his response, the answers to these questions were "quite a lot", and "quite a while" respectively …

As usual, he'd been there, done that ... see here:http://forum.enjoysudoku.com/post253291.html#p253291

Anyway, I let my search process run on the selected target, and killed it a couple of weeks later when it had found almost 700 million MUA's, which now very looks very much like representing, at the very best, barely 1% of the actual set.

I kept the data, and have found some points of interest, hence this posting.

Firstly, the target grid, T, is actually a case that dobrichev found with a 40-clue minimal puzzle. Here is T alongside its CF (canonical form):
Code: Select all
`+-------+-------+-------+  +-------+-------+-------+| 5 7 6 | 8 2 1 | 3 4 9 |  | 1 2 3 | 4 5 6 | 7 8 9 || 8 1 2 | 9 3 4 | 5 6 7 |  | 4 5 6 | 7 8 9 | 1 2 3 || 9 3 4 | 5 7 6 | 1 8 2 |  | 7 9 8 | 1 3 2 | 5 6 4 |+-------+-------+-------+  +-------+-------+-------+| 7 4 1 | 3 5 8 | 2 9 6 |  | 2 3 1 | 6 7 5 | 4 9 8 || 3 5 8 | 6 9 2 | 4 7 1 |  | 5 8 4 | 9 2 3 | 6 1 7 || 6 2 9 | 1 4 7 | 8 5 3 |  | 6 7 9 | 8 4 1 | 2 3 5 |+-------+-------+-------+  +-------+-------+-------+| 4 6 3 | 7 1 5 | 9 2 8 |  | 3 6 7 | 5 1 8 | 9 4 2 || 1 8 5 | 2 6 9 | 7 3 4 |  | 8 1 5 | 2 9 4 | 3 7 6 || 2 9 7 | 4 8 3 | 6 1 5 |  | 9 4 2 | 3 6 7 | 8 5 1 |+-------+-------+-------+  +-------+-------+-------+`

And here is table of the MUA counts I found for T, by size and # of different digits involved:

Hidden Text: Show
MUA table
Code: Select all
` ------------------------------------------------------------------------------------------- UA sz                  2d       3d       4d       5d       6d        7d        8d        9d ------------------------------------------------------------------------------------------- sz  4:         5        5        .        .        .        .         .         .         . sz  6:        12        4        8        .        .        .         .         .         . sz  8:        18        2       13        3        .        .         .         .         . sz  9:         8        .        3        5        .        .         .         .         . sz 10:        78        1       21       38       18        .         .         .         . sz 11:        49        .        5       24       20        .         .         .         . sz 12:       195        3       19       46       86       41         .         .         . sz 13:       119        .        8       32       57       22         .         .         . sz 14:       508        4       30       84      216      137        37         .         . sz 15:       610        .       23      118      238      177        54         .         . sz 16:      1533        .       29      192      533      545       212        22         . sz 17:      2199        .       22      242      701      818       365        51         . sz 18:      5393       27       55      356     1422     2064      1166       269        34 sz 19:      8771        .       51      430     2019     3453      2247       541        30 sz 20:     18579        .       61      624     3512     7096      5375      1743       168 sz 21:     33275        .       49      813     5072    12116     11171      3723       331 sz 22:     67835        .       37     1150     8220    22397     24701     10114      1216 sz 23:    127962        .       18     1397    12218    38547     49300     23383      3099 sz 24:    256349        .       12     1616    18572    68855    101244     56771      9279 sz 25:    492782        .        3     1653    27183   116985    196413    126814     23731 sz 26:    977016        .        .     1602    39003   199785    387487    285478     63661 sz 27:   1886965        .        .     1303    51340   330300    735282    614007    154733 sz 28:   3700697        .        .      892    64205   532248   1392611   1327494    383247 sz 29:   7166139        .        .      525    74472   827743   2564168   2789054    910177 sz 30:  13816659        .        .      204    77924  1224983   4602369   5773741   2137438 sz 31:  26141845        .        .       55    72020  1691125   7943974  11586981   4847690 sz 32:  47328145        .        .        5    55087  2109234  12783758  21938048  10442013 sz 33:  76551886        .        .        .    32340  2177353  17713710  36633628  19994855 sz 34: 103126684        .        .        .    12425  1697117  19447335  50074812  31894995 sz 35: 111456930        .        .        .     3154   960083  16222785  53556191  40714717 sz 36:  98311849        .        .        .      456   404677  10496465  45445860  41964391 sz 37:  74335351        .        .        .       36   132691   5552268  32135480  36514876 sz 38:  50618794        .        .        .        1    35027   2520452  19908705  28154609 sz 39:  32073179        .        .        .        .     7682   1011195  11159028  19895274 sz 40:  19234606        .        .        .        .     1303    361365   5750090  13121848 sz 41:  10973751        .        .        .        .      173    114781   2735713   8123084 sz 42:   5960058        .        .        .        .       19     32071   1199446   4728522 sz 43:   3077233        .        .        .        .        1      7678    483828   2585726 sz 44:   1501441        .        .        .        .        .      1560    177095   1322786 sz 45:    689473        .        .        .        .        .       242     58310    630921 sz 46:    295215        .        .        .        .        .        37     17315    277863 sz 47:    118542        .        .        .        .        .         3      4579    113960 sz 48:     43417        .        .        .        .        .         .       976     42441 sz 49:     14517        .        .        .        .        .         .       168     14349 sz 50:      4286        .        .        .        .        .         .        28      4258 sz 51:      1126        .        .        .        .        .         .         2      1124 sz 52:       267        .        .        .        .        .         .         .       267 sz 53:        60        .        .        .        .        .         .         .        60 sz 54:        10        .        .        .        .        .         .         .        10 sz 55:         4        .        .        .        .        .         .         .         4 ------------------------------------------------------------------------------------------- Total  690422425       46      467    13409   562550 12604797 104283881 303879488 269077787`

Mathimagics
2017 Supporter

Posts: 1329
Joined: 27 May 2015
Location: Canberra

### Blue's Sample Predictions

Estimating total MUA's for grid T

I have appended my MUA counts to blue's table, and divided the table into zones. The first zone is UA sizes 4 to 25, for which the full count for the target grid is (almost certainly) known:

Code: Select all
`--------+--------------------+--------------------+--------------+------------UA size | A = all grids      | G = grids with 17s |      int(G)  |       T--------+--------------------+--------------------+--------------+------------    4   | 1.1580e+1 ( 0.04%) | 7.1160e+0 ( 0.03%) |            7 |         5    6   | 1.5338e+1 ( 0.06%) | 1.4746e+1 ( 0.03%) |           15 |        12    8   | 2.2038e+1 ( 0.07%) | 2.2646e+1 ( 0.04%) |           23 |        18    9   | 6.0455e+0 ( 0.16%) | 7.2594e+0 ( 0.08%) |            7 |         8   10   | 5.8380e+1 ( 0.08%) | 6.7124e+1 ( 0.04%) |           67 |        78   11   | 2.9499e+1 ( 0.12%) | 3.8499e+1 ( 0.06%) |           38 |        49   12   | 1.3667e+2 ( 0.09%) | 1.6819e+2 ( 0.05%) |          168 |       195   13   | 1.0483e+2 ( 0.11%) | 1.3118e+2 ( 0.06%) |          131 |       119   14   | 3.6172e+2 ( 0.09%) | 4.4636e+2 ( 0.05%) |          446 |       508   15   | 3.9133e+2 ( 0.11%) | 5.0261e+2 ( 0.05%) |          503 |       610   16   | 1.0498e+3 ( 0.10%) | 1.3534e+3 ( 0.05%) |         1353 |      1533   17   | 1.4800e+3 ( 0.10%) | 1.9305e+3 ( 0.05%) |         1931 |      2199   18   | 3.4658e+3 ( 0.10%) | 4.5559e+3 ( 0.05%) |         4556 |      5393   19   | 5.5821e+3 ( 0.10%) | 7.4088e+3 ( 0.05%) |         7409 |      8771   20   | 1.1778e+4 ( 0.10%) | 1.5759e+4 ( 0.05%) |        15759 |     18579   21   | 2.0773e+4 ( 0.11%) | 2.8016e+4 ( 0.05%) |        28016 |     33275   22   | 4.1781e+4 ( 0.11%) | 5.6895e+4 ( 0.06%) |        56895 |     67835   23   | 7.7262e+4 ( 0.11%) | 1.0601e+5 ( 0.06%) |       106010 |    127962   24   | 1.5191e+5 ( 0.12%) | 2.1048e+5 ( 0.06%) |       210480 |    256349   25   | 2.8748e+5 ( 0.12%) | 4.0185e+5 ( 0.06%) |       401850 |    492782`

The counts for T seem to correlate better with the sample predictions for "grids with 17's" than they do with the "all grids" figures. For that reason I have shown the integerised values for the 17's to make the comparison clearer.

The remaing zones (see full table below) are:

• size 26 - 33: the T counts exceed the 17-clue estimates, and are probably very close to being full counts.
• size 34 - 49: the T counts peak at size at 34/35 and dwindle rapidly. This zone has the estimated 99% of MUA's that are still to be found, but which are also the hardest to find using existing methods. The zone also marks the limit of what blue's sampling process can achieve, for the same reason, the difficulty of obtaining samples!
• size 50 - 62: the twilight zone! We have samples of up to size 55 for T, and we know 62 is possible for other grids (again, dobrichev), but mostly this zone is a mystery.
• size 63: its very existence is questionable (or can we deduce that a minimal UA63 is not possible?)

Full Table: Show
Code: Select all
`--------+--------------------+--------------------+--------------+------------UA size | A = all grids      | G = grids with 17s |       int(G) |   grid  T   --------+--------------------+--------------------+--------------+------------    4   | 1.1580e+1 ( 0.04%) | 7.1160e+0 ( 0.03%) |            7 |         5    6   | 1.5338e+1 ( 0.06%) | 1.4746e+1 ( 0.03%) |           15 |        12    8   | 2.2038e+1 ( 0.07%) | 2.2646e+1 ( 0.04%) |           23 |        18    9   | 6.0455e+0 ( 0.16%) | 7.2594e+0 ( 0.08%) |            7 |         8   10   | 5.8380e+1 ( 0.08%) | 6.7124e+1 ( 0.04%) |           67 |        78   11   | 2.9499e+1 ( 0.12%) | 3.8499e+1 ( 0.06%) |           38 |        49   12   | 1.3667e+2 ( 0.09%) | 1.6819e+2 ( 0.05%) |          168 |       195   13   | 1.0483e+2 ( 0.11%) | 1.3118e+2 ( 0.06%) |          131 |       119   14   | 3.6172e+2 ( 0.09%) | 4.4636e+2 ( 0.05%) |          446 |       508   15   | 3.9133e+2 ( 0.11%) | 5.0261e+2 ( 0.05%) |          503 |       610   16   | 1.0498e+3 ( 0.10%) | 1.3534e+3 ( 0.05%) |         1353 |      1533   17   | 1.4800e+3 ( 0.10%) | 1.9305e+3 ( 0.05%) |         1931 |      2199   18   | 3.4658e+3 ( 0.10%) | 4.5559e+3 ( 0.05%) |         4556 |      5393   19   | 5.5821e+3 ( 0.10%) | 7.4088e+3 ( 0.05%) |         7409 |      8771   20   | 1.1778e+4 ( 0.10%) | 1.5759e+4 ( 0.05%) |        15759 |     18579   21   | 2.0773e+4 ( 0.11%) | 2.8016e+4 ( 0.05%) |        28016 |     33275   22   | 4.1781e+4 ( 0.11%) | 5.6895e+4 ( 0.06%) |        56895 |     67835   23   | 7.7262e+4 ( 0.11%) | 1.0601e+5 ( 0.06%) |       106010 |    127962   24   | 1.5191e+5 ( 0.12%) | 2.1048e+5 ( 0.06%) |       210480 |    256349   25   | 2.8748e+5 ( 0.12%) | 4.0185e+5 ( 0.06%) |       401850 |    492782--------+--------------------+--------------------+--------------+------------   26   | 5.5831e+5 ( 0.13%) | 7.8740e+5 ( 0.07%) |       787400 |    977016   27   | 1.0649e+6 ( 0.13%) | 1.5137e+6 ( 0.07%) |      1513700 |   1886965   28   | 2.0469e+6 ( 0.14%) | 2.9377e+6 ( 0.07%) |      2937700 |   3700697   29   | 3.8959e+6 ( 0.15%) | 5.6359e+6 ( 0.08%) |      5635900 |   7166139   30   | 7.3881e+6 ( 0.16%) | 1.0791e+7 ( 0.08%) |     10791000 |  13816659   31   | 1.3891e+7 ( 0.17%) | 2.0447e+7 ( 0.09%) |     20447000 |  26141845   32   | 2.5872e+7 ( 0.18%) | 3.8398e+7 ( 0.09%) |     38398000 |  47328145   33   | 4.7497e+7 ( 0.19%) | 7.1136e+7 ( 0.10%) |     71136000 |  76551886--------+--------------------+--------------------+--------------+------------   34   | 8.5945e+7 ( 0.21%) | 1.2982e+8 ( 0.11%) |    129820000 | 103126684   35   | 1.5226e+8 ( 0.23%) | 2.3212e+8 ( 0.12%) |    232120000 | 111456930   36   | 2.6388e+8 ( 0.25%) | 4.0553e+8 ( 0.13%) |    405530000 |  98311849   37   | 4.4514e+8 ( 0.28%) | 6.9067e+8 ( 0.14%) |    690670000 |  74335351   38   | 7.2814e+8 ( 0.32%) | 1.1396e+9 ( 0.16%) |   1139600000 |  50618794   39   | 1.1460e+9 ( 0.37%) | 1.8111e+9 ( 0.18%) |   1811100000 |  32073179   40   | 1.7355e+9 ( 0.43%) | 2.7683e+9 ( 0.21%) |   2768300000 |  19234606   41   | 2.5057e+9 ( 0.53%) | 4.0162e+9 ( 0.25%) |   4016200000 |  10973751   42   | 3.4120e+9 ( 0.68%) | 5.5462e+9 ( 0.32%) |   5546200000 |   5960058   43   | 4.3680e+9 ( 0.94%) | 7.1899e+9 ( 0.43%) |   7189900000 |   3077233   44   | 5.2410e+9 ( 1.36%) | 8.6178e+9 ( 0.62%) |   8617800000 |   1501441   45   | 5.8689e+9 ( 2.19%) | 9.8323e+9 ( 0.97%) |   9832300000 |    689473   46   | 5.8592e+9 ( 3.86%) | 9.8494e+9 ( 1.70%) |   9849400000 |    295215   47   | 5.2146e+9 ( 7.47%) | 8.7982e+9 ( 3.34%) |   8798200000 |    118542   48   | 3.9547e+9 (17.54%) | 7.3022e+9 ( 7.37%) |   7302200000 |     43417   49   | 3.3898e+9 (40.82%) | 6.0837e+9 (17.76%) |   6083700000 |     14517--------+--------------------+--------------------+--------------+------------   50   |                    |                    |              |      4286   51   |                    |                    |              |      1126   52   |                    |                    |              |       267   53   |                    |                    |              |        60   54   |                    |                    |              |        10   55   |                    |                    |              |         4   56   |                    |                    |              |   57   |                    |                    |              |   58   |                    |                    |              |   59   |                    |                    |              |   60   |                    |                    |              |   61   |                    |                    |              |   62   |                    |                    |              |--------+--------------------+--------------------+--------------+------------   63   ? existence?`

Based on the sample data for sizes 49, and making some liberal assumptions about the missing estimates, blue's data suggests T will have somewhere from 75 to 100 billion MUA's. This would suggest that my known MUA set of 690,422,425 is very likely less than 1% of the actual set.

At least, I think so …

Mathimagics
2017 Supporter

Posts: 1329
Joined: 27 May 2015
Location: Canberra

### UA's and Isomorphism

UA's and Isomorphism

Minimal UA's of size N correspond to puzzles of size 81-N that have 2 solutions, one of which is T, and a companion grid which I will call U.

If one considers UA4's and UA6's, it is fairly clear that any pair (T, U) must almost always be ED. There are some exceptions, but these are extremely rare.

Among the sample of 690 million MUA's for T, just 110 of them produce isomorphisms of T. These are listed below. There are 37 with size 18, 65 of size 30, and a sprinkling of others (including, remarkably, one of size 37!).

Some of the 18's are easily recognised as pairs of entire rows or columns, within a band/stack, for which presumably the corresponding permutation that they represent can't be divided into sub-cycles.

Others are clearly more exotic, and I trust somebody out there will be tempted into exploring them! (I'm already got too many pots on the stove)

List follows, note that each should be applied to the T on the left in the post above, not the canonicalized version.

Isomorphic UAs: Show
Code: Select all
`...............................................................XXXXXXXXXXXXXXXXXX...........................XXXXXXXXX.........XXXXXXXXX......................................................XXXXXXXXXXXXXXXXXX..............................................XX.XX.......XXX.X..X.XXX......XX..X.X.XXX.......XX.X.X..XXX...X...XX.X..........X.X...XX.X.XX.X...X.X.X...XXXXX.....X.X....X.XXX..X...X.X.X....X.X...X.X.........XXXXXXXXXXXXXXXXXX.............................................................XX...X.X...X.X.......X.....X.....X.X....X.X....X.....X.......X..X.X.X...........X.X...XX....XX..........X...X.X...X......X.....X..X...X.......X.X..X...X.........X.X...XX....XX..........X...X.X...X......X.....X..X...X..XXXXX.XXXXXXXX.XXX......XX.....XX....XX.......X.X.....X.....X......X...XX.X.............XX...X.X.........XXX...X.XX.XX.X...X.X.X....XXX....X.X.X..X.X.X.XXXXXXX.XXXXXXXXXX..X.X..X.X.....X..X.X.X.....X.....X....X....X.....X...X..XX.........X.X..X....X....X.....X......X..X.X.X.....X.....X..XX.XXXXXX....X...XXX.XXXXXX....X.X..X....X....X.....X......X.X..X...X.....X...X...XX............X.X...XX....X...X....X.......X...X...X......XX...X..X.....X....X....XX.....X.......X...X....X..X.X....X......X......X.X......XX...X..X.....X....X....XX.....X.......X...X....X..X.X....XXXXXXX.XXXXXXXX.X.....XX...X..X.....X....X..XXX.XXXXXX.......XXXX.XXXXX..X.X....X......X......X.X......XX..X.XXXXXXXX.XXXXXXX..XX.....X.......X...X....X..X.X....X......X......X.X......XXXXXXX.XX....X....XX..X.XX..XX.........X...X.XX.XXXX....X.X.....XXX.XX.XX......X..X...X..X.....X.....X.X....X.......XX...X..X....X......X....X....XX..X.........X..X...X..X.....X.....X.X....X.......XX...X..X....X......X.XXX.XXXXXXXX.XXXXX....X..X...X..X.....X.....XX.XXXXXXX.....XX..X.XXXXXXXX......X....X....XX..X.........X..X...X..X.....X.....XXXXXXX.XXXXXXXX.XX.X..X....X......X....X....XX..X.........X..X.XX.XXXXXXXX.XXXXXX.X....X.......XX...X..X....X......X....X....XX..X.........X.X....X.X.....X......X...X..X..X....X....X......X..X....X....X...X.X....X.......XX.......XX.......XX.......XX.......XX.......XX.......XX.......XX.......XX.......XX....XX............X.X..X...X.......X..X.X.X.........X..X..XXXXXXXX.XXXXXXXX....XX....XX............X.X..X...X.......X..X.X.X.........X..X.X..X.....X......X.....XXXX...........XX.XX....X.XXX...X...XXX......XX..XX.X.XX.......XX.XX...XXX......X....X.XXXXXXXX.XXXXXXXX.....X.X...X.X......X...X........X.X.X...X....X..X.......X....XX..X.....X......X......X.X...X.X......X...X........X.X.X...X....X..X.......X....XX..X.....X......X......X.X...X.X......X...X........X.XX.XXXXXXXX.XXXXXXX...X...X.X....X.....X....X..X...X.....X...X......X.X..X.......X.X......X...XX.......X..X..X...X.....X.....X....X.X...X.X............X.X..X.....X.X.....X.....XX......X.X......X.X......X.X......X.X......X.X......X.X......X.X......X.X......X.X......X.X.XX.........X.XX.X....X.X.X.X....XXXX....XXXX...X..X.XX.....X.X..X.X.X.X......X.XX..X..XXX....X.X.X.X..........X.XX.X......X.XX.X..XX.X..X.X.X.X.X....XXX......X.XXX....XXX....XXX.X....X.X.X...X..X.XX.....XXX..XX.XX.X......X.X.XX............X.XXXXXXX..X....XX...X...X..XX.XXX.X...X..X...X.XXX.XXX....X.........X.XXX.X.....XX.......XX.......XX.......XX.......XX.......XX.......XX.......XX.......XX.......XX..X.X..XXX.....XXX..X..X.XXX.....XXX.X.....XX.X..X..XX...X.X.XX...X............XX.X.X.........XX.XX.......XX..X.X..XX......XXX...X..XXX.X.....XXX.X..X.XXX......XXX.X..X.XXX.....XXX.X...XXXX.......XX.X.X.........X..XX....X..XX...X...XX..X....XXXX..X...XX....X..XX.X....XXX...X.X.XX.......XXX.X..X.XX..X.X..XX.X.............XXXXX...X..X....XX.XX..X..XX.XX.X.....X..XXX.XXX....XX..X...X.XXX..XX.....XX.X..X..X....X.....X......XX....X.....X...X....XX..X......X..X....X...X..........XX...X..X....X.....X......XX..XXXXXXXX.XXXXXXXX.X..X......X..X....X...X..........XX...X.X......X....X......X..X......X.X...X.X...XX........X.....X....XX....X.....X....XX.....X......X......X.X......X..X..XX.....X.....X...X......X.X..X........X.X....XX.....X......X......X.X......X..X..XX.....X.....X...X......XXXXX.XXXXXXXX.XXXX..XX.....XXXXXXX.XXXXXXXX.X.....X..X..XX.....X.....X...X......X.X..X........X.X....XXX......XXX..X....XXX..X...XX.X.X...XXX...XX.XX.....X.XX..X..........X..XX.X....XXXX.....XX.X.X....X.X..X...X.XX.X.........XX.X.X....X.X.X.X....XXX...X..X.XX...X......X...X....XX...X....X......X.....X..X...X..X......X..X.......XX...XX.......X......X...X....XX...X....XXXXXXX.XXXXXXXX.X..X..X......X..X.......XX...XX.......X.....X......X..X..X.X....XX.............XX.....XX...X..X...........X.X..XX......X....X......X...X.X..X.....XXXXXXXX.XXXXXXXX.....X..X..XX...........XX...X..X....X....X......X...X.X..X....X..X.....X......X......X..X..XX...........XX...X..X....X....X..XXXX.XXXXXXXX.XXXXX..X.....X......X......X..X..XX...........XX...X..X....X...X....X......X....X.X..X.X.............XX...X.X......XX....X.....X....X....X..X..X......X.....X....X...XX.....X.......X.X..X...X......X...X....X..X..X.X.......X..X....XXXXXXXX.XXXXXXXX.X.....X.......X.X..X...X......X...X....X..X..X.X.......X..XX.X.....XX..X..X.XX...XX..XX.......XXXX..........X..XXX.......XXX.X..XXXX....X.X.....X.......X....X..X.X....X.....X....X......XX.....X....X.X....X....X.X.....X.X.....X.......X....X..X.XXXXX.XXX..X....X.XXXXX.XXX...X....X.X....X....X.X.....X.X.X....X.X.X..X...XXXX..X.XX.X......X.X.XX............XXX...X..X.XX....XX.X.X..X.XXX....X.XX...X...XX.X..X.XXX.......XX..XX...XXX............X..XX.X....XXX..X..XX.............XX....XX....XXXXXXXX...X...X..XXXXXXXX.X.X.........X.X....X...X...XX.............XX....XX...X.......X...X...X.X....X....X.X.........X.X....X...X...XX.............XX....XX...X.......X...X...X.X....X....X.X.....XXXXXX.XXXXXXXX.XX.XX.XX.......XX.XX.........X...XX..X...XXX.X.X...XX....X.XXX.......XXX....X.XXX...XXX.....XXX.....X.XX.X..X.XXX..X....XX....X..XX..XX...XXX....XX.XXXXXXXXX.XXXXXX.XXX..X..XXX.X.....XX....X..XXX.X...XXX.......XX...X.XXX.XXXXXXX.XXXXXXX.XX.XX....XXXXXXXX...X..X...XXXXXXXX....X..X..X..X......X....X......XX....X..X....X......XX.......X...X..X..X..X.........X..X..X..X......X....X......XX....X..X....X......XX.......X...X..X..X..X.....XXXX.XXXXXXXX.XXXX..X....X......XX....X..X....X......XX.......X...X..X..X..X.....XXXXXXX.X.X..X....XXXXXXX.X.....XX....X..X....X......XX.......XXXX.XXXXXXXX.XXXXX....X..X..X..X......X....X......XX....X..X....X......XX......X......XX....XX......X..X.....X....X......X..X.X....X.....X.....X...X....XX......X......XX....XX......X..X.....X....X......X..X.X....X...XXXXXXXX.XXXXXXXX.X......X......XX....XX.....X.XXXXXXXX.XXXXXXX....X..X.X....X.....X.....X...X....XX......X......XX....XX.....XXXX.XXXX.X....X..XXXX.XXXXX....X.....X.....X...X....XX....X....X....X.....X..X....X.X.....X......X...X...X.....XX...X.X.............XXX....X...XXXXXX.XXXXXXXX.XX..X.X.....X......X...X...X.....XX...X.X.............XXX...X......X...X.....X....X....X.X...X...X....X.....X......X.X...XX.....X.......XX...XX....X..XXX.....XXXX....X.XX....X..XX..X...XXX.X..........X.X.XX.......XX.XXX..XXXXXX...X.X..X..XXXXX...XX...X....X.XX..XXXXXX.X..XX.X..X.XX.X.XXXXX...XX....X.X............XX....X.X.......X...X.X.X.....X......X..X...X.....X.X..........X.XX.X......X.X......X.X......X.X......X.X......X.X......X.X......X.X......X.X......X.X....XXX.XX.X............XXX....X.X.X.X.X..X.X.X....X.X...X..X.X..X..XXXXX.....X.X...XX.X.X.XX...XXX......XXXX.....X.X...X..X.X.X...X.........X.X....XXX.XX.X...X.X..X...XXX...X..X.XX..X..X.X.X....XXX.....XX.XX...X.X.X.XX............X.X....XXX.XX..X..X.X.X....XXX....X.X.XX.X............X.X...X.XX.X.....XXXX....X.X.X.XX...X.XX.X......X.XXX.............XXX..X.X.X.X...X..X.X.X..X.X.X.....XXXX......X.XX.XX.XXXXXXX....X...XX.XXXXXXXX..X.....X......X......X..X..XX...........XX...X..X...X.XXXXXXXX.XXXXXXX....X.X..X.X.............XX...X.X......XX....X.....X....X....X.XX.XXXXXXXX.XXXXXX.....X..X......X.X...X.X...XX........X.....X....XX....X.....X..XXX..X...XXX.....XX.X.X.X...........X.X....XXX.XX.X...X.XXX....X.X...X..X.X....X.XXX.X....X.X.....XX.X.X...XX.X...X..X.X..X.X.XXX..X...X.XX...X.X.XX..X...........XXX.XXXXXXXX.XXXXXX......X......X.X...X.X......X...X........X.X.X...X....X..X....XXXX.XXXX..X.....XXXXX.XXXXX.....X.......X.X..X...X......X...X....X..X..X.X......XXXX.XXXXXXXX.XXXX.X......X...X..X..X....X....X......X..X....X....X...X.X....X...XXXXX.XXX.X.....X.XXXXX.XXX..X.....X...X....XX..X......X..X....X...X..........XX.XXXXX.XXXXXXXX.XXX..X...X...XX............X.X...XX....X...X....X.......X...X...X.XXXXXX.XX.X..X....XXXXXX.XX..XX.....X.......X...X....X..X.X....X......X......X.X.XXXXXXX.XX....X...XXXXXXX.X.X...X.....X...X......X.X..X.......X.X......X...XX....XXXXXXXX.XXXXXXXX.X...X....X......X.....X..X...X..X......X..X.......XX...XX......XXXXXXXXX.........XXXXXXXXX......................................................XXXXXXXXX..X.X...XX.XX.XXXXX..X..X..X....X.X..X...X..X..XX...X....X..XX.X.X..X...XXXXXXXXXXXXXXXXXX...............................................................`

Mathimagics
2017 Supporter

Posts: 1329
Joined: 27 May 2015
Location: Canberra

### Re: UA Set for a Given Grid

Hi Mathimagics,

dobrichev
2016 Supporter

Posts: 1745
Joined: 24 May 2010

### Re: UA Set for a Given Grid

That's strange, it should find at least one hit here ...

All I meant by that rather vague expression was that I found MUA's by randomly reducing (removing clues) from the target grid and at the first instance of multiple solutions I then extracted the UA's. Rinse and repeat …

Cheers!

Mathimagics
2017 Supporter

Posts: 1329
Joined: 27 May 2015
Location: Canberra

### Re: UA Set for a Given Grid

Isn't this slow?

I would compare the chosen grid with stream of randomly generated valid grids.
Then check whether the bitmap of the differences isn't superset of any of the first few hundreds of already known short minimal UA sets.
Then split (into 2+ disjoint UA) or minimize, one cell at a time. Not in all possible ways.

This should minimize the bias too.

Cheers,
MD
dobrichev
2016 Supporter

Posts: 1745
Joined: 24 May 2010

### Re: UA Set for a Given Grid

Of course it's slow! It was written by me!

This code was just a quick and nasty method originally written to find small numbers of UA's. I never anticipated it would one day be going on a multi-billion UA hunt …

But your suggestion seems like a good one, and I will give it a try ...

Mathimagics
2017 Supporter

Posts: 1329
Joined: 27 May 2015
Location: Canberra

### Re: UA's and Isomorphism

Mathimagics wrote:Minimal UA's of size N correspond to puzzles of size 81-N that have 2 solutions, one of which is T, and a companion grid which I will call U.

That isn't quite right.
Here's a proper definition.

S : a solution grid
U : a subgrid of S
P := S - U ... the puzzle produced from S, by removing the "clues" in U

If P has >= 2 solutions, then U is an unavoidable set (of S).
P has S as a solution, obviously.
If every other solution differs from S in every cell of U, then U is a minimal unavoidable set.

The valency of U, is defined as the number of solutions for P.
Most minimal UA's (of moderate size, at least) have valency 2.
Added: The terms strongly/weakly minimal, are used to distinguish between valency 2 and valency >= 3.
Edited: Wrong on my part. The Strong/weak definitions don't involve the valency number.
[ Valency=2 implies "strong", but (AFAIK) it's still undecided, whether the converse is true. ]
BTW: For grid T, there are 3 weak/"valency >= 3" minimals with size 22, 3 with size 23, and 25 with size 24.
I might have a result for size 25, when I get back home tonight.
For sizes <= 24, your counts match the "strong minimals""valency 2" counts
In addition there are 71 (size 25) minimals with valency >=3 ... one with v=4, the rest with v=3.

---

Here's a verison of my "counts" table, that includes information about "valency >= 3" cases.
For UA sizes <= 25, it looks like 99.99% of them have valency 2.
Hidden Text: Show
Code: Select all
`size |   minimal UA sets   |     valency >= 3    |   ratio-----+---------------------+---------------------+---------- 4   | 1.1580e+1 (  0.04%) |                     | 6   | 1.5338e+1 (  0.06%) |                     | 8   | 2.2038e+1 (  0.07%) |                     | 9   | 6.0455e+0 (  0.16%) |                     |10   | 5.8380e+1 (  0.08%) |                     |11   | 2.9499e+1 (  0.12%) |                     |12   | 1.3667e+2 (  0.09%) |                     |13   | 1.0483e+2 (  0.11%) |                     |14   | 3.6172e+2 (  0.09%) |                     |15   | 3.9133e+2 (  0.11%) |                     |16   | 1.0498e+3 (  0.10%) |                     |17   | 1.4800e+3 (  0.10%) |                     |18   | 3.4658e+3 (  0.10%) | 3.3787e-3 ( 59.10%) | 9.7487e-719   | 5.5821e+3 (  0.10%) | 1.5690e-2 ( 38.10%) | 2.8107e-620   | 1.1778e+4 (  0.10%) | 1.0898e-1 ( 18.40%) | 9.2533e-621   | 2.0773e+4 (  0.11%) | 4.0030e-1 ( 12.79%) | 1.9270e-522   | 4.1781e+4 (  0.11%) | 1.6317e+0 (  8.41%) | 3.9052e-523   | 7.7262e+4 (  0.11%) | 5.4877e+0 (  6.12%) | 7.1027e-524   | 1.5191e+5 (  0.12%) | 1.7002e+1 (  4.82%) | 1.1192e-425   | 2.8748e+5 (  0.12%) | 5.3381e+1 (  3.66%) | 1.8569e-426   | 5.5831e+5 (  0.13%) | 1.5338e+2 (  3.00%) | 2.7472e-427   | 1.0649e+6 (  0.13%) | 4.3704e+2 (  2.46%) | 4.1041e-428   | 2.0469e+6 (  0.14%) | 1.1532e+3 (  2.11%) | 5.6339e-429   | 3.8959e+6 (  0.15%) | 3.0590e+3 (  1.84%) | 7.8519e-430   | 7.3881e+6 (  0.16%) | 7.7228e+3 (  1.65%) | 1.0453e-331   | 1.3891e+7 (  0.17%) | 1.9571e+4 (  1.50%) | 1.4089e-332   | 2.5872e+7 (  0.18%) | 4.7553e+4 (  1.40%) | 1.8380e-333   | 4.7497e+7 (  0.19%) | 1.1388e+5 (  1.34%) | 2.3977e-334   | 8.5945e+7 (  0.21%) | 2.6384e+5 (  1.31%) | 3.0699e-335   | 1.5226e+8 (  0.23%) | 5.9284e+5 (  1.31%) | 3.8936e-336   | 2.6388e+8 (  0.25%) | 1.2800e+6 (  1.37%) | 4.8505e-337   | 4.4514e+8 (  0.28%) | 2.6858e+6 (  1.45%) | 6.0337e-338   | 7.2814e+8 (  0.32%) | 5.4933e+6 (  1.59%) | 7.5442e-339   | 1.1460e+9 (  0.37%) | 1.0506e+7 (  1.84%) | 9.1679e-340   | 1.7355e+9 (  0.43%) | 1.9351e+7 (  2.16%) | 1.1150e-241   | 2.5057e+9 (  0.53%) | 3.3455e+7 (  2.68%) | 1.3352e-242   | 3.4120e+9 (  0.68%) | 5.6215e+7 (  3.48%) | 1.6476e-243   | 4.3680e+9 (  0.94%) | 8.3512e+7 (  4.90%) | 1.9119e-244   | 5.2410e+9 (  1.36%) | 1.2100e+8 (  7.17%) | 2.3087e-245   | 5.8689e+9 (  2.19%) | 1.5797e+8 ( 11.16%) | 2.6916e-246   | 5.8592e+9 (  3.86%) | 1.9888e+8 ( 18.12%) | 3.3943e-247   | 5.2146e+9 (  7.47%) | 2.0544e+8 ( 34.59%) | 3.9397e-248   | 3.9547e+9 ( 17.54%) | 1.2840e+8 ( 87.65%) | 3.2468e-249   | 3.3898e+9 ( 40.82%) |                     |`

Example of (2) minimal UA's with valency 3.
Hidden Text: Show
Grid:

Code: Select all
`+-------+-------+-------+| 1 4 6 | 2 7 9 | 3 5 8 || 2 5 8 | 1 4 3 | 9 7 6 || 3 7 9 | 6 5 8 | 2 4 1 |+-------+-------+-------+| 7 3 1 | 8 6 5 | 4 2 9 || 8 2 5 | 9 3 4 | 1 6 7 || 9 6 4 | 7 2 1 | 8 3 5 |+-------+-------+-------+| 6 9 7 | 4 1 2 | 5 8 3 || 5 8 2 | 3 9 7 | 6 1 4 || 4 1 3 | 5 8 6 | 7 9 2 |+-------+-------+-------+146279358258143976379658241731865429825934167964721835697412583582397614413586792`

Two (valency 3) minimal UA sets and thier "alternates".
The minimal UA's are on the left, and thier alternates on the right.

Code: Select all
`+-------+-------+-------+  +-------+-------+-------+  +-------+-------+-------+| . . 6 | . . 9 | . . . |  | . . 9 | . . 6 | . . . |  | . . 9 | . . 6 | . . . || 2 . . | . . 3 | 9 . . |  | 3 . . | . . 9 | 2 . . |  | 3 . . | . . 9 | 2 . . || 3 . 9 | 6 . . | 2 . . |  | 2 . 6 | 3 . . | 9 . . |  | 6 . 2 | 3 . . | 9 . . |+-------+-------+-------+  +-------+-------+-------+  +-------+-------+-------+| . . . | . . . | . . . |  | . . . | . . . | . . . |  | . . . | . . . | . . . || . . . | . . . | . . . |  | . . . | . . . | . . . |  | . . . | . . . | . . . || . . . | . . . | . . . |  | . . . | . . . | . . . |  | . . . | . . . | . . . |+-------+-------+-------+  +-------+-------+-------+  +-------+-------+-------+| 6 . . | 4 . . | . . . |  | 4 . . | 6 . . | . . . |  | 4 . . | 6 . . | . . . || . . 2 | 3 . . | . . 4 |  | . . 3 | 4 . . | . . 2 |  | . . 3 | 4 . . | . . 2 || 4 . 3 | . . 6 | . . 2 |  | 6 . 2 | . . 3 | . . 4 |  | 2 . 6 | . . 3 | . . 4 |+-------+-------+-------+  +-------+-------+-------+  +-------+-------+-------++-------+-------+-------+  +-------+-------+-------+  +-------+-------+-------+| . . 6 | 2 . . | . . 8 |  | . . 8 | 6 . . | . . 2 |  | . . 8 | 6 . . | . . 2 || . . 8 | . . 3 | . . . |  | . . 3 | . . 8 | . . . |  | . . 3 | . . 8 | . . . || 3 . . | 6 . 8 | 2 . . |  | 6 . . | 2 . 3 | 8 . . |  | 6 . . | 3 . 2 | 8 . . |+-------+-------+-------+  +-------+-------+-------+  +-------+-------+-------+| . . . | . . . | . . . |  | . . . | . . . | . . . |  | . . . | . . . | . . . || . . . | . . . | . . . |  | . . . | . . . | . . . |  | . . . | . . . | . . . || . . . | . . . | 8 . 5 |  | . . . | . . . | 5 . 8 |  | . . . | . . . | 5 . 8 |+-------+-------+-------+  +-------+-------+-------+  +-------+-------+-------+| 6 . . | . . 2 | 5 . . |  | 5 . . | . . 6 | 2 . . |  | 5 . . | . . 6 | 2 . . || 5 . . | 3 . . | . . . |  | 3 . . | 5 . . | . . . |  | 3 . . | 5 . . | . . . || . . 3 | 5 . 6 | . . 2 |  | . . 6 | 3 . 2 | . . 5 |  | . . 6 | 2 . 3 | . . 5 |+-------+-------+-------+  +-------+-------+-------+  +-------+-------+-------+`

Note: There are UA4's hidden in the alternates.
The alternates are UAs, but not minimal UA's for the corresponding "replacement" grids.
Last edited by blue on Sat Jun 29, 2019 8:04 am, edited 1 time in total.
blue

Posts: 877
Joined: 11 March 2013

### Re: UA's and Isomorphism

Hi, blue!
blue wrote:Here's a proper definition.

S : a solution grid
U : a subgrid of S
P := S - U ... the puzzle produced from S, by removing the "clues" in U

If P has >= 2 solutions, then U is an unavoidable set (of S).
P has S as a solution, obviously.
If every other solution differs from S in every cell of U, then U is a minimal unavoidable set.

The valency of U, is defined as the number of solutions for P.
Most minimal UA's (of moderate size, at least) have valency 2.

I've found important link to Red Ed's strongly/weakly minimal UA sets definition.

If all solutions of P are minimal unavoidable sets (in their solution grids), unavoidable set U is strongly minimal, otherwise unavoidable set U is weakly minimal.

Usually strongly minimal unavoidable set has valency 2, but nobody proved, that strongly minimal unavoidable sets with valency 3+ don't exist. When unavoidable set U is weakly minimal, all other solutions usually are not minimal unavoidable sets (in their solution grids), but nobody proved, that all other solutions always are not minimal unavoidable sets.

Serg

[Edited. I corrected errors in my definitions.]
[Edited2. I was wrong in weakly minimal UA set definition. All my text was corrected. Thanks to blue for pointing to my error.]
Last edited by Serg on Sat Jun 29, 2019 5:12 pm, edited 2 times in total.
Serg
2018 Supporter

Posts: 652
Joined: 01 June 2010
Location: Russia

### Re: UA Set for a Given Grid

Wow!

I love it here, but the peer review process can be a little bit medieval at times? (short, sharp, and brutal!)

Ok, so my methodology is execrable (Mladen), my definitions are wrong (blue), and now there appears to be some question about the underlying terminology / definitions (Serg) …

I call that business as usual!

Let me address blue's points first:

• the UA's I am dealing with in the grid T above, and which are of particular interest to me, are those with valency 2 only
• I was using minimal in the same sense as "minimal puzzles", viz. to indicate that U has no (proper) subsets that are UA's.

I mistakenly assumed that by this definition of minimality, the valency of 2 was implied.

Now that I think about it, my confusion of definitions also comes from an assumption I made when I first encountered the term valency in this forum. I always assumed that it was just another name for degree (the number of clues required to be added to P to fix the unique solution S).

By blue's definition, minimality is the property that every grid in A differs from S in every cell position defined by U. Does this condition suffice to ensure that U is of degree 1? Are minimal UA's of higher degree just unions of degree 1 UA's?
Last edited by Mathimagics on Sat Jun 29, 2019 4:48 am, edited 1 time in total.

Mathimagics
2017 Supporter

Posts: 1329
Joined: 27 May 2015
Location: Canberra

### Re: UA Set for a Given Grid

Definition: MUA ("Mathimagics UA")

A UA that is minimal, and has no minimal UA as a proper subset, and has valency 2, and has degree 1.

I retain the rights to add/remove any properties at any time.

========================================================

Serg: I need some time to work out the Red Ed stuff and see what the real difference is between his and blue's definitions, to understand what you've posted.

blue: thanks for those valency 3 examples, they were useful.

Cheers!
MM

Mathimagics
2017 Supporter

Posts: 1329
Joined: 27 May 2015
Location: Canberra

### Re: UA's and Isomorphism

Hi Serg,

You're right, of course. I've edited the original post.
As soon as I got out the door and headed down the road, I remembered the proper definitions for strong-vs-weak minimals

The rest of what I wrote is correct, in the sense that if it doesn't match the "original defintion" (wherever that might be found (?)), it's "equivalent" to the original definition. I tried to frame it in a way that conformed to Mathimagics' notion of "P := S - U", and it's solutions.
[ The (set of) "permutations of U (with the same footprint as U)" mentioned elsewhere, and the set of "solutions to P, restricted to the cells in U", are (of course) the same sets. ]

Serg wrote:
blue wrote:Here's a proper definition.
(...)

I think UA set definition should be more complicated (see original Red Ed's definition).

Let's call solutions of P unavoidable set permutations (in accordance with Red Ed's terminology). If every cell of unavoidable set's permutation contains unique value (comparing it with all other permutations of considered unavoidable set), this permutation is called minimal. If an unavoidable set contains at least one minimal permutation, such unavoidable set called minimal. If all unavoidable set's permutations are minimal, unavoidable set is strongly minimal, otherwise unavoidable set is weakly minimal.

Everything seems correct, except the part that I underlined.

In the example(s) with valency 3, if S = (P + U), S2 = (P + V), and S3 = (P + W) are the 3 solutions to P, then V and W are unavoidable sets in S2 and S3 (respectfully). Neither one is a minimal UA for its respective grid, though, since each of them contains a (smaller) U4.

On the other hand, {U,V,W} is the set of permutations for U, and for V and W as well, and that set includes U, which is minimal.
The "contains at least one minimal permutation" concept, then ... as applied to V, for example ... isn't a guarantee that V itself, is minimal (in the usual sense). Check the "BTW:" at the bottom of this post, if that doesn't make sense.

Serg wrote:Usually strongly minimal unavoidable set has valency 2 (contains 2 permutations), but nobody proved, that strongly minimal unavoidable sets with valency 3+ don't exist. Usually weakly minimal unavoidable set contains 1 minimal permutation only, but nobody proved, that it cannot contain 2+ minimal permutations.

All true, AFAIK ... no "non-existence" proofs, and no evidence to contradict the non-existence hypotheses.

--

BTW: You do understand (please, I hope) ... that above, {U,V,W} is a just set of permutations (of a single "seed", in principle) ... and that only U,V or W, individually, could be an "unavoidable set" ... minimal, strong, weak, or otherwise ?

You use, twice, phrases like "contains a minimal permutation", where "has a minimal permuation" should appear instead.
For example: "Usually weakly minimal unavoidable set contains 1 minimal permutation only".
It should be: "Usually [a] weakly minimal unavoidable set has 1 minimal permutation only" ... that being the set itself.
blue

Posts: 877
Joined: 11 March 2013

### Re: UA Set for a Given Grid

I'm glad we appear to have got all of our definitions edited and everything nailed down …

However, I have to say that I do NOT like calling something a PERMUTATION that is really a SET … it is really confusing and, IMHO, totally unnecessary.

It is of course desirable to have some convenient term to label a particular set when describing properties, but I think Ed picked the worst possible one of all, since individual Sudoku grids are in a very real sense permutations, but you guys know this already ...

Perhaps "valency set"? Let V = V(S,U) be the set of solution grids for S and U. "Valency" is thus |V|

Simple. We might use "v-set" as shorthand …

Terms like "permuted unavoidables" (which I see in that thread) sound to me like medical conditions (a particularly horrid one), or one of those obscure clues you used to see in crosswords, like "voided escutcheon" …

Mathimagics
2017 Supporter

Posts: 1329
Joined: 27 May 2015
Location: Canberra

### Re: UA Set for a Given Grid

Hi Mathimagics,

Mathimagics wrote:
• I was using minimal in the same sense as "minimal puzzles", viz. to indicate that U has no (proper) subsets that are UA's.
I mistakenly assumed that by this definition of minimality, the valency of 2 was implied.

Good ... that's another, possibly the original definition ... for a "minimal" UA.
Valency 2 isn't implied though.

Now that I think about it, my confusion of definitions also comes from an assumption I made when I first encountered the term valency in this forum. I always assumed that it was just another name for degree (the number of clues required to be added to P to fix the unique solution S).

By blue's definition, minimality is the property that every grid in A differs from S in every cell position defined by U. Does this condition suffice to ensure that U is of degree 1? Are minimal UA's of higher degree just unions of degree 1 UA's?

The answer to the first question is "yes" : if a single clue from U is added to P, then its solution set is reduced to just {S}, since every other solution to (original) P, differed from S in that cell.

It's late for me ... early in the morning, actually ... and I need time to think about the 2nd question.

From the first answer, it's clear that the set couldn't be a "minimal UA" in the usual sense.
I'm assuming, then, that by "minimal" and "of higher degree", you mean that removing any cell from U (or equivalently, adding any clue from U, to P), would reduce its degree ... reducing it by one (and no more), necessarily.
blue

Posts: 877
Joined: 11 March 2013

### Re: UA's and Isomorphism

blue wrote:The rest of what I wrote is correct, in the sense that if it doesn't match the "original defintion" (wherever that might be found (?)), it's "equivalent" to the original definition.

Mathimagics wrote:I'm glad we appear to have got all of our definitions edited and everything nailed down

Hi,

In late 2010 I opened topic in the former Sudoku Programmers forum "Unavoidable Sets: Definition, Properties, Classification".
We collected several definitions and references to the original posts. Like here, definitions were reconsidered by their author (JPF and Red Ed). For several times. Provoked by Serg and Blue.
From the 3 pages, I saved the last 2. The starting post, where the essence was accumulated, is lost.

Later I can re-post the posts from pages 2 and 3.

It was fun that Ed Russel, starting with
This thread's going nowhere. The equivalent definitions of unavoidable set (originally: exchangeable set) were done long ago; let's not rehash them. Is the aim to collect together or extend some actual results? Then edit the top post to list open & closed questions, with links as appropriate to the most recent information on each.

edited his own definitions, and finally wrote
For those keen on developing theorems, it would be best to start with strongly minimal unavoidables. Their properties are much nicer and (hello, MD) you can probably get away with studying just their footprints.

That was far before Minimal Unavoidable Sets with 145 permutations were discovered.

@Blue: in the same archive I found your short topic on "Grids with minimal UA18s for all 2-row,2-col,2-digit UA sets". I can send you for reposting here, if you want.
dobrichev
2016 Supporter

Posts: 1745
Joined: 24 May 2010

Next