The New Sudoku Players' Forum

by **JPF** » Sun Apr 22, 2012 11:18 pm

Using the results given by Red Ed here, we can easily calculate the number of e-d patterns with n clues.

Here are the results (number of clues, number of e-d patterns):

Code: Select all: 0 1 1 1 2 5 3 21 4 109 5 548 6 3074 7 16847 8 92393 9 489448 10 2499689 11 12199113 12 56737622 13 250632745 14 1049547176 15 4159131734 16 15578997961 17 55113078988 18 184060159680 19 580219975879 20 1726649409444 21 4852092873260 22 12881523178029 23 32326780555962 24 76733980909494 25 172397698733180 26 366849216218909 27 739856554278500 28 1415123268225799 29 2568609122743361 30 4427035437198339 31 7248951925550465 32 11282386772412398 33 16698823272821708 34 23512787678143566 35 31507091246915793 36 40191031928611303 37 48817495062238591 38 56472143448081548 39 62225821998470051 40 65317264463457661 41 65317264463457661 42 62225821998470051 43 56472143448081548 44 48817495062238591 45 40191031928611303 46 31507091246915793 47 23512787678143566 48 16698823272821708 49 11282386772412398 50 7248951925550465 51 4427035437198339 52 2568609122743361 53 1415123268225799 54 739856554278500 55 366849216218909 56 172397698733180 57 76733980909494 58 32326780555962 59 12881523178029 60 4852092873260 61 1726649409444 62 580219975879 63 184060159680 64 55113078988 65 15578997961 66 4159131734 67 1049547176 68 250632745 69 56737622 70 12199113 71 2499689 72 489448 73 92393 74 16847 75 3074 76 548 77 109 78 21 79 5 80 1 81 1 ------------------------------ 746186061249180790

JPF

by **Serg** » Mon Apr 23, 2012 6:46 am

Hi, JPF!
You published great result, congratulations!
I calculated (manually) low bound for number of e-d 17-clue patterns. I got low bound 3.8e10 (if I was not wrong in calculations). It does not contradict with your exact number of 17-clue patterns - 5.5e10 (appox.).
Well done!

Serg

by **JPF** » Sat Apr 28, 2012 6:24 pm

Thanks Serg !

Here I put online some details on the calculation of Nn and some comments on the En=C(81,n)/3359232 approximation.

Here are the results:

