## Need help in some probability calculations

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

### Re: Need help in some probability calculations

Back to the point. Here is what I did to a first approximation.
I wrote:Is it better to choose the Maximal Disjoint Set for the mapping, or some non-maximal but with more small sized UA? [Issue 1]
If there are more than one similar Disjoint Set candidates, how to weight them and choose the best one? [Issue 2]
How the UA of equal size to be ordered while determining the mapping? [Issue 3]
How the cells within each UA to be ordered? [Issue 4]
How the remaining cells (these that are not members of the chosen Disjoint Set) to be ordered? [Issue 5]

1) Use one of the Maximal DJ Sets
2) Use one of the sets having minimal combinations, i.e. minimal product of UA sizes.
3) Each UA is rated by the number of distinct combinations of disjoint sets. The number of DJ combinations forming maximal cliques has top importance. The number of DJ combinations forming max-1 clique has lower importance, etc. The UA with higher rating is placed at right. (Only UA of same size are reordered in this way, these with less size are at right.)
4) One cell from the UA is removed. The rest of the cells are rated as in 3). The cell resulting in higher rate of the complementary set is placed at right.
5) Same as in 4).
Rating with much UA sets is memory consuming. Initially I used UA of size up to 14 (which definitely will kill the memory for some of the grids). Then reduced the size to 11, and surprisingly this gave better results. Better in later puzzle enuneration, not only in rating calculation. Size matters.

The overhead is ~ 1 minute.

