part of "Between chessboard and computer", Vaclav Kotesovec, 1996
(Mezi šachovnicí a počítačem, str.204-206, Václav Kotěšovec, 1996)2 Queens, board 2xn: (n-1)(n-2)
3 Queens, board 3xn: (n-3)(n2-6n+12)
4 Queens, board 4xn: n4-18n3+139n2-534n+840, n>=7 (M.Tarry, 1890)
5 Queens, board 5xn: n5-30n4+407n3-3098n2+13104n-24332, n>=11 (V.Kotesovec, 1992)
6 Queens, board 6xn: n6-45n5+943n4-11755n3+91480n2-418390n+870920, n>=17 (V.Kotesovec, 1992)
7 Queens, board 7xn: n7-63n6+1879n5-34411n4+417178n3-3336014n2+16209916n-36693996, n>=23 (V.Kotesovec, 1992)
Podle mojí hypotézy z citovaného článku má obecně polynom tvar: nk-3(k!/(2!(k-2)!))nk-1 + ...
2 Queens, board nxn: n(n-1)(n-2)(3n-1)/6
3 Queens, board nxn (E.Landau, 1896): n(n-2)2(2n3-12n2+23n-10)/12, pro n sudé (even),
(n-1)(n-3)(2n4-12n3+25n2-14n+1)/12, pro n liché (odd)
4 Queens, board nxn (V.Kotesovec, 1992): n>=2 : n8/24 - 5n7/6 + 65n6/9 - 1051n5/30 + 817n4/8 - ...
a dále podle typu n:
a) n=6k, -4769n3/27 + 1963n2/12 - 1769n/30
b) n=6k+1, -9565n3/54 + 1013n2/6 - 6727n/90 + 257/27
c) n=6k+2, -4769n3/27 + 1963n2/12 - 5467n/90 + 28/27
d) n=6k+3, -9565n3/54 + 1013n2/6 - 2189n/30 + 7
e) n=6k+4, -4769n3/27 + 1963n2/12 - 5467n/90 + 68/27
f) n=6k+5, -9565n3/54 + 1013n2/6 - 6727n/90 + 217/27
Koeficienty u n3 a n2, jdou vyjádřit také takto: -19103/108 + (-1)n/4 , -3989/24 - 21(-1)n/8
2 Kings, board nxn: (n-1)(n-2)(n2+3n-2)/2
3 Kings, board nxn: (n-1)(n-2)(n4+3n3-20n2-30n+132)/6
4 Kings, board nxn: (n8-54n6+72n5+995n4-2472n3-5094n2+21480n-17112)/24, n>=3, (K.Fabel + K.Soltsien)
5 Kings, board nxn: (n-4)(n9+4n8-74n7-176n6+2411n5+1844n4-38194n3+18944n2+236520n-316320)/120, n>=4, (V.Kotesovec, 1992)
Jelikož vzorce pro rozmístění k dam na šachovnici kxn platí vždy až od jistého n, jsou v následující tabulce uvedeny počty i pro malá n, kde vzorce ještě neplatí (tučná čísla). Sloupec vpravo představuje počty rozmístění vzájemně se neohrožujících n dam na šachovnici nxn (jehož speciálním případem je známý problém 8 dam, který vyřešil již v roce 1850 slavný matematik Gauss). Odvodit obecný vzorec se zatím nepodařilo a i jen tyto dílčí výsledky naznačují, o jak obtížný problém se jedná (porovnejte s diagonálou v tabulce).
n |
k=2 |
k=3 |
k=4 |
k=5 |
k=6 |
k=7 |
n queens, nxn |
2 |
0 |
|
|
|
|
0 |
|
3 |
2 |
0 |
|
|
|
|
0 |
4 |
6 |
4 |
2 |
|
|
|
2 |
5 |
12 |
14 |
12 |
10 |
|
|
10 |
6 |
20 |
36 |
46 |
40 |
4 |
|
4 |
7 |
30 |
76 |
140 |
164 |
94 |
40 |
40 |
8 |
42 |
140 |
344 |
568 |
550 |
312 |
92 |
9 |
56 |
234 |
732 |
1614 |
2292 |
2038 |
352 |
10 |
72 |
364 |
1400 |
3916 |
7552 |
9632 |
724 |
11 |
90 |
536 |
2468 |
8492 |
21362 |
37248 |
2680 |
12 |
110 |
756 |
4080 |
16852 |
52856 |
120104 |
14200 |
13 |
132 |
1030 |
6404 |
31100 |
117694 |
335010 |
73712 |
14 |
156 |
1364 |
9632 |
54068 |
241484 |
835056 |
365596 |
15 |
182 |
1764 |
13980 |
89428 |
463038 |
1897702 |
2279184 |
16 |
210 |
2236 |
19688 |
141812 |
838816 |
3998456 |
14772512 |
17 |
240 |
2786 |
27020 |
216932 |
1448002 |
7907094 |
95815104 |
18 |
272 |
3420 |
36264 |
321700 |
2398292 |
14818300 |
666090624 |
19 |
306 |
4144 |
47732 |
464348 |
3832374 |
26512942 |
4968057848 |
20 |
342 |
4964 |
61760 |
654548 |
5935120 |
45562852 |
39029188884 |
21 |
380 |
5886 |
78708 |
903532 |
8941514 |
75580634 |
314666222712 |
22 |
420 |
6916 |
98960 |
1224212 |
13145292 |
121520020 |
2691008701644 |
23 |
462 |
8060 |
122924 |
1631300 |
18908302 |
190031678 |
24233937684440 |
24 |
506 |
9324 |
151032 |
2141428 |
26670584 |
289879092 |
? |
25 |
552 |
10714 |
183740 |
2773268 |
36961170 |
432420154 |
? |
26 |
600 |
12236 |
221528 |
3547652 |
50409604 |
632159540 |
? |
27 |
650 |
13896 |
264900 |
4487692 |
67758182 |
907376502 |
? |
28 |
702 |
15700 |
314384 |
5618900 |
89874912 |
1280833348 |
? |
29 |
756 |
17654 |
370532 |
6969308 |
117767194 |
1780569602 |
? |
30 |
812 |
19764 |
433920 |
8569588 |
152596220 |
2440786884 |
? |
31 |
870 |
22036 |
505148 |
10453172 |
195692094 |
3302829550 |
? |
32 |
930 |
24476 |
584840 |
12656372 |
248569672 |
4416266132 |
? |
Druhá tabulka udává rozmístění k dam na šachovnici nxn, rovněž zde diagonála odpovídá výše nastíněnému problému, ale tato cesta je ještě těžší.
n |
k=2 |
k=3 |
k=4 |
n queens, nxn |
2 |
0 |
|
|
0 |
3 |
8 |
0 |
|
0 |
4 |
44 |
24 |
2 |
2 |
5 |
140 |
204 |
82 |
10 |
6 |
340 |
1024 |
982 |
4 |
7 |
700 |
3628 |
7002 |
40 |
8 |
1288 |
10320 |
34568 |
92 |
9 |
2184 |
25096 |
131248 |
352 |
10 |
3480 |
54400 |
412596 |
724 |
11 |
5280 |
107880 |
1123832 |
2680 |
12 |
7700 |
199400 |
2739386 |
14200 |
13 |
10868 |
348020 |
6106214 |
73712 |
14 |
14924 |
579264 |
12654614 |
365596 |
15 |
20020 |
926324 |
24675650 |
2279184 |
16 |
26320 |
1431584 |
45704724 |
14772512 |
17 |
34000 |
2148048 |
80999104 |
95815104 |
18 |
43248 |
3141120 |
138170148 |
666090624 |
19 |
54264 |
4490256 |
227938788 |
4968057848 |
20 |
67260 |
6291000 |
365106738 |
39029188884 |
21 |
82460 |
8656860 |
569681574 |
314666222712 |
22 |
100100 |
11721600 |
868289594 |
2691008701644 |
23 |
120428 |
15641340 |
1295775946 |
24233937684440 |
24 |
143704 |
20597104 |
1897176508 |
? |
25 |
170200 |
26797144 |
2729909796 |
? |
26 |
200200 |
34479744 |
3866439956 |
? |
27 |
234000 |
43915768 |
5397191260 |
? |
28 |
271908 |
55411720 |
7434046062 |
? |
29 |
314244 |
69312516 |
10114126790 |
? |
30 |
361340 |
86004800 |
13604287706 |
? |
31 |
413540 |
105919940 |
18105920006 |
? |
32 |
471200 |
129537600 |
23860611236 |
? |
33 |
534688 |
157388960 |
31156143476 |
? |
34 |
604384 |
190060544 |
40333505448 |
? |
35 |
680680 |
228197664 |
51794268148 |
? |
36 |
763980 |
272508504 |
66009149958 |
? |
37 |
854700 |
323767788 |
83526964218 |
? |
38 |
953268 |
382821120 |
104984952954 |
? |
39 |
1060124 |
450588876 |
131119515534 |
? |
40 |
1175720 |
528070800 |
162778537232 |
? |
n | T(n) | log T(n)/(n log n) | Q(n) | log Q(n)/(n log n) | (Q(n)/n!)(1/(n-1)) |
1 | 1 | - | 1 | - | - |
2 | 0 | - | 0 | - | - |
3 | 0 | - | 0 | - | - |
4 | 0 | - | 2 | 0.12500 | 0.436790 |
5 | 10 | 0.28613 | 10 | 0.28613 | 0.537285 |
6 | 0 | - | 4 | 0.12895 | 0.353953 |
7 | 28 | 0.24463 | 40 | 0.27081 | 0.446620 |
8 | 0 | - | 92 | 0.27181 | 0.419382 |
9 | 0 | - | 352 | 0.29651 | 0.420095 |
10 | 0 | - | 724 | 0.28597 | 0.388049 |
11 | 88 | 0.16974 | 2680 | 0.29926 | 0.382559 |
12 | 0 | - | 14200 | 0.32063 | 0.387578 |
13 | 4524 | 0.25243 | 73712 | 0.33612 | 0.388542 |
14 | 0 | - | 365596 | 0.34669 | 0.385792 |
15 | 0 | - | 2279184 | 0.36039 | 0.387849 |
16 | 0 | - | 14772512 | 0.37213 | 0.388976 |
17 | 140692 | 0.24612 | 95815104 | 0.38156 | 0.388506 |
18 | 0 | - | 666090624 | 0.39050 | 0.388371 |
19 | 820496 | 0.24341 | 4968057848 | 0.39908 | 0.388602 |
20 | 0 | - | 39029188884 | 0.40703 | 0.388822 |
21 | 0 | - | 314666222712 | 0.41408 | 0.388575 |
22 | 0 | - | 2691008701644 | 0.42087 | 0.388583 |
23 | 128850048 | 0.25894 | 24233937684440 | 0.42734 | 0.388717 |
24 | 0 | - | ? | ? | ? |
25 | 1957725000 | 0.26586 | ? | ? | ? |
. | |||||
Ą | ®1 | ®1 | ®0.3885... |
|
Durango Bill Birger Nielsen Rivin+Vardi+Zimmermann Order < --- Ordinary Queens --- > < - Superqueens - > (f(n)/n!)^(1/(n-1)) ("N") Total Solutions Unique Solutions Tot. Sol. Unique Sol. log(f(n))/(n*log(n)) ------------------------------------------------------------------ 1 1 1 1 1 2 0 0 0 0 3 0 0 0 0 4 2 1 0 0 5 10 2 0 0 6 4 1 0 0 7 40 6 0 0 8 92 12 0 0 9 352 46 0 0 10 724 92 4 1 0.2177875229 0.0602059991 11 2680 341 44 6 0.2536469800 0.1434663320 12 14200 1787 156 22 0.2571896108 0.1693509629 13 73712 9233 1876 239 0.2861405294 0.2260322668 14 365596 45752 5180 653 0.2780659430 0.2314830981 15 2279184 285053 32516 4089 0.2863046443 0.2557679703 16 14772512 1846955 202900 25411 0.2922654623 0.2754751459 17 95815104 11977939 1330622 166463 0.2973799174 0.2927699845 18 666090624 83263591 8924976 1115871 0.3013522738 0.3076183338 19 4968057848 621012754 64492432 8062150 0.3052738993 0.3214276591 20 39029188884 4878666808 ? ? 21 314666222712 39333324973 ? ? 22 2691008701644 336376244042 ? ? 23 24233937684440 3029242658210 ? ?