Code: Select all: n Nn Nn En Nn/En 0 1 1.00E+00 2.98E-07 3.3592E+06 1 1 1.00E+00 2.41E-05 4.1472E+04 2 5 5.00E+00 9.65E-04 5.1840E+03 3 21 2.10E+01 2.54E-02 8.2682E+02 4 109 1.09E+02 4.95E-01 2.2008E+02 5 548 5.48E+02 7.63E+00 7.1848E+01 6 3074 3.07E+03 9.66E+01 3.1818E+01 7 16847 1.68E+04 1.04E+03 1.6275E+01 8 92393 9.24E+04 9.57E+03 9.6495E+00 9 489448 4.89E+05 7.77E+04 6.3022E+00 10 2499689 2.50E+06 5.59E+05 4.4703E+00 11 12199113 1.22E+07 3.61E+06 3.3800E+00 12 56737622 5.67E+07 2.11E+07 2.6949E+00 13 250632745 2.51E+08 1.12E+08 2.2429E+00 14 1049547176 1.05E+09 5.43E+08 1.9337E+00 15 4159131734 4.16E+09 2.42E+09 1.7156E+00 16 15578997961 1.56E+10 1.00E+10 1.5578E+00 17 55113078988 5.51E+10 3.82E+10 1.4413E+00 18 184060159680 1.84E+11 1.36E+11 1.3538E+00 19 580219975879 5.80E+11 4.51E+11 1.2871E+00 20 1726649409444 1.73E+12 1.40E+12 1.2356E+00 21 4852092873260 4.85E+12 4.06E+12 1.1953E+00 22 12881523178029 1.29E+13 1.11E+13 1.1635E+00 23 32326780555962 3.23E+13 2.84E+13 1.1383E+00 24 76733980909494 7.67E+13 6.86E+13 1.1181E+00 25 172397698733180 1.72E+14 1.56E+14 1.1017E+00 26 366849216218909 3.67E+14 3.37E+14 1.0885E+00 27 739856554278500 7.40E+14 6.87E+14 1.0776E+00 28 1415123268225799 1.42E+15 1.32E+15 1.0688E+00 29 2568609122743361 2.57E+15 2.42E+15 1.0615E+00 30 4427035437198339 4.43E+15 4.19E+15 1.0555E+00 31 7248951925550465 7.25E+15 6.90E+15 1.0505E+00 32 11282386772412398 1.13E+16 1.08E+16 1.0464E+00 33 16698823272821708 1.67E+16 1.60E+16 1.0431E+00 34 23512787678143566 2.35E+16 2.26E+16 1.0403E+00 35 31507091246915793 3.15E+16 3.04E+16 1.0381E+00 36 40191031928611303 4.02E+16 3.88E+16 1.0363E+00 37 48817495062238591 4.88E+16 4.72E+16 1.0350E+00 38 56472143448081548 5.65E+16 5.46E+16 1.0340E+00 39 62225821998470051 6.22E+16 6.02E+16 1.0334E+00 40 65317264463457661 6.53E+16 6.32E+16 1.0331E+00 41 65317264463457661 6.53E+16 6.32E+16 1.0331E+00 42 62225821998470051 6.22E+16 6.02E+16 1.0334E+00 43 56472143448081548 5.65E+16 5.46E+16 1.0340E+00 44 48817495062238591 4.88E+16 4.72E+16 1.0350E+00 45 40191031928611303 4.02E+16 3.88E+16 1.0363E+00 46 31507091246915793 3.15E+16 3.04E+16 1.0381E+00 47 23512787678143566 2.35E+16 2.26E+16 1.0403E+00 48 16698823272821708 1.67E+16 1.60E+16 1.0431E+00 49 11282386772412398 1.13E+16 1.08E+16 1.0464E+00 50 7248951925550465 7.25E+15 6.90E+15 1.0505E+00 51 4427035437198339 4.43E+15 4.19E+15 1.0555E+00 52 2568609122743361 2.57E+15 2.42E+15 1.0615E+00 53 1415123268225799 1.42E+15 1.32E+15 1.0688E+00 54 739856554278500 7.40E+14 6.87E+14 1.0776E+00 55 366849216218909 3.67E+14 3.37E+14 1.0885E+00 56 172397698733180 1.72E+14 1.56E+14 1.1017E+00 57 76733980909494 7.67E+13 6.86E+13 1.1181E+00 58 32326780555962 3.23E+13 2.84E+13 1.1383E+00 59 12881523178029 1.29E+13 1.11E+13 1.1635E+00 60 4852092873260 4.85E+12 4.06E+12 1.1953E+00 61 1726649409444 1.73E+12 1.40E+12 1.2356E+00 62 580219975879 5.80E+11 4.51E+11 1.2871E+00 63 184060159680 1.84E+11 1.36E+11 1.3538E+00 64 55113078988 5.51E+10 3.82E+10 1.4413E+00 65 15578997961 1.56E+10 1.00E+10 1.5578E+00 66 4159131734 4.16E+09 2.42E+09 1.7156E+00 67 1049547176 1.05E+09 5.43E+08 1.9337E+00 68 250632745 2.51E+08 1.12E+08 2.2429E+00 69 56737622 5.67E+07 2.11E+07 2.6949E+00 70 12199113 1.22E+07 3.61E+06 3.3800E+00 71 2499689 2.50E+06 5.59E+05 4.4703E+00 72 489448 4.89E+05 7.77E+04 6.3022E+00 73 92393 9.24E+04 9.57E+03 9.6495E+00 74 16847 1.68E+04 1.04E+03 1.6275E+01 75 3074 3.07E+03 9.66E+01 3.1818E+01 76 548 5.48E+02 7.63E+00 7.1848E+01 77 109 1.09E+02 4.95E-01 2.2008E+02 78 21 2.10E+01 2.54E-02 8.2682E+02 79 5 5.00E+00 9.65E-04 5.1840E+03 80 1 1.00E+00 2.41E-05 4.1472E+04 81 1 1.00E+00 2.98E-07 3.3592E+06 ------------------------------------------------------------ TOTAL 746186061249180790 7.46E+17 7.20E+17 1.0367E+00

JPF

by **Serg** » Sat May 26, 2012 6:25 am

Hi, JPF!
I counted number of essentially different patterns having map

Code: Select all: 1 2 2 2 2 2 2 2 2