Below is an example log for the grid with 20 17's, scanning for 17.
Hidden Text: Show
Code: Select all
`Loaded 4824 UA.Remapping the Grid...Finding Maximal Cliques using 722 unavoidable sets of size up to 14.MCN=12, Maximal Cliques found=1Clique 000, 04 04 04 04 04 06 06 06 06 06 08 14 = 891813888 combinations.Choosing Clique 0.Reordering 5 members of size 6 within partition 1.1=76,2=1269,3=6958,4=15216,5=15210,6=7880,7=2482,8=582,9=98,10=8,1=85,2=1465,3=8031,4=17903,5=19708,6=12886,7=5747,8=1739,9=314,10=25,1=86,2=1522,3=8549,4=20196,5=24451,6=17559,7=8218,8=2453,9=419,10=31,1=97,2=2024,3=13089,4=33246,5=38128,6=22556,7=8240,8=2047,9=330,10=25,1=95,2=1933,3=12140,4=28583,5=28664,6=13874,7=3753,8=714,9=109,10=9,        Placing member 0 at position 4. (Note: read this as "swap members 0 and 4". Cells are placed, members are swapped)        Placing member 0 at position 3.        Placing member 1 at position 2.        Placing member 0 at position 1.Reordering 5 members of size 4 within partition 0.1=109,2=2412,3=15750,4=39986,5=48528,6=32290,7=12996,8=3222,9=469,10=31,1=98,2=2117,3=14306,4=37375,5=44596,6=28209,7=11060,8=2815,9=437,10=31,1=107,2=2396,3=16257,4=42684,5=50788,6=30745,7=11133,8=2698,9=424,10=31,1=110,2=2468,3=15957,4=38926,5=44704,6=29092,7=11853,8=3051,9=466,10=31,1=105,2=2381,3=16284,4=42507,5=50462,6=31303,7=11559,8=2870,9=445,10=31,        Placing member 2 at position 4.        Placing member 1 at position 3.        Leaving member 2 at position 2.        Leaving member 1 at position 1.Reordering cells within each member.Reordering 4 cells within member 0.1=119,2=2887,3=20109,4=52804,5=63981,6=41107,7=15312,8=3444,9=473,10=31,1=118,2=2874,3=20821,4=57781,5=73215,6=47333,7=16912,8=3648,9=481,10=31,1=119,2=2929,3=21268,4=58118,5=71974,6=45605,7=16284,8=3545,9=478,10=31,1=116,2=2769,3=19292,4=50240,5=60201,6=38438,7=14521,8=3359,9=472,10=31,        Placing cell 1 at position 3.        Placing cell 2 at position 2.        Placing cell 0 at position 1.        Placing cell 3 at position 0.Reordering 4 cells within member 1.1=121,2=2980,3=20424,4=51007,5=57861,6=36088,7=13861,8=3374,9=492,10=31,1=118,2=2865,3=20195,4=53031,5=63029,6=39587,7=14609,8=3390,9=481,10=31,1=120,2=2982,3=21339,4=56393,5=67114,6=42125,7=15682,8=3675,9=514,10=31,1=117,2=2862,3=20482,4=54183,5=64474,6=40868,7=15409,8=3611,9=514,10=32,        Placing cell 3 at position 3.        Placing cell 2 at position 2.        Placing cell 0 at position 1.        Placing cell 1 at position 0.Reordering 4 cells within member 2.1=112,2=2716,3=19856,4=54933,5=69200,6=45268,7=16635,8=3749,9=511,10=32,1=119,2=2955,3=21594,4=58874,5=70794,6=43243,7=15428,8=3671,9=544,10=37,1=115,2=2874,3=21380,4=58954,5=70047,6=40758,7=13543,8=3048,9=449,10=31,1=109,2=2570,3=18103,4=47436,5=55260,6=33093,7=11786,8=2878,9=445,10=31,        Placing cell 1 at position 3.        Placing cell 0 at position 2.        Placing cell 2 at position 1.        Placing cell 3 at position 0.Reordering 4 cells within member 3.1=111,2=2686,3=19562,4=53399,5=64271,6=39157,7=14071,8=3272,9=474,10=32,1=104,2=2402,3=17605,4=50666,5=66630,6=44446,7=16614,8=3687,9=496,10=33,1=109,2=2573,3=18591,4=50204,5=59725,6=36615,7=13526,8=3228,9=474,10=32,1=114,2=2760,3=20106,4=54481,5=65133,6=39963,7=14845,8=3621,9=554,10=40,        Placing cell 3 at position 3.        Placing cell 1 at position 2.        Placing cell 0 at position 1.        Placing cell 2 at position 0.Reordering 4 cells within member 4.1=120,2=2951,3=21138,4=56172,5=65237,6=37971,7=13263,8=3128,9=472,10=31,1=120,2=3002,3=21922,4=59089,5=70160,6=42176,7=15086,8=3552,9=541,10=37,1=114,2=2815,3=21470,4=63260,5=83998,6=55251,7=19646,8=4206,9=576,10=39,1=116,2=2843,3=20951,4=59341,5=75020,6=46098,7=15530,8=3312,9=456,10=31,        Placing cell 2 at position 3.        Placing cell 1 at position 2.        Placing cell 0 at position 1.        Placing cell 3 at position 0.Reordering 6 cells within member 5.1=94,2=1860,3=11193,4=27188,5=32402,6=22139,7=9642,8=2696,9=443,10=32,1=93,2=1821,3=11537,4=30652,5=39599,6=27578,7=11543,8=3048,9=473,10=32,1=96,2=1898,3=11685,4=29257,5=35953,6=24832,7=10724,8=2956,9=474,10=33,1=94,2=1780,3=10407,4=24891,5=29715,6=20592,7=9198,8=2637,9=434,10=31,1=91,2=1698,3=9693,4=22386,5=25964,6=18010,7=8283,8=2458,9=419,10=31,1=93,2=1807,3=10785,4=25454,5=29375,6=19670,7=8659,8=2494,9=420,10=31,        Placing cell 2 at position 5.        Placing cell 1 at position 4.        Placing cell 0 at position 3.        Placing cell 3 at position 2.        Placing cell 5 at position 1.        Placing cell 4 at position 0.Reordering 6 cells within member 6.1=102,2=2230,3=14856,4=37960,5=42805,6=24504,7=8622,8=2082,9=330,10=25,1=100,2=2197,3=15246,4=42046,5=52176,6=32499,7=11783,8=2836,9=443,10=32,1=100,2=2115,3=13772,4=35041,5=40170,6=23653,7=8511,8=2084,9=332,10=25,1=101,2=2212,3=14941,4=38772,5=43962,6=24856,7=8594,8=2060,9=330,10=25,1=103,2=2312,3=16032,4=41917,5=47562,6=26972,7=9102,8=2135,9=336,10=25,1=105,2=2356,3=15729,4=40437,5=46393,6=26982,7=9551,8=2313,9=361,10=25,        Placing cell 1 at position 5.        Placing cell 5 at position 4.        Placing cell 4 at position 3.        Placing cell 2 at position 2.        Placing cell 0 at position 1.        Placing cell 3 at position 0.Reordering 6 cells within member 7.1=96,2=1900,3=11321,4=26129,5=27874,6=16480,7=6599,8=1867,9=322,10=25,1=90,2=1703,3=10360,4=25428,5=29767,6=19131,7=7750,8=2075,9=339,10=26,1=96,2=1853,3=10995,4=25908,5=29816,6=20347,7=9569,8=3165,9=673,10=79,11=4,1=92,2=1722,3=10168,4=24189,5=27628,6=17655,7=7274,8=2007,9=335,10=25,1=88,2=1559,3=8619,4=19146,5=20835,6=13424,7=5913,8=1770,9=316,10=25,1=94,2=1879,3=11600,4=27937,5=31726,6=20820,7=9334,8=2884,9=547,10=51,11=1,        Placing cell 2 at position 5.        Placing cell 5 at position 4.        Placing cell 1 at position 3.        Placing cell 3 at position 2.        Placing cell 0 at position 1.        Placing cell 4 at position 0.Reordering 6 cells within member 8.1=101,2=2168,3=14128,4=34032,5=34615,6=16781,7=4430,8=784,9=114,10=9,1=99,2=2136,3=14455,4=37074,5=40964,6=22108,7=6990,8=1607,9=264,10=21,1=105,2=2328,3=15529,4=37937,5=38616,6=18475,7=4744,8=824,9=114,10=9,1=98,2=2086,3=13838,4=34802,5=37563,6=19427,7=5553,8=1109,9=165,10=13,1=103,2=2293,3=15734,4=40678,5=45425,6=24575,7=7230,8=1379,9=193,10=14,1=107,2=2387,3=15995,4=39573,5=41546,6=21146,7=5927,8=1168,9=196,10=22,11=1,        Placing cell 5 at position 5.        Placing cell 1 at position 4.        Placing cell 4 at position 3.        Placing cell 3 at position 2.        Placing cell 2 at position 1.        Placing cell 0 at position 0.Reordering 6 cells within member 9.1=86,2=1586,3=9346,4=21315,5=21732,6=11178,7=3361,8=752,9=122,10=10,1=83,2=1499,3=8542,4=18678,5=18017,6=8732,7=2577,8=584,9=98,10=8,1=82,2=1497,3=8964,4=21672,5=24465,6=14149,7=4695,8=1075,9=177,10=15,1=84,2=1549,3=9390,4=22750,5=24834,6=13279,7=4034,8=914,9=153,10=12,1=86,2=1603,3=9418,4=21335,5=21433,6=10816,7=3151,8=684,9=111,10=9,1=85,2=1553,3=9040,4=20166,5=19676,6=9609,7=2868,8=641,9=102,10=8,        Placing cell 2 at position 5.        Placing cell 3 at position 4.        Placing cell 0 at position 3.        Placing cell 4 at position 2.        Placing cell 5 at position 1.        Placing cell 1 at position 0.Reordering 8 cells within member 10.1=73,2=1036,3=4649,4=8761,5=8627,6=5347,7=2280,8=663,9=116,10=9,1=77,2=1220,3=6102,4=12207,5=11845,6=6742,7=2574,8=693,9=117,10=9,1=79,2=1240,3=5991,4=11983,5=12352,6=7720,7=3201,8=885,9=144,10=10,1=77,2=1169,3=5629,4=11325,5=11571,6=7001,7=2796,8=763,9=130,10=10,1=76,2=1133,3=5408,4=10751,5=10739,6=6351,7=2490,8=680,9=116,10=9,1=72,2=1030,3=4819,4=9612,5=9882,6=6071,7=2453,8=676,9=116,10=9,1=75,2=1127,3=5464,4=11043,5=11128,6=6539,7=2558,8=702,9=120,10=9,1=78,2=1230,3=6115,4=12512,5=12963,6=8095,7=3372,8=955,9=163,10=13,        Placing cell 7 at position 7.        Placing cell 2 at position 6.        Placing cell 3 at position 5.        Placing cell 6 at position 4.        Placing cell 1 at position 3.        Placing cell 4 at position 2.        Placing cell 5 at position 1.        Placing cell 0 at position 0.Reordering 14 cells within member 11.1=59,2=663,3=2367,4=3810,5=3340,6=1903,7=837,8=285,9=72,10=12,11=1,1=60,2=693,3=2530,4=3992,5=3390,6=1905,7=837,8=285,9=72,10=12,11=1,1=60,2=691,3=2532,4=4029,5=3425,6=1920,7=839,8=285,9=72,10=12,11=1,1=59,2=664,3=2393,4=3833,5=3335,6=1901,7=837,8=285,9=72,10=12,11=1,1=59,2=689,3=2644,4=4457,5=3919,6=2158,7=907,8=297,9=73,10=12,11=1,1=58,2=643,3=2309,4=3753,5=3316,6=1899,7=837,8=285,9=72,10=12,11=1,1=58,2=643,3=2309,4=3753,5=3316,6=1899,7=837,8=285,9=72,10=12,11=1,1=61,2=726,3=2692,4=4233,5=3510,6=1932,7=840,8=285,9=72,10=12,11=1,1=58,2=643,3=2309,4=3753,5=3316,6=1899,7=837,8=285,9=72,10=12,11=1,1=58,2=643,3=2309,4=3753,5=3316,6=1899,7=837,8=285,9=72,10=12,11=1,1=59,2=681,3=2595,4=4387,5=3822,6=2092,7=882,8=293,9=73,10=12,11=1,1=60,2=702,3=2634,4=4233,5=3524,6=1925,7=838,8=285,9=72,10=12,11=1,1=59,2=672,3=2447,4=3903,5=3359,6=1903,7=837,8=285,9=72,10=12,11=1,1=59,2=664,3=2402,4=3876,5=3371,6=1904,7=837,8=285,9=72,10=12,11=1,        Placing cell 4 at position 13.        Placing cell 10 at position 12.        Placing cell 7 at position 11.        Placing cell 2 at position 10.        Placing cell 11 at position 9.        Placing cell 1 at position 8.        Placing cell 13 at position 7.        Placing cell 12 at position 6.        Placing cell 0 at position 5.        Placing cell 3 at position 4.        Placing cell 5 at position 3.        Placing cell 6 at position 2.        Placing cell 8 at position 1.        Placing cell 9 at position 0.Reordering the rest 9 cells.1=54,2=682,3=3062,4=6151,5=6566,6=4382,7=2134,8=797,9=216,10=37,11=3,1=50,2=594,3=2664,4=5584,5=6307,6=4419,7=2196,8=818,9=219,10=37,11=3,1=55,2=719,3=3378,4=7142,5=7993,6=5436,7=2556,8=893,9=230,10=38,11=3,1=60,2=803,3=3794,4=7919,5=8493,6=5510,7=2585,8=934,9=245,10=40,11=3,1=57,2=726,3=3282,4=6695,5=7386,6=5153,7=2528,8=915,9=238,10=39,11=3,1=52,2=639,3=2929,4=6213,5=7066,6=4968,7=2459,8=915,9=244,10=40,11=3,1=50,2=604,3=2726,4=5654,5=6224,6=4238,7=2098,8=792,9=216,10=37,11=3,1=48,2=547,3=2365,4=4847,5=5506,6=3995,7=2068,8=791,9=216,10=37,11=3,1=51,2=612,3=2704,4=5464,5=5984,6=4159,7=2090,8=791,9=216,10=37,11=3,        Placing cell 3 at position 8.        Placing cell 5 at position 7.        Placing cell 4 at position 6.        Placing cell 2 at position 5.        Placing cell 1 at position 4.        Placing cell 0 at position 3.        Placing cell 6 at position 2.        Placing cell 8 at position 1.        Placing cell 7 at position 0.00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80Mapping iterator to grid76 03 75 04 20 19 55 56 67 66 48 49 39 12 13 40 71 16 17 70 57 58 31 21 22 30 41 32 36 45 51 33 64 01 47 02 65 46 54 63 69 72 60 78 05 15 14 00 09 06 10 38 37 11 73 29 28 74 53 52 43 35 26 07 79 80 08 62 25 44 61 34 68 77 59 18 23 24 42 50 27Mapping grid to iterator47 33 35 01 03 44 49 63 66 48 50 53 13 14 46 45 17 18 75 05 04 23 24 76 77 68 62 80 56 55 25 22 27 31 71 61 28 52 51 12 15 26 78 60 69 29 37 34 10 11 79 30 59 58 38 06 07 20 21 74 42 70 67 39 32 36 09 08 72 40 19 16 41 54 57 02 00 73 43 64 65maxPositionLimitsByUA04 08 12 16 20 26 32 38 44 50 58 72 81 81 81 81 81Using 2000 UA, 1050 of size up to 15, and leftmost 950 regardless of the size.01.2306% at 0.002h,Checked=16,Found=0,ETTF=0.165h01.6638% at 0.004h,Checked=32,Found=0,ETTF=0.210h02.3217% at 0.005h,Checked=35,Found=0,ETTF=0.209h03.1863% at 0.007h,Checked=38,Found=0,ETTF=0.208h04.4240% at 0.008h,Checked=65,Found=0,ETTF=0.183h04.6303% at 0.010h,Checked=69,Found=0,ETTF=0.202h05.0210% at 0.011h,Checked=74,Found=0,ETTF=0.216h05.3579% at 0.013h,Checked=81,Found=0,ETTF=0.227h06.3319% at 0.014h,Checked=140,Found=0,ETTF=0.214h07.5699% at 0.016h,Checked=156,Found=0,ETTF=0.197h08.2260% at 0.018h,Checked=187,Found=0,ETTF=0.198h08.9391% at 0.019h,Checked=200,Found=0,ETTF=0.196h09.9751% at 0.021h,Checked=224,Found=0,ETTF=0.188h10.9103% at 0.022h,Checked=227,Found=0,ETTF=0.181h11.7411% at 0.024h,Checked=257,Found=0,ETTF=0.177h12.8531% at 0.025h,Checked=284,Found=0,ETTF=0.169h13.8183% at 0.026h,Checked=291,Found=0,ETTF=0.163h15.5420% at 0.028h,Checked=302,Found=0,ETTF=0.150h17.0734% at 0.029h,Checked=310,Found=0,ETTF=0.140h18.2242% at 0.030h,Checked=343,Found=0,ETTF=0.135h20.4501% at 0.031h,Checked=366,Found=0,ETTF=0.122h21.8463% at 0.033h,Checked=396,Found=0,ETTF=0.117h25.6436% at 0.034h,Checked=428,Found=0,ETTF=0.099h26.8035% at 0.036h,Checked=472,Found=0,ETTF=0.098h28.1707% at 0.037h,Checked=535,Found=0,ETTF=0.096h30.2114% at 0.039h,Checked=566,Found=0,ETTF=0.090h32.9156% at 0.040h,Checked=582,Found=0,ETTF=0.082h34.5835% at 0.042h,Checked=608,Found=0,ETTF=0.079h36.9129% at 0.043h,Checked=628,Found=0,ETTF=0.074h41.1386% at 0.045h,Checked=651,Found=0,ETTF=0.065h42.4267% at 0.047h,Checked=661,Found=0,ETTF=0.064h43.7948% at 0.049h,Checked=756,Found=0,ETTF=0.062h45.9699% at 0.050h,Checked=813,Found=0,ETTF=0.059h49.6342% at 0.051h,Checked=917,Found=0,ETTF=0.052h51.5815% at 0.053h,Checked=989,Found=0,ETTF=0.050h51.7955% at 0.054h,Checked=1023,Found=0,ETTF=0.050h52.1131% at 0.055h,Checked=1030,Found=0,ETTF=0.051h52.7455% at 0.057h,Checked=1032,Found=0,ETTF=0.051h53.3986% at 0.058h,Checked=1086,Found=0,ETTF=0.050h53.6243% at 0.059h,Checked=1098,Found=0,ETTF=0.051h54.1117% at 0.060h,Checked=1155,Found=0,ETTF=0.051h54.7306% at 0.061h,Checked=1163,Found=0,ETTF=0.051h55.5789% at 0.062h,Checked=1172,Found=0,ETTF=0.050h56.3869% at 0.064h,Checked=1192,Found=0,ETTF=0.049h57.5618% at 0.065h,Checked=1218,Found=0,ETTF=0.048h50420000000004003010000000006007300000000050100000000003000007000050040080002000050420000000004003012000000006007300000000050100000000003000007000050040080000000050420000000004003010000000006007300000000050100000000003000007000058040080000000050420000000004003210000000006007300000000050100000000003000007000050040080000000050420000000004003010000000006007300000000050100000000003000007000050042080000000050420000000004003010006000006007300000000050100000000003000007000050040080000000050420000000004003010000000006007300000000050120000000003000007000050040080000000050420000000004003010000000006007320000000050100000000003000007000050040080000000059420000000004003010000000006007300000000050100000000003000007000050040080000000050420000000004003010000000006007300000000050100000000003000087000050040080000000050420000008004003010000000006007300000000050100000000003000007000050040080000000050420000000004003010000000006007300000000050100000009003000007000050040080000000050420000000004003010000000006007300800000050100000000003000007000050040080000000059020000000004003010000000406007300000000050100000000003000007000050040080000000050420008000004003010000000006007300000000050100000000003000007000050040080000000050420000000004003010000000006007300000000050100000000003000007000050040080000000958.7101% at 0.066h,Checked=1355,Found=16,ETTF=0.046h60.1690% at 0.067h,Checked=1382,Found=16,ETTF=0.044h50420000000004003010000800006007300000000050100000000003000007000050040080000000061.9350% at 0.068h,Checked=1401,Found=17,ETTF=0.042h50420000000004003010000090006007300000000050100000000003000007000050040080000000064.6045% at 0.070h,Checked=1446,Found=18,ETTF=0.038h65.9132% at 0.071h,Checked=1460,Found=18,ETTF=0.037h68.4109% at 0.072h,Checked=1477,Found=18,ETTF=0.033h74.0921% at 0.073h,Checked=1498,Found=18,ETTF=0.026h78.2322% at 0.074h,Checked=1590,Found=18,ETTF=0.021h50420000000004003010000000006007300000000050100000600003000007000050040080000000080.9235% at 0.075h,Checked=1618,Found=19,ETTF=0.018h81.6487% at 0.077h,Checked=1623,Found=19,ETTF=0.017h82.0620% at 0.078h,Checked=1643,Found=19,ETTF=0.017h82.8156% at 0.079h,Checked=1671,Found=19,ETTF=0.016h84.0644% at 0.080h,Checked=1807,Found=19,ETTF=0.015h85.8939% at 0.081h,Checked=1847,Found=19,ETTF=0.013h87.9816% at 0.082h,Checked=1883,Found=19,ETTF=0.011h90.6156% at 0.084h,Checked=2006,Found=19,ETTF=0.009h93.3752% at 0.085h,Checked=2053,Found=19,ETTF=0.006h93.8757% at 0.086h,Checked=2080,Found=19,ETTF=0.006h94.9878% at 0.087h,Checked=2116,Found=19,ETTF=0.005h50420000000004003010000000096007300000000050100000000003000007000050040080000000098.3968% at 0.088h,Checked=2185,Found=20,ETTF=0.001hChecked for 17, generated 2211 puzzles, found 20 valid.Iterations done in 317.859 secondsTotal time 387.828 seconds`

