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

Postby dobrichev » Thu Jul 01, 2010 9:21 pm

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=1
Clique 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 80
Mapping iterator to grid
76 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 27
Mapping grid to iterator
47 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 65

maxPositionLimitsByUA
04 08 12 16 20 26 32 38 44 50 58 72 81 81 81 81 81
Using 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.165h
01.6638% at 0.004h,Checked=32,Found=0,ETTF=0.210h
02.3217% at 0.005h,Checked=35,Found=0,ETTF=0.209h
03.1863% at 0.007h,Checked=38,Found=0,ETTF=0.208h
04.4240% at 0.008h,Checked=65,Found=0,ETTF=0.183h
04.6303% at 0.010h,Checked=69,Found=0,ETTF=0.202h
05.0210% at 0.011h,Checked=74,Found=0,ETTF=0.216h
05.3579% at 0.013h,Checked=81,Found=0,ETTF=0.227h
06.3319% at 0.014h,Checked=140,Found=0,ETTF=0.214h
07.5699% at 0.016h,Checked=156,Found=0,ETTF=0.197h
08.2260% at 0.018h,Checked=187,Found=0,ETTF=0.198h
08.9391% at 0.019h,Checked=200,Found=0,ETTF=0.196h
09.9751% at 0.021h,Checked=224,Found=0,ETTF=0.188h
10.9103% at 0.022h,Checked=227,Found=0,ETTF=0.181h
11.7411% at 0.024h,Checked=257,Found=0,ETTF=0.177h
12.8531% at 0.025h,Checked=284,Found=0,ETTF=0.169h
13.8183% at 0.026h,Checked=291,Found=0,ETTF=0.163h
15.5420% at 0.028h,Checked=302,Found=0,ETTF=0.150h
17.0734% at 0.029h,Checked=310,Found=0,ETTF=0.140h
18.2242% at 0.030h,Checked=343,Found=0,ETTF=0.135h
20.4501% at 0.031h,Checked=366,Found=0,ETTF=0.122h
21.8463% at 0.033h,Checked=396,Found=0,ETTF=0.117h
25.6436% at 0.034h,Checked=428,Found=0,ETTF=0.099h
26.8035% at 0.036h,Checked=472,Found=0,ETTF=0.098h
28.1707% at 0.037h,Checked=535,Found=0,ETTF=0.096h
30.2114% at 0.039h,Checked=566,Found=0,ETTF=0.090h
32.9156% at 0.040h,Checked=582,Found=0,ETTF=0.082h
34.5835% at 0.042h,Checked=608,Found=0,ETTF=0.079h
36.9129% at 0.043h,Checked=628,Found=0,ETTF=0.074h
41.1386% at 0.045h,Checked=651,Found=0,ETTF=0.065h
42.4267% at 0.047h,Checked=661,Found=0,ETTF=0.064h
43.7948% at 0.049h,Checked=756,Found=0,ETTF=0.062h
45.9699% at 0.050h,Checked=813,Found=0,ETTF=0.059h
49.6342% at 0.051h,Checked=917,Found=0,ETTF=0.052h
51.5815% at 0.053h,Checked=989,Found=0,ETTF=0.050h
51.7955% at 0.054h,Checked=1023,Found=0,ETTF=0.050h
52.1131% at 0.055h,Checked=1030,Found=0,ETTF=0.051h
52.7455% at 0.057h,Checked=1032,Found=0,ETTF=0.051h
53.3986% at 0.058h,Checked=1086,Found=0,ETTF=0.050h
53.6243% at 0.059h,Checked=1098,Found=0,ETTF=0.051h
54.1117% at 0.060h,Checked=1155,Found=0,ETTF=0.051h
54.7306% at 0.061h,Checked=1163,Found=0,ETTF=0.051h
55.5789% at 0.062h,Checked=1172,Found=0,ETTF=0.050h
56.3869% at 0.064h,Checked=1192,Found=0,ETTF=0.049h
57.5618% at 0.065h,Checked=1218,Found=0,ETTF=0.048h
504200000000040030100000000060073000000000501000000000030000070000500400800020000
504200000000040030120000000060073000000000501000000000030000070000500400800000000
504200000000040030100000000060073000000000501000000000030000070000580400800000000
504200000000040032100000000060073000000000501000000000030000070000500400800000000
504200000000040030100000000060073000000000501000000000030000070000500420800000000
504200000000040030100060000060073000000000501000000000030000070000500400800000000
504200000000040030100000000060073000000000501200000000030000070000500400800000000
504200000000040030100000000060073200000000501000000000030000070000500400800000000
594200000000040030100000000060073000000000501000000000030000070000500400800000000
504200000000040030100000000060073000000000501000000000030000870000500400800000000
504200000080040030100000000060073000000000501000000000030000070000500400800000000
504200000000040030100000000060073000000000501000000090030000070000500400800000000
504200000000040030100000000060073008000000501000000000030000070000500400800000000
590200000000040030100000004060073000000000501000000000030000070000500400800000000
504200080000040030100000000060073000000000501000000000030000070000500400800000000
504200000000040030100000000060073000000000501000000000030000070000500400800000009
58.7101% at 0.066h,Checked=1355,Found=16,ETTF=0.046h
60.1690% at 0.067h,Checked=1382,Found=16,ETTF=0.044h
504200000000040030100008000060073000000000501000000000030000070000500400800000000
61.9350% at 0.068h,Checked=1401,Found=17,ETTF=0.042h
504200000000040030100000900060073000000000501000000000030000070000500400800000000
64.6045% at 0.070h,Checked=1446,Found=18,ETTF=0.038h
65.9132% at 0.071h,Checked=1460,Found=18,ETTF=0.037h
68.4109% at 0.072h,Checked=1477,Found=18,ETTF=0.033h
74.0921% at 0.073h,Checked=1498,Found=18,ETTF=0.026h
78.2322% at 0.074h,Checked=1590,Found=18,ETTF=0.021h
504200000000040030100000000060073000000000501000006000030000070000500400800000000
80.9235% at 0.075h,Checked=1618,Found=19,ETTF=0.018h
81.6487% at 0.077h,Checked=1623,Found=19,ETTF=0.017h
82.0620% at 0.078h,Checked=1643,Found=19,ETTF=0.017h
82.8156% at 0.079h,Checked=1671,Found=19,ETTF=0.016h
84.0644% at 0.080h,Checked=1807,Found=19,ETTF=0.015h
85.8939% at 0.081h,Checked=1847,Found=19,ETTF=0.013h
87.9816% at 0.082h,Checked=1883,Found=19,ETTF=0.011h
90.6156% at 0.084h,Checked=2006,Found=19,ETTF=0.009h
93.3752% at 0.085h,Checked=2053,Found=19,ETTF=0.006h
93.8757% at 0.086h,Checked=2080,Found=19,ETTF=0.006h
94.9878% at 0.087h,Checked=2116,Found=19,ETTF=0.005h
504200000000040030100000000960073000000000501000000000030000070000500400800000000
98.3968% at 0.088h,Checked=2185,Found=20,ETTF=0.001h

