Number of ways of placing non-attacking queens and kings

part of "Between chessboard and computer", Vaclav Kotesovec, 1996

k Queens on board k x n

2 Queens, board 2xn: (n-1)(n-2)

3 Queens, board 3xn: (n-3)(n²-6n+12)

4 Queens, board 4xn: n⁴-18n³+139n²-534n+840, n>=7 (M.Tarry, 1890)

5 Queens, board 5xn: n⁵-30n⁴+407n³-3098n²+13104n-24332, n>=11 (V.Kotesovec, 1992)

6 Queens, board 6xn: n⁶-45n⁵+943n⁴-11755n³+91480n²-418390n+870920, n>=17 (V.Kotesovec, 1992)

7 Queens, board 7xn: n⁷-63n⁶+1879n⁵-34411n⁴+417178n³-3336014n²+16209916n-36693996, n>=23 (V.Kotesovec, 1992)

Podle mojí hypotézy z citovaného článku má obecně polynom tvar: n^k-3(k!/(2!(k-2)!))n^k-1 + ...

k Queens on board n x n

2 Queens, board nxn: n(n-1)(n-2)(3n-1)/6

3 Queens, board nxn (E.Landau, 1896): n(n-2)²(2n³-12n²+23n-10)/12, pro n sudé (even),
(n-1)(n-3)(2n⁴-12n³+25n²-14n+1)/12, pro n liché (odd)

4 Queens, board nxn (V.Kotesovec, 1992): n>=2 : n⁸/24 - 5n⁷/6 + 65n⁶/9 - 1051n⁵/30 + 817n⁴/8 - ...

a dále podle typu n:

a) n=6k, -4769n³/27 + 1963n²/12 - 1769n/30

b) n=6k+1, -9565n³/54 + 1013n²/6 - 6727n/90 + 257/27

c) n=6k+2, -4769n³/27 + 1963n²/12 - 5467n/90 + 28/27

d) n=6k+3, -9565n³/54 + 1013n²/6 - 2189n/30 + 7

e) n=6k+4, -4769n³/27 + 1963n²/12 - 5467n/90 + 68/27

f) n=6k+5, -9565n³/54 + 1013n²/6 - 6727n/90 + 217/27

Koeficienty u n³ a n², jdou vyjádřit také takto: -19103/108 + (-1)ⁿ/4 , -3989/24 - 21(-1)ⁿ/8

k Kings on board n x n

2 Kings, board nxn: (n-1)(n-2)(n²+3n-2)/2

3 Kings, board nxn: (n-1)(n-2)(n⁴+3n³-20n²-30n+132)/6

4 Kings, board nxn: (n⁸-54n⁶+72n⁵+995n⁴-2472n³-5094n²+21480n-17112)/24, n>=3, (K.Fabel + K.Soltsien)

5 Kings, board nxn: (n-4)(n⁹+4n⁸-74n⁷-176n⁶+2411n⁵+1844n⁴-38194n³+18944n²+236520n-316320)/120, n>=4, (V.Kotesovec, 1992)

Tables

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).

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ěžší.

                                                    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          ?          ?