Now I am crunching the worst grid - no U4, 3xU6, two of them with common clue.

Hidden Text: Show
Code: Select all
`123456789456789132789213645275941368638527914941638257394175826517862493862394571UA sets{11,14,17,21,24,27}{12,14,18,32,34,38}{13,16,23,26,33,36}{11,12,41,42,43,81,82,83}....3 UA with valency of 7{15,17,22,23,24,25,29,31,32,34,37,39,41,42,49,51,53,54,55,56,66,67,69,75,76,79,81,84,85,86,92,97}{15,16,17,22,23,24,25,29,31,32,34,37,39,41,42,49,51,53,54,55,56,66,67,69,76,79,81,84,85,86,92,97}{11,12,16,17,19,24,26,27,29,33,35,37,41,44,46,48,55,56,57,58,63,64,67,69,72,78,79,83,85,86,88,93,98,99}MCN=8, Maximal Cliques found=5Clique 0{12,14,18,32,34,38} (6){13,16,23,26,33,36} (6){24,25,73,75,77,83,84,87} (8){27,28,42,46,47,52,56,58} (8){41,45,49,53,55,59,91,93} (8){64,65,74,79,85,89,94,99} (8){11,15,17,31,35,39,68,69,97,98} (10){21,22,61,62,72,76,78,81,86,88} (10)combinations = 14745600Clique 1{12,14,18,32,34,38} (6){13,16,23,26,33,36} (6){24,25,73,75,77,83,84,87} (8){27,28,42,46,47,52,56,58} (8){41,45,49,53,55,59,91,93} (8){64,65,82,85,89,92,94,99} (8){11,15,17,31,35,39,68,69,97,98} (10){21,22,61,62,72,76,78,81,86,88} (10)combinations = 14745600Clique 2{12,14,18,32,34,38} (6){41,47,52,57,61,67,71,72} (8){43,46,54,58,63,68,74,76} (8){55,56,75,78,83,86,93,98} (8){64,65,82,85,89,92,94,99} (8){21,23,51,53,73,77,81,87,91,97} (10){25,26,42,45,49,62,66,69,95,96} (10){11,13,15,16,17,19,31,33,35,36,37,39} (12)combinations = 29491200Clique 3{13,16,23,26,33,36} (6){11,14,21,24,31,35,74,75} (8){12,15,22,29,34,39,54,55} (8){17,18,67,68,77,78,97,98} (8){41,43,73,76,81,86,93,96} (8){42,46,49,63,66,69,82,83} (8){27,28,37,38,47,48,57,58,87,88} (10){51,52,64,65,71,79,85,89,92,94} (10)combinations = 19660800Clique 4{13,16,23,26,33,36} (6){11,14,21,24,31,35,74,75} (8){12,15,22,29,34,39,54,55} (8){17,18,67,68,77,78,97,98} (8){41,43,73,76,81,86,93,96} (8){42,46,53,56,63,66,82,83} (8){27,28,37,38,47,48,57,58,87,88} (10){51,52,64,65,71,79,85,89,92,94} (10)combinations = 19660800Selected Clique 0Using 2000 UA, 1839 of size up to 15, and leftmost 161 regardless of the size.00.0673% at 0.001h,Checked=3,Found=0,ETTF=1.875h00.0692% at 0.002h,Checked=5,Found=0,ETTF=3.605h00.0721% at 0.004h,Checked=7,Found=0,ETTF=5.195h.....63.3135% at 47.054h,Checked=119922,Found=0,ETTF=27.265h`
dobrichev
2016 Supporter