Checked for 17, generated 2211 puzzles, found 20 valid.

Iterations done in 317.859 seconds

Total 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
123456789456789132789213645275941368638527914941638257394175826517862493862394571

UA 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=5
Clique 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 = 14745600
Clique 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 = 14745600
Clique 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 = 29491200
Clique 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 = 19660800
Clique 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 = 19660800
Selected Clique 0
Using 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.875h
00.0692% at 0.002h,Checked=5,Found=0,ETTF=3.605h
00.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: 1311
Joined: 24 May 2010

Re: Need help in some probability calculations

Postby Red Ed » Sat Jul 03, 2010 6:59 am

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

Postby dobrichev » Sat Jul 03, 2010 9:51 am

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: 1311
Joined: 24 May 2010

Re: Need help in some probability calculations

Postby Red Ed » Sat Jul 03, 2010 6:29 pm

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

Postby dobrichev » Sat Jul 03, 2010 10:43 pm

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: 1311
Joined: 24 May 2010

Source in C++ and Windows executable

Postby dobrichev » Wed Jul 07, 2010 4:59 pm

Source code and windows executable are available here.
dobrichev
2016 Supporter
 
Posts: 1311
Joined: 24 May 2010

Re: Need help in some probability calculations

Postby dukuso » Wed Jul 07, 2010 5:19 pm

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

Postby dobrichev » Wed Jul 07, 2010 6:15 pm

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: 1311
Joined: 24 May 2010

Previous

Return to General