i.e. subset of 17-clue patterns set. (2084 known 17-clue valid puzzles have this map.)
My result - 76590743 (approx. 77 millions) essentially different patterns for this map.
Could you cross-check this result, i.e. count number of 17-clue essentially different patterns such, that one its box has 1 clue, but each remaining box has 2 clues?

Serg

[Edited. I found a bug in my patterns' generator. So, published previously number of patterns for this map ("39922455 (approx. 40 millions)" patterns) is wrong. Posted correct number (2 times approx. greater). This time I am posting more reliable data.]

by **coloin** » Tue May 29, 2012 9:37 pm

Serg wrote:....
I counted number of essentially different patterns having map
Code: Select all
1 2 2 2 2 2 2 2 2

i.e. subset of 17-clue patterns set. (2084 known 17-clue valid puzzles have this map.)
My result - 39922455 (approx. 40 millions) essentially different patterns for this map.......

whilst you are waiting ......
I am just wondering how many patterns are there with map

Code: Select all: 222 222 222

sort of thinking there might be less [not more] than your 17-clue case !

C

by **Serg** » Wed May 30, 2012 6:27 am

Hi, coloin!

coloin wrote:I am just wondering how many patterns are there with map
Code: Select all
222 222 222

sort of thinking there might be less [not more] than your 17-clue case !

Surely this map has less patterns than map

Code: Select all: 1 2 2 2 2 2 2 2 2

because your (18-clue) map has more automorphisms (72 versus 8). I'll count tonight exact number of patterns for map

Code: Select all: 2 2 2 2 2 2 2 2 2

(It took me 1.5 hours to count number of patterns for 17-clue map.)

Serg

by **Serg** » Thu May 31, 2012 5:06 am

Hi, coloin!
Map

Code: Select all: 2 2 2 2 2 2 2 2 2

has 33,135,278 essentially different patterns (7 seconds CPU time for patterns' enumerating).

Serg

[Edited. I found a bug in my patterns' generator. So, published previously number of patterns for this map (17,915,615 patterns) is wrong. I've posted correct number now (2 times approx. greater). This time I am posting more reliable data.]

by **coloin** » Thu May 31, 2012 8:55 pm

thanks
some of those maybe wont have puzzles too ...... maybe not that many though

continued on other thread here

c

by **JPF** » Wed Jun 13, 2012 8:32 pm

Here are the number of e-d patterns with n clues for different numbers of boxes B1 to B1B2B3B4B5B6B7B8B9:

Code: Select all: n B1 B1B2 B1B2B3 B1B2B3B4 B1B2B3B4B5 B1B2B3B4B5B6 B1B2B3B4B5B6B7 B1B2B3B4B5B6B7B8 B1B2B3B4B5B6B7B8B9 0 1 1 1 1 1 1 1 1 1 1 1 1 1 3 3 1 3 2 1 2 2 5 5 16 19 8 22 14 5 3 4 12 15 64 86 30 110 72 21 4 5 31 43 234 393 151 602 434 109 5 5 59 110 782 1626 638 3009 2396 548 6 4 115 281 2421 6433 2918 14863 13270 3074 7 2 163 606 6810 23394 12168 69113 69537 16847 8 1 219 1219 17626 79527 49664 307373 349866 92393 9 1 231 2172 41741 249606 188848 1289738 1669434 489448 10 219 3457 90395 724724 677647 5109946 7566939 2499689 11 163 4896 178953 1938798 2262557 19028540 32465851 12199113 12 115 6198 323697 4779476 7045245 66537844 131758212 56737622 13 59 6952 534619 10842118 20359408 218091920 504942820 250632745 14 31 6952 806209 22638115 54629003 669734791 1825702500 1049547176 15 12 6198 1109836 43498539 135890798 1925999530 6222058467 4159131734 16 5 4896 1394425 76946005 313518202 5187092778 19976256249 15578997961 17 1 3457 1599162 125337208 670752253 13085359351 60395383112 55113078988 18 1 2172 1673892 188080950 1331597002 30932683677 171929014874 184060159680 19 1219 1599162 260089331 2453894292 68553053577 460862724409 580219975879 20 606 1394425 331565715 4200743119 142513113721 1163500088165 1726649409444 21 281 1109836 389759092 6683626917 278066354028 2767453369549 4852092873260 22 110 806209 422560597 9890065077 509515193017 6204420086070 12881523178029 23 43 534619 422560597 13617417504 877242406757 13117237102348 32326780555962 24 15 323697 389759092 17454896343 1419912078432 26165736733002 76733980909494 25 5 178953 331565715 20835765799 2161666638170 49272814549281 172397698733180 26 1 90395 260089331 23168779886 3096610618278 87639189277975 366849216218909 27 1 41741 188080950 24002434607 4175574811114 147309412053150 739856554278500 28 17626 125337208 23168779886 5301687533366 234107817191961 1415123268225799 29 6810 76946005 20835765799 6340014086036 351925225023723 2568609122743361 30 2421 43498539 17454896343 7142131065903 500623181795629 4427035437198339 31 782 22638115 13617417504 7580234218886 674145594447876 7248951925550465 32 234 10842118 9890065077 7580234218886 859631941645706 11282386772412398 33 64 4779476 6683626917 7142131065903 1038240759222551 16698823272821708 34 16 1938798 4200743119 6340014086036 1187946672144049 23512787678143566 35 3 724724 2453894292 5301687533366 1287867881680654 31507091246915793 36 1 249606 1331597002 4175574811114 1322996243356504 40191031928611303 37 79527 670752253 3096610618278 1287867881680654 48817495062238591 38 23394 313518202 2161666638170 1187946672144049 56472143448081548 39 6433 135890798 1419912078432 1038240759222551 62225821998470051 40 1626 54629003 877242406757 859631941645706 65317264463457661 41 393 20359408 509515193017 674145594447876 65317264463457661 42 86 7045245 278066354028 500623181795629 62225821998470051 43 19 2262557 142513113721 351925225023723 56472143448081548 44 3 677647 68553053577 234107817191961 48817495062238591 45 1 188848 30932683677 147309412053150 40191031928611303 46 49664 13085359351 87639189277975 31507091246915793 47 12168 5187092778 49272814549281 23512787678143566 48 2918 1925999530 26165736733002 16698823272821708 49 638 669734791 13117237102348 11282386772412398 50 151 218091920 6204420086070 7248951925550465 51 30 66537844 2767453369549 4427035437198339 52 8 19028540 1163500088165 2568609122743361 53 1 5109946 460862724409 1415123268225799 54 1 1289738 171929014874 739856554278500 55 307373 60395383112 366849216218909 56 69113 19976256249 172397698733180 57 14863 6222058467 76733980909494 58 3009 1825702500 32326780555962 59 602 504942820 12881523178029 60 110 131758212 4852092873260 61 22 32465851 1726649409444 62 3 7566939 580219975879 63 1 1669434 184060159680 64 349866 55113078988 65 69537 15578997961 66 13270 4159131734 67 2396 1049547176 68 434 250632745 69 72 56737622 70 14 12199113 71 2 2499689 72 1 489448 73 92393 74 16847 75 3074 76 548 77 109 78 21 79 5 80 1 81 1 TOTAL 26 1443 51912 13887880 3758243512 225686785565 78291664988992 14260697696136800 746186061249180790

These numbers have to be checked.

JPF

by **Serg** » Thu Jun 14, 2012 3:06 pm

Hi, JPF!

JPF wrote:Here are the number of e-d patterns with n clues for different numbers of boxes B1 to B1B2B3B4B5B6B7B8B9:

Impressive results!I confirm variant "B1" and total number of e-d patterns for variant "B1B2B3" (51912).

Serg

by **dobrichev** » Thu Jun 14, 2012 8:40 pm

Hi,

Does B1B2B3 column cover in some way B1B5B9 or there are no results calculated except for the exactly named box combinations?

by **JPF** » Thu Jun 14, 2012 9:47 pm

dobrichev wrote:...there are no results calculated except for the exactly named box combinations?

Yes, B1B2B3 is the first band and is different from B1B5B9 not given here.
I should calculate these numbers for the 26 non equivalent combinations of boxes.

JPF

by **JPF** » Fri Jun 15, 2012 9:05 pm

As an example, here are the values for B1B2 and B1B5:

Code: Select all: n B1B2 B1B5 0 1 1 1 1 1 2 5 3 3 12 6 4 31 13 5 59 20 6 115 34 7 163 42 8 219 55 9 231 56 10 219 55 11 163 42 12 115 34 13 59 20 14 31 13 15 12 6 16 5 3 17 1 1 18 1 1 TOTAL 1443 406

and B1B2B3 - B1B5B9:

Code: Select all: n B1B2B3 B1B5B9 0 1 1 1 1 1 2 5 3 3 15 7 4 43 15 5 110 28 6 281 55 7 606 92 8 1219 153 9 2172 232 10 3457 323 11 4896 414 12 6198 494 13 6952 535 14 6952 535 15 6198 494 16 4896 414 17 3457 323 18 2172 232 19 1219 153 20 606 92 21 281 55 22 110 28 23 43 15 24 15 7 25 5 3 26 1 1 27 1 1 TOTAL 51912 4706

JPF

by **Serg** » Tue Aug 07, 2012 8:06 am

Hi, people!
It turned out, that it is very complicated task (for me, at least) to develope an algoritm generating all essentially different patterns for given map. It is difficult to construct transparent and reliable such algorithm. So, I decided to solve simpler task first - to enumerate (count) all essentially different patterns for given map. I've developed such enumerator. It runs much more faster, than my previous patterns generator.

I recalculated number of essentially different patterns for 2 posted above maps (possible maps for 17-clue and 18-clue puzzles). Here are results.

Map

Code: Select all: 1 2 2 2 2 2 2 2 2

has 76,590,743 essentially different patterns. (Too many to do exhaustive search in reasonable time yet

.) CPU time: 1 second.

Map

Code: Select all: 2 2 2 2 2 2 2 2 2

has 33,135,278 essentially different patterns. CPU time: 7 seconds.

Now I continue to develope generator which could produce all essentially different patterns for given map. (This task is required for N-clue exhaustive search problem solving.)

Serg

by **Serg** » Wed Jun 05, 2013 5:00 am

Hi, all!
I confirmed results of JPF, posted in this thread:

JPF wrote:Using the results given by Red Ed here, we can easily calculate the number of e-d patterns with n clues.

Here are the results (number of clues, number of e-d patterns):

Code: Select all
0 1 1 1 2 5 3 21 4 109 5 548 6 3074 7 16847 8 92393 9 489448 10 2499689 11 12199113 12 56737622 13 250632745 14 1049547176 15 4159131734 16 15578997961 17 55113078988 18 184060159680 19 580219975879 20 1726649409444 21 4852092873260 22 12881523178029 23 32326780555962 24 76733980909494 25 172397698733180 26 366849216218909 27 739856554278500 28 1415123268225799 29 2568609122743361 30 4427035437198339 31 7248951925550465 32 11282386772412398 33 16698823272821708 34 23512787678143566 35 31507091246915793 36 40191031928611303 37 48817495062238591 38 56472143448081548 39 62225821998470051 40 65317264463457661 41 65317264463457661 42 62225821998470051 43 56472143448081548 44 48817495062238591 45 40191031928611303 46 31507091246915793 47 23512787678143566 48 16698823272821708 49 11282386772412398 50 7248951925550465 51 4427035437198339 52 2568609122743361 53 1415123268225799 54 739856554278500 55 366849216218909 56 172397698733180 57 76733980909494 58 32326780555962 59 12881523178029 60 4852092873260 61 1726649409444 62 580219975879 63 184060159680 64 55113078988 65 15578997961 66 4159131734 67 1049547176 68 250632745 69 56737622 70 12199113 71 2499689 72 489448 73 92393 74 16847 75 3074 76 548 77 109 78 21 79 5 80 1 81 1 ------------------------------ 746186061249180790

I used different method of calculation number of N-clue patterns:
1. I calculated "cycle factorization classes" for VPT group (see thread Cycle factorization classes).
2. I produced cycle index of VPT group (polynomial, describing cycle structures of VPT) directly from "cycle factorization classes".
3. I used Polya Enumeration Theorem to get final results.

Serg

The New Sudoku Players' Forum

Number of non equivalent patterns having N clues

Number of non equivalent patterns having N clues

Re: Number of non equivalent patterns having N clues

Re: Number of non equivalent patterns having N clues

Re: Number of non equivalent patterns having N clues

Re: Number of non equivalent patterns having N clues

Re: Number of non equivalent patterns having N clues

Re: Number of non equivalent patterns having N clues

Re: Number of non equivalent patterns having N clues

Re: Number of non equivalent patterns having N clues

Re: Number of non equivalent patterns having N clues

Re: Number of non equivalent patterns having N clues

Re: Number of non equivalent patterns having N clues

Re: Number of non equivalent patterns having N clues

Re: Number of non equivalent patterns having N clues

Re: Number of non equivalent patterns having N clues