Posts: 1622
Joined: 24 May 2010

### Re: Need help in some probability calculations

in the head post, dobrichev wrote:1) Find several thousands of unavoidable sets (UA).
2) ...

You don't mention it explicitly, so I'll ask: do you restrict yourself to only minimal unavoidable sets?
Red Ed

Posts: 633
Joined: 06 June 2005

### Re: Need help in some probability calculations

Red Ed wrote:
in the head post, dobrichev wrote:1) Find several thousands of unavoidable sets (UA).
2) ...

You don't mention it explicitly, so I'll ask: do you restrict yourself to only minimal unavoidable sets?

Yes.

I am removing all combinations of 5 digits (1,2,3,4,5; 1,2,3,4,6...5,6,7,8,9) (5-rookeries?). For each of them I am solving (< 10M solutions), and removing supersets. This guarantees all UA of size 4..11 are in the list. Then removing all combinations of 5 boxes in the same way adds some extra sets. Result is 60K - 900K minimal UA for about 5-10 minutes. This is improved version of dukso's unav36.
Large amount of U12+ can be found iterating trough maximum (not only maximal) cliques formed by already known UA, and searching for UA within the rest clues. This depends of initial set and therefore doesn't guarantee all UA are found. It is slow - takes hours or days.
The template matching algorithm implemented in Checker (it is your idea, isn't it?) gives faster results for UA12...UA14. I didn't implement it.
I'll publish the source code soon.
dobrichev
2016 Supporter

Posts: 1622
Joined: 24 May 2010

### Re: Need help in some probability calculations

dobrichev wrote:I am removing all combinations of 5 digits ... solving (< 10M solutions) ... guarantees all UA of size 4..11
Nice observation.

When you throw away non-minimals, how do you do it? I can think of two ways: (A) put the raw list of unavoidables in a heap and repeat { pop smallest, delete all supersets of it }; or (B) for each raw unavoidable U in a solution grid S, keep U iff all solutions of S\U other than S itself have exactly 81-size(U) clues in common with S. It's not clear to me which is quicker.

The template matching algorithm implemented in Checker (it is your idea, isn't it?)
Probably not my idea as I've no idea what you're referring to!
Red Ed

Posts: 633
Joined: 06 June 2005

### Re: Need help in some probability calculations

Red Ed wrote:When you throw away non-minimals, how do you do it?

I am representing UA as 128-bit value in XMM register, 81 bits used.
On each pass (comparing solutions for a combination of givens removed), for each solution a bitmap of values different than original grid is composed (non-minimal UA). Bitmaps are stored in array. Before adding new bitmap at the end of the array, it is compared to all previously stored values. If it is a superset of already added set, it is skipped. If it is a subset, the respective superset in the array is invalidated (all 128 bits are set). After finishing with all solutions, valid bitmaps are added to global UA storage. For global storage I am using C++ STL set associative container, which simply ignores the duplicates coming from different passes.

For bitmapped sets A and B:
A is superset (or duplicate) of B when (A | B) == A.
A is subset of B when B is superset of A.

Note: This works only when all solutions are processed. If some part of the solutions is skipped (due to limitation in solver, memory, etc.), a non-minimal UA could be generated.

A comprehensive validation for minimality of UA is solving and checking for a second solution of a puzzle with all cells given except these in the UA, repeat by removing the UA cells one at a time. It is very fast if the brute force solver knows the original grid and is guessing starting from the "right" digit when possible. This transforms the guessing to marking the branches during the solving process, finding the original grid at first iteration (w/o any wrong guess), and eventually finding a second solution which is very close (in the terms of possible guess branches, or decision tree traversal) to the original grid.

Red Ed wrote:
The template matching algorithm implemented in Checker (it is your idea, isn't it?)
Probably not my idea as I've no idea what you're referring to!

Prepare a static list of known UA sets.
For a given grid, permute the bands, stacks, rows in a band, and columns in a stack in all possible ways.
On each permutation check each known UA for matching the grid. Equal digits in a template must correspond to equal digits in the permutation, and different digits in a template must correspond to different digits in the premutation.
dobrichev
2016 Supporter

Posts: 1622
Joined: 24 May 2010

### Source in C++ and Windows executable

Source code and windows executable are available here.
dobrichev
2016 Supporter

Posts: 1622
Joined: 24 May 2010

### Re: Need help in some probability calculations

so it backtracks through all n-subsets of the grid which are sudokus and contain a clue in each UA ?

the size of the maximum subset of mutually disjoint unavoidable sets,

is it useful, should it be determined
dukuso

Posts: 479
Joined: 25 June 2005

### Re: Need help in some probability calculations

dukuso wrote:so it backtracks through all n-subsets of the grid which are sudokus and contain a clue in each UA ?

the size of the maximum subset of mutually disjoint unavoidable sets,

is it useful, should it be determined

Yes, yes, and yes. See the first post in this topic for details.

I created new topic in Software section. Please post further comments there.

MD.
dobrichev
2016 Supporter

Posts: 1622
Joined: 24 May 2010

Previous