Number of ways of placing non-attacking
queens, kings, bishops and knights

on boards of various sizes - new results and formulas since 1996

(Vaclav Kotesovec, 1.2.2010, updated 9.2.2010)

This article is based on part of book "Between chessboard and computer", Vaclav Kotesovec, 1996. Pages 204-6 is a straight piece of combinatorial mathematics concerning the number of ways of placing non-attacking kings and queens on boards of various sizes. Now new results and formulas since 1996 are published.

Tento článek je věnován problematice počtu rozmístění neohrožujících se kamenů stejných hodnot na různých velikostech a typech šachovnic. Nejznámější z těchto problémů je tzv. n-Queens problem, který řeší počet rozmístění n neohrožujících se dam na šachovnici n x n. O tomto problému byla napsána již spousta článků a základní informace a přehled linků je možno nalézt na mojí stránce links. Můj článek má ale širší záběr a věnuje se různým typům kamenů i šachovnic. Základ článku tvoří jeho verze z roku 1996, publikovaná v mé knize "Mezi šachovnicí a počítačem", str.204-206. Od roku 1996 došlo k výraznému zrychlení počítačů, což umožnilo získat další výsledky a odvodit řadu nových vzorců.

Content - Obsah

1.1 Queens on board n x n
1.2 Queens on board k x n
1.3 Conjectures for Q(n), n ® Ą
1.4 Queens on toroidal board n x n

2.1 Kings on board n x n
2.2 Kings on board k x n
2.3 Kings on boards of various size

3.1 Rooks on board n x n
3.2 Rooks on board k x n

4.1 Bishops on board n x n
4.2 Bishops on board k x n

5.1 Knights on board n x n
5.2 Knights on board k x n
5.3 Knights on cylindrical board n x n
5.4 Knights on toroidal board n x n

6.1 Nightriders on board n x n
6.2 Nightriders on board k x n

7.1 Amazons (superqueens) on board n x n
7.2 Amazons (superqueens) on board k x n

8.1 Zebras on board n x n
8.2 Zebras on board k x n

9.1 Wazirs on board n x n
9.2 Wazirs on board k x n

10. Other fairy pieces

1.1) Queens on board n x n - Dámy na šachovnici n x n

2 Queens, board nxn (E.Lucas, 1891): 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

V roce 2005 našel S.Perepechko pro tento můj vzorec zápis formálně sjednocující všech 6 případů. Sergey Perepechko (2005) convert these 6 formulas by Vaclav Kotesovec (1992) into 1 unified expression, kde [x]=floor(x) je celá část (largest integer not greater than x)
n(n-1)(45n⁶-855n⁵+6945n⁴-30891n³+78864n²-106226n+53404)/1080 + (n³-21/2*n²+28n-14)[n/2]+32/9(n-1)[n/3]+(16/9*n-4)[(n+1)/3]

Na základě řešení diferenční rovnice jsem ještě odvodil jiný jednotný vzorec pro tuto funkci (dávající pro celočíselné hodnoty n stejné výsledky):
n⁸/24 - 5n⁷/6 + 65n⁶/9 - 1051n⁵/30 + 817n⁴/8 - 19103n³/108 + 3989n²/24 - 18131n/270 + 253/54 + (n³/4 - 21n²/8 + 7n - 7/2)*(-1)ⁿ + 32(n-1)/27*COS(2*pi*n/3) + 40/81*3^(1/2)*SIN(2*pi*n/3)

Pro k dam na šachovnici n x n je odhad průběhu této funkce:
n^2k/k!-5/3n^2k-1/(k-2)!+O(n^2k-2)

Vzorce jsou i v On-Line Encyclopedia of Integer Sequences (Neil J. A. Sloane)
A036464 - 2Q NxN
A047659 - 3Q NxN
A061994 - 4Q NxN
A108792 - 5Q NxN - Sergey Perepechko, 2005 (pouze numericky pro n≤25)

Viz Edouard Lucas: Théorie des nombres (1891), vzorec pro počet rozmístění 2 neohrožujících se dam najdeme na str.98, dále je uveden též v knize Edouard Lucas: Récréations mathématiques (1894) str.132
Viz Naturwissenschaftliche wochenschrift (1896) - v čísle z 2.8.1896, str.367-371 (str.380 v PDF) je článek "Ueber das Achtdamenproblem und seine Verallgemeinerung", jehož autorem je Edmund Landau. V článku jsou odvozeny vzorce pro rozmístění 3 dam na šachovnici n x n (pro sudé a liché n). Je zajímavé, že tento slavný německý matematik objevil vzorec už ve svých 19 letech.

Této problematice byly věnovány také 2 články ve francouzském časopise "Rex Multiplex". Ve druhém byly publikovány moje nové výsledky.
Rex Multiplex 18/1986, (page 615, Louis Azemard, Echecs et Mathématiques) "Placements et Configurations pour 2, 3 et 4 Dames"
Rex Multiplex 38/1992, (Louis Azemard, Echecs et Mathématiques), "Une communication de Vaclav Kotesovec"

Poznámka: Panos Louridas publikoval v idee & form 93/2007 (str. 2936-2938) obecnější vzorec pro rozmístění 3 dam na šachovnici m x n. Vzorec je však dost neelegantní (zabírá skoro půl stránky), proto zájemce odkazuji na tento článek.

Tabulka udává rozmístění k dam na šachovnici nxn, diagonála odpovídá problému n-dam.

n	k=2	k=3	k=4	k=5	n queens, nxn
2	0				0
3	8	0			0
4	44	24	2		2
5	140	204	82	10	10
6	340	1024	982	248	4
7	700	3628	7002	4618	40
8	1288	10320	34568	46736	92
9	2184	25096	131248	310496	352
10	3480	54400	412596	1535440	724
11	5280	107880	1123832	6110256	2680
12	7700	199400	2739386	20609544	14200
13	10868	348020	6106214	60963094	73712
14	14924	579264	12654614	162323448	365596
15	20020	926324	24675650	396155466	2279184
16	26320	1431584	45704724	899046952	14772512
17	34000	2148048	80999104	1917743448	95815104
18	43248	3141120	138170148	3879011584	666090624
19	54264	4490256	227938788	7491080844	4968057848
20	67260	6291000	365106738	13892164232	39029188884
21	82460	8656860	569681574	24854703014	314666222712
22	100100	11721600	868289594	43071383040	2691008701644
23	120428	15641340	1295775946	72532831794	24233937684440
24	143704	20597104	1897176508	119038462248	227514171973736
25	170200	26797144	2729909796	190849299076	2207893435808352
26	200200	34479744	3866439956	?	22317699616364044
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	?	?

Zde je link na samotný "n-queens problem":
A000170 - NQ NxN - počty řešení na šachovnici NxN (Ways of placing n nonattacking queens on n x n board).

1.2) Queens on board k x n - Dámy na šachovnici k x n

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

3 Queens, board 3xn: (n-3)(n²-6n+12), (E.Pauls, 1874)

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)

8 Queens, board 8xn: n⁸-84n⁷+3378n⁶-85078n⁵+1467563n⁴-17723656n³+145910074n²-745654756n+1802501048, n>=31 (V.Kotesovec, 3.2.2010)

Podle mojí hypotézy mají obecně polynomy tvar: n^k - 3k(k-1)/2*n^k-1 + (9k⁴/8-29k³/12-k²/8+23k/12-1/4+(-1)^k/4)*n^k-2 - ...
(sekvence u třetího členu by tedy měla pokračovat takto: 0, 2, 30, 139, 407, 943, 1879, 3378, 5626, 8840, ...)

Tyto vzorce se dostaly i do OEIS
A061989 - 3Q 3xN
A061990 - 4Q 4xN
A061991 - 5Q 5xN
A061992 - 6Q 6xN
A061993 - 7Q 7xN
A172449 - 8Q 8xN

O autorech vzorců pro k=3 a k=4 se zmiňuje Wilhelm Ahrens ve své knize Mathematische Unterhaltungen und Spiele (vydání z roku 1921) na str.277.
Vzorec pro k=3 publikoval E.Pauls, "Das Maximalproblem der Damen auf dem Schachbrete", Deutsche Schachzeitung, 1874, str.261-263
Vzorec pro k=4 publikoval M. Harold Tarry na kongresu francouzských matematiků v roce 1890 v Limoges. Ve své přednášce uvedl i vzorce pro k=2 a k=3 a je proto v literatuře občas uváděn i jako autor těchto vzorců (vzorec pro k=3 však vymyslel již v roce 1874 E.Pauls). V Intermédiaire des Mathématiciens 1903, str.297-8 (str.682 v PDF) potom Tarry vyzval matematiky k nalezení obdobného vzorce pro šachovnici 5 x n, nikdo však takový vzorec nenalezl. Tento problém pak vyřešil až Václav Kotěšovec v roce 1992.

Poznámka: Ke stejným výsledkům (pro k=2,3,4,5,6) došli v článku Nonattacking queens in a rectangular strip (PDF) (na str.16) Thomas Zaslavsky, Seth Chaiken a Christopher R.H. Hanusa (2009). Bohužel jejich další výsledky (uvedené v tomto článku) pro střelce, jezdce a tátoše jsou chybné, protože uvažovali jen taková rozmístění, kde na každém řádku a sloupci stojí právě 1 kámen. To platí pro dámy a věže, ale v případě jiných kamenů může stát na jednom sloupci 2 i více neohrožujících se kamenů stejných hodnot.

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í (červená čí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	k=8	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	92
9	56	234	732	1614	2292	2038	1066	352
10	72	364	1400	3916	7552	9632	7828	724
11	90	536	2468	8492	21362	37248	44148	2680
12	110	756	4080	16852	52856	120104	195270	14200
13	132	1030	6404	31100	117694	335010	707698	73712
14	156	1364	9632	54068	241484	835056	2211868	365596
15	182	1764	13980	89428	463038	1897702	6120136	2279184
16	210	2236	19688	141812	838816	3998456	15324708	14772512
17	240	2786	27020	216932	1448002	7907094	35312064	95815104
18	272	3420	36264	321700	2398292	14818300	75937606	666090624
19	306	4144	47732	464348	3832374	26512942	153942964	4968057848
20	342	4964	61760	654548	5935120	45562852	296590536	39029188884
21	380	5886	78708	903532	8941514	75580634	546621416	314666222712
22	420	6916	98960	1224212	13145292	121520020	968910732	2691008701644
23	462	8060	122924	1631300	18908302	190031678	1659114170	24233937684440
24	506	9324	151032	2141428	26670584	289879092	2754780934	227514171973736
25	552	10714	183740	2773268	36961170	432420154	4449361442	2207893435808352
26	600	12236	221528	3547652	50409604	632159540	7009572728	22317699616364044
27	650	13896	264900	4487692	67758182	907376502	10796663102	?
28	702	15700	314384	5618900	89874912	1280833348	16292133888	?
29	756	17654	370532	6969308	117767194	1780569602	24128511810	?
30	812	19764	433920	8569588	152596220	2440786884	35125842896	?
31	870	22036	505148	10453172	195692094	3302829550	50334575910	?
32	930	24476	584840	12656372	248569672	4416266132	71085565752	?
33	992	27090	673644	15218500	312945122	5840076618	99047961338	?
34	1056	29884	772232	18181988	390753204	7643950612	136295785608	?
35	1122	32864	881300	21592508	484165270	9909701414	185384054238	?
36	1190	36036	1001568	25499092	595607984	12732801060	249435319880	?
37	1260	39406	1133780	29954252	727782762	16224041362	332237569362	?
38	1332	42980	1278704	35014100	883685932	20511325988	438354441528	?
39	1406	46764	1437132	40738468	1066629614	25741598622	573248773718	?
40	1482	50764	1609880	47191028	1280263320	32082912244	743420525208	?

1.3) Conjectures - Hypotézy o funkci Q(n) pro n ® Ą

Jeden z nejzajímavějších článků o problému N-dam je Igor Rivin, Ilan Vardi and Paul Zimmermann: The n-Queens Problem, The American Mathematical Monthly, 101 (7/1994), str.629-639. Autoři zde analyzují "klasický" problém N-dam a počet různých pozic označují Q(n). Pro mnohé bude překvapující, že neohrožující se dámy je možné rozestavit též na prstencové šachovnici (toroidal board) pro některá lichá n. Tuto funkci označují T(n).
(poznámka: Bernd Eickenscheidt dokázal v článku Das n-Damen-Problem auf dem Zylinderbrett (feenschach 50/1980, str.382-5), že v případě válcové nebo prstencové šachovnice má problém n-dam řešení jen pro taková n, která nejsou dělitelná 2 ani 3). Jak jsem však zjistil v literatuře, důkaz tohoto tvrzení provedl mnohem dříve již Polya.

1) Rivin, Vardi a Zimmermann vyslovují hypotézu o průběhu těchto funkcí. Obě funkce jsou podle nich řádu n^an, kde konstanta a < 1. Jaká je přesně hodnota obou konstant pro tyto funkce však není známo. (hodnoty jsem doplnil o aktuální výsledky, tehdy jen do n=20)

2) Jak se zdá, byla tato hypotéza vyvrácena - Dronninger pa et skakbrat - článek v dánštině z 27.9.2000, jehož autorem je Birger Nielsen. Vyslovuje zde hypotézu, že funkce Q(n) je řádu Q(n) ~ n!*p^(n-1), kde p=0.3885... Dokládá to výpočty pro N až do 23 a hodnota p je mimořádně stabilní (na rozdíl od konstant ve výše citovaném článku), z čehož lze usuzovat, že řada je možná konvergentní. Naprosto unikátní objev! (viz hodnoty v tabulce dále)

3) 10.11.2002 vyslovil podobnou hypotézu Benoit Cloitre, podle něj funkce 1/n*log(n!/Q(n)) pro n®Ą konverguje ke konstantě C~0.90... (added 10.12.2004). Je zajímavé, že mezi touto konstantou C a konstantou P z hypotézy B.Nielsena platí (pro n®Ą) jednoduchý vztah c=-log(p). Takže pokud p=0.3885..., muselo by být c=0.9454...

4) Další pozoruhodný výsledek publikovali 28.8.2008 Cheng Zhang and Jianpeng Ma. V článku Counting Solutions for the N-queens and Latin Square Problems by Efficient Monte Carlo Simulations (PDF) došli pomocí simulací metodou Monte Carlo k (zatím asi nejpřesnějšímu) vztahu:
log (n!/Q(n)) ~ 0.944001*n - 0.937
s maximální chybou 0.02 (pro n > 100)
Zatímco předchozí hypotézy vznikaly na základě pokusů o extrapolaci ze známých (přesných) výsledků, tedy pouze z něco přes 20 čísel, tento výsledek má jiný charakter. Autoři simulovali problém až do šachovnic N x N, kde N=10000. Takové výsledky, podložené teorií pravděpodobnosti, mají proto větší váhu. Jejich metoda nám sice nepřinese přesné hodnoty Q(n) pro jednotlivá N, ale u odhadů lze stanovit rozsah pravděpodobné chyby. Je to proto první rovnice, která není jen hypotézou, ale opravdovým výsledkem řešení tohoto problému. (viz hodnoty v tabulce dále)
Tento výsledek je téměř shodný s hypotézou Birger Nielsena, neboť přepočtem vychází Q(n) ~ e^0.937*n!*e^-0.944*n
po úpravách z toho dostaneme Q(n) ~ 2.552*n!*0.389ⁿ
což se dá napsat také jako Q(n) ~ 0.993*n!*0.389^(n-1)
a nyní už je na místě otázka, zda konstanta 0.993 nemá být spíš 1 ?
Pokud bychom obráceně vyšli z (elegantnější) hypotézy Birger Nielsena, lze ji převést do tvaru
log (n!/Q(n)) ~ 0.9454*n - 0.9454
Rozdíl je tedy pouze v tom, že zde jsou obě konstanty shodné.
A pro "c" ze vztahu Benoit Cloitrea dostáváme limitně přímo hodnotu 0.944001..., resp. 0.9454...

n	T(n)	log T(n)/(n log n)	Q(n)	log Q(n)/(n log n)	(Q(n)/n!)^(1/(n-1))	1/n*log(n!/Q(n))	(0.937+log(n!/Q(n))/n
1	1	-	1	-	-	-	-
2	0	-	0	-	-	-	-
3	0	-	0	-	-	-	-
4	0	-	2	0.12500	0.436790	0.6212266624	0.855476662
5	10	0.28613	10	0.28613	0.537285	0.4969813299	0.684381330
6	0	-	4	0.12895	0.353953	0.8654928084	1.021659475
7	28	0.24463	40	0.27081	0.446620	0.6908974152	0.824754558
8	0	-	92	0.27181	0.419382	0.7603517907	0.877476791
9	0	-	352	0.29651	0.420095	0.7709107004	0.875021812
10	0	-	724	0.28597	0.388049	0.8519621180	0.945662118
11	88	0.16974	2680	0.29926	0.382559	0.8735214338	0.958703252
12	0	-	14200	0.32063	0.387578	0.8688514376	0.946934771
13	4524	0.25243	73712	0.33612	0.388542	0.8726340743	0.944710997
14	0	-	365596	0.34669	0.385792	0.8844240718	0.951352643
15	0	-	2279184	0.36039	0.387849	0.8839962227	0.946462889
16	0	-	14772512	0.37213	0.388976	0.8852238369	0.943786337
17	140692	0.24612	95815104	0.38156	0.388506	0.8898319151	0.944949562
18	0	-	666090624	0.39050	0.388371	0.8932504953	0.945306051
19	820496	0.24341	4968057848	0.39908	0.388602	0.8954520716	0.944767861
20	0	-	39029188884	0.40703	0.388822	0.8974020412	0.944252041
21	0	-	314666222712	0.41408	0.388575	0.9002552664	0.944874314
22	0	-	2691008701644	0.42087	0.388583	0.9022838241	0.944874733
23	128850048	0.25894	24233937684440	0.42734	0.388717	0.9038217572	0.944560888
24	0	-	227514171973736	0.43341	0.388823	0.9052706563	0.944312323
25	1957725000	0.26586	2207893435808352	0.43904	0.388796	0.9069115985	0.944391599
26	0	-	22317699616364044	0.44438	0.388795	0.9083671268	0.944405588
27	0	-	?	?	?	?	?
28	0	-	?	?	?	?	?
29	605917055356	0.27782	?	?	?	?	?
30	0	-	?	?	?	?	?
31	13404947681712	0.28394	?	?	?	?	?
32	0	-	?	?	?	?	?
33	0	-	?	?	?	?	?
34	0	-	?	?	?	?	?
35	?	?	?	?	?	?	?
.
Ą		®1 ?		®1 ?	®0.3885... ?	®0.9454... ?	®0.9440... ?

Updated for n=24 (4.12.2004), for n=25 (25.6.2005) and for n=26 (21.1.2010)

Pokud přijmeme hypotézu B.Nielsena, pak s použitím Stirlingova vzorce n! ~ nⁿ e^-n Ö(2 p n) dostaneme

lim
n® Ą

ć
ç
č

log Q(n)

n log(n)

ö
÷
ř

a tím pádem obě konstanty z hypotézy Rivin+Vardi+Zimmermann ®1, což tuto hypotézu znehodnocuje.

Odkazy na jiné stránky s podobnou problematikou links

1.4) Queens on toroidal board n x n - Dámy na prstencové šachovnici n x n

2 Queens, toroidal board nxn:
n²(n-2)²/2, pro n sudé (even),
n²(n-1)(n-3)/2, pro n liché (odd)

3 Queens, toroidal board nxn:
n²(n-2)(n-4)(n²-6n+12)/6, pro n sudé (even), (V. Kotesovec, 31.1.2010)
n²(n-1)(n-3)(n²-8n+18)/6, pro n liché (odd), (V. Kotesovec, 31.1.2010)

4 Queens, toroidal board nxn:
Počet rozmístění 4 neohrožujících se dam na prstencové šachovnici se dá vyjádřit buď tímto jedním vzorcem nebo 12 vzorci odpovídajícími velikosti šachovnice (podle zbytku po dělení 12). Někoho možná překvapí funkce cosinus ve vzorci, taková řešení však jsou obvyklá, pokud charakteristická rovnice pro příslušnou diferenční rovnici má imaginární kořeny. Výsledné hodnoty jsou vždy celočíselné a nejmenší perioda je 12.
(n⁸/24 - n⁷ + 245n⁶/24 - 113n⁵/2 + 2843n⁴/16 - 593n³/2 + 4757n²/24) + (n⁶/8 - 5n⁵/2 + 305n⁴/16 - 129n³/2 + 629n²/8)*(-1)ⁿ + 8n²*COS(2*pi*n/3)/3 + 9n²*COS(pi*n/2)/2, (V. Kotesovec, 5.2.2010)

4 Queens toroidal nxn n=	n⁸	n⁷	n⁶	n⁵	n⁴	n³	n²	n¹	n⁰
12a	1/24	-1	31/3	-59	787/4	-361	284	0	0
12a+1	1/24	-1	121/12	-54	1269/8	-232	473/4	0	0
12a+2	1/24	-1	31/3	-59	787/4	-361	271	0	0
12a+3	1/24	-1	121/12	-54	1269/8	-232	489/4	0	0
12a+4	1/24	-1	31/3	-59	787/4	-361	280	0	0
12a+5	1/24	-1	121/12	-54	1269/8	-232	473/4	0	0
12a+6	1/24	-1	31/3	-59	787/4	-361	275	0	0
12a+7	1/24	-1	121/12	-54	1269/8	-232	473/4	0	0
12a+8	1/24	-1	31/3	-59	787/4	-361	280	0	0
12a+9	1/24	-1	121/12	-54	1269/8	-232	489/4	0	0
12a+10	1/24	-1	31/3	-59	787/4	-361	271	0	0
12a+11	1/24	-1	121/12	-54	1269/8	-232	473/4	0	0

Rekurentní vztah:
a_n = -a_n-1+3a_n-2+6a_n-3+3a_n-4-9a_n-5-20a_n-6-11a_n-7+15a_n-8+40a_n-9+31a_n-10-15a_n-11-53a_n-12-50a_n-13+50a_n-15+53a_n-16+15a_n-17-31a_n-18-40a_n-19-15a_n-20+11a_n-21+20a_n-22+9a_n-23-3a_n-24-6a_n-25-3a_n-26+a_n-27+a_n-28
(pro n>=29, člen n-14 má koeficient 0)

OEIS linky:
A172517 - 2Q toroidal NxN
A172518 - 3Q toroidal NxN
A172519 - 4Q toroidal NxN

n	2 queens	3 queens	4 queens
2	0	0	0
3	0	0	0
4	32	0	0
5	100	100	50
6	288	576	288
7	588	2156	2450
8	1152	7168	16384
9	1944	17496	62208
10	3200	41600	233600
11	4840	82280	638880
12	7200	161280	1755072
13	10140	280540	3901534
14	14112	486080	8772176
15	18900	774900	17051850
16	25088	1232896	33507328
17	32368	1844976	59175640
18	41472	2757888	105557904
19	51984	3933456	173570244
20	64800	5606400	287904000
21	79380	7699860	447885774
22	96800	10570560	702042000
23	116380	14081980	1044894554
24	139392	18754560	1565385984
25	165000	24365000	2247132500
26	194688	31647616	3244194304
27	227448	40258296	4519015596
28	264992	51204608	6326171264
29	306124	63979916	8590557654
30	352800	79934400	11716668000
31	403620	98348740	15567229390
32	460800	120995840	20763631616
33	522720	146884320	27070819380
34	591872	178301440	35416066816
35	666400	213914400	45416742700
36	749088	256628736	58421984832
37	837828	304690116	73833633570
38	935712	361739328	93571390608
39	1040364	425508876	116731332198
40	1155200	500505600	145991424000
41	1277560	583844920	180024039020
42	1411200	681045120	222499677456
43	1553160	788487560	271515768944
44	1707552	912862720	332023922560
45	1871100	1049687100	401355457650
46	2048288	1207000256	486095146064
47	2235508	1379308436	582569828310
48	2437632	1576194048	699422837760

(Hodnoty pro k=4 byly ověřeny výpočtem až do n=120)

Poznámka: Z matematického pohledu je zajímavější prstencová šachovnice než válcová (z šachového pohledu je to asi obráceně). V případě dam, věží nebo střelců jsou výsledky pro prstencovou šachovnici shodné jako pro válcovou šachovnici. V případě bodových kamenů (např. jezdců) to ale neplatí.
For queens, rooks and bishops are results for toroidal and cylindrical chessboard same, but for leapers (for example knights) are results different.

Zde je link na samotný "n-queens problem" na prstencové šachovnici:
A007705 - NQ NxN - počty řešení na prstencové šachovnici (Nonattacking queens on a 2n+1 x 2n+1 toroidal board).

2.1) Kings on board n x n - Králové na šachovnici n x n

Velmi zajímavý (i když poněkud jiný) je problém rozmístění neohrožujících se králů.

2 Kings, board nxn: (n-1)(n-2)(n²+3n-2)/2, (E. Lucas, 1891)

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

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

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

6 Kings, board nxn: (n¹²-135n¹⁰+180n⁹+7465n⁸-18840n⁷-202665n⁶+751860n⁵+2442334n⁴-13441200n³-3643800n²+89860320n-108217440)/720, n>=5, (V. Kotesovec, 27.1.2010)

Obecný vzorec není znám, ale první členy polynomu mají vždy tvar n^2k/k! - 9n^2k-2/2/(k-2)! + 6n^2k-3/(k-2)! ...

Tyto vzorce jsou i v OEIS
A061995 - 2K NxN
A061996 - 3K NxN
A061997 - 4K NxN
A061998 - 5K NxN
A172158 - 6K NxN

Viz Edouard Lucas: Théorie des nombres (1891), vzorec pro počet rozmístění 2 neohrožujících se králů najdeme na str.98 (ve vzorci vypadlo "/2"), viz též Edouard Lucas: Récréations mathématiques (1894) str.132 (i zde vypadlo "/2", v následujících dvou knihách Ahrense a Fabela je tento vzorec uveden správně).
Vzorec pro k=3 uvádí v knize Mathematische unterhaltungen und spiele (1901) Wilhelm Ahrens na str.155 s tím, že mu jej v dopise zaslal Edmund Landau.
Vzorec pro k=4 uvádí v knize Schach und Zahl (1966) na str.54 Karl Fabel.

n	2 kings	3 kings	4 kings	5 kings	6 kings
2	0	0	0
3	16	8	1	0	0
4	78	140	79	0	0
5	228	964	1987	1974	978
6	520	3920	16834	42368	62266
7	1020	11860	85275	397014	1220298
8	1806	29708	317471	2326320	12033330
9	2968	65240	962089	10087628	77784658
10	4608	129984	2515262	35464464	377818258
11	6840	240240	5882109	106783320	1492665418
12	9790	418220	12605095	285336128	5042436754
13	13596	693308	25175191	693331146	15062292834
14	18408	1103440	47443474	1558986816	40736208186
15	24388	1696604	85152487	3286192514	101489568538

2.2) Kings on board k x n - Králové na šachovnici k x n

2 kings, board 2xn: 2(n-1)(n-2)
3 kings, board 3xn: (n-2)(9n²-45n+70)/2, n>=2, (V. Kotesovec, 27.1.2010)
4 kings, board 4xn: (64n⁴-720n³+3347n²-7569n+6894)/6, n>=3, (V. Kotesovec, 27.1.2010)
5 kings, board 5xn: (625n⁵-9750n⁴+66415n³-247626n²+504664n-446544)/24, n>=4, (V. Kotesovec, 27.1.2010)
6 kings, board 6xn: 2(162n⁶-3240n⁵+29160n⁴-151830n³+483798n²-895085n+749335)/5, n>=5, (V. Kotesovec, 27.1.2010)
7 kings, board 7xn: (117649n⁷-2873997n⁶+32197753n⁵-215350695n⁴+932130286n³-2618213868n²+4424623272n-3468569760)/720, n>=6, (V. Kotesovec, 28.1.2010)
8 kings, board 8xn: (1048576n⁸-30277632n⁷+406210560n⁶-3319585920n⁵+18136811049n⁴-68048382318n³+171628664735n²-266425935930n+194935658400)/2520, n>=7, (V. Kotesovec, 30.1.2010)

První členy těchto vzorců mají obecně tvar (kn)^k/k! - 3(k-1)(3k-2)(kn)^k-1/2/k! + ...

OEIS linky:
A172202 - 3 kings 3 X n
A172203 - 4 kings 4 X n
A172204 - 5 kings 5 X n
A172205 - 6 kings 6 X n
A172206 - 7 kings 7 X n
A172261 - 8 kings 8 X n

n	2 kings	3 kings	4 kings	5 kings	6 kings	7 kings	8 kings
2	0	0	0	0	0	0	0
3	4	8	9	15	16	24	25
4	12	34	79	194	408	926	1847
5	24	105	454	1974	8544	37282	162531
6	40	248	1566	9856	62266	394202	2501726
7	60	490	4103	34475	291908	2484382	21243084
8	84	858	9009	95466	1021254	10999618	119138166
9	112	1379	17484	224589	2916232	38168864	502726650
10	144	2080	30984	468854	7179314	110899878	1724809105
11	180	2988	51221	893646	15790572	281638602	5059647669
12	220	4130	80163	1585850	31795390	643766432	13132889249
13	264	5533	120034	2656976	59638832	1352358921	30905051345
14	312	7224	173314	4246284	105546666	2651129458	67124176002
15	364	9230	242739	6523909	177953044	4906381466	136380034610
16	420	11578	331301	9693986	287974838	8648792662	261909043488
17	480	14295	442248	13997775	449932632	14623854922	479315827404
18	544	17408	579084	19716786	681918370	23851793294	841394145399
19	612	20944	745569	27175904	1006409660	37697787702	1424246670499
20	684	24930	945719	36746514	1450930734	57953320884	2334919892115
21	760	29393	1183806	48849626	2048760064	86929476107	3720787187147
22	840	34360	1464358	63959000	2839684634	127563008202	5780929883024
23	924	39858	1792159	82604271	3870800868	183536011462	8779782913128
24	1012	45914	2172249	105374074	5197362214	259410007946	13063328442266
25	1104	52555	2609924	132919169	6883673384	360775279732	19078137617070

2.3) Kings on boards of various size - Králové na šachovnicích jiných rozměrů

Maximální možný počet neohrožujících se králů na šachovnici n x n je n²/4 (pro n sudé) a (n²+1)/4 (pro n liché), více viz Kings Problem

Řadu výsledků najdeme v knize Schach und Zahl, 1966, jejíž autoři jsou E.Bonsdorff, K.Fabel, O.Riihimaa.

Number of ways to place n nonattacking kings on a 2 x 2n chessboard.
V citované knize na str.53 najdeme (pro tento jednoduchý případ) vzorec:
f₁(n) = (n+1)*2ⁿ

A061593 - Number of ways to place 2n nonattacking kings on a 4 x 2n chessboard.
Na str.53 knihy Schach und Zahl (1966) nalezneme i excelentní vzorec pro rozmístění 2m neohrožujících se králů na šachovnici 2m x 4, jehož autorem je C.Bandelow. Stejný vzorec najdeme v článku Nonattacking kings on a chessboard, D. E. Knuth, 1994.
f₂(n) = (17n-109)*3ⁿ+2*Fibonacci(2n+10)
Kdo by čekal v obecném vzorci Fibonacciho čísla? Explicitní tvar tohoto vzorce je
f₂(n) = (17n-109)*3ⁿ + 2/sqrt(5)*(((3+sqrt(5))/2)ⁿ⁺⁵ - ((3-sqrt(5))/2)ⁿ⁺⁵)
Ještě je možno poznamenat, že tato (poněkud divoká) funkce je řešením diferenční rovnice
a_n = 9a_n-1-28a_n-2+33a_n-3-9a_n-4

A061594 - Number of ways to place 3n nonattacking kings on a 6 x 2n chessboard
Herbert S. Wilf se dostal ještě trochu dál, když v článku The Problem of the Kings, Electronic Journal of Combinatorics (1995), uvedl pro šachovnici 6x2n a 3n neohrožujících se králů odhad:
f₃(n) = 231*n*4ⁿ - 2377*4ⁿ - 384*3ⁿ + O(1.707ⁿ)

Podařilo se mi najít přesný vzorec (exact formula by Vaclav Kotesovec, 5.2.2010):
f₃(n) = (231n-2377)*4ⁿ - 384*3ⁿ + (1953*sqrt(2)/2+1381+(35*sqrt(2)+99/2)*n)*(2+sqrt(2))ⁿ + (1381-1953*sqrt(2)/2+(99/2-35*sqrt(2))*n)*(2-sqrt(2))ⁿ

kde sqrt(2) = odmocnina ze 2. Je tedy vidět, že Wilfův odhad zbytku byl poněkud nepřesný, správně mělo být + O(n*3.4142ⁿ)
Příslušná diferenční rovnice je
a_n=19a_n-1 - 148a_n-2 + 604a_n-3 - 1364a_n-4 + 1644a_n-5 - 928a_n-6 + 192a_n-7

Herbert S. Wilf ve svém článku z roku 1995 dále uvádí, že pro 4n králů na šachovnici 8 x 2n má první člen podobné rovnice tvar
f₄(n) ~ (7963567/2610)*n*5ⁿ + ...

Zajímavé by bylo odvodit, jak se tato funkce chová pokud jde n do nekonečna. Z předchozích vzorců jde odhadnout tvar hlavního členu
f_m(n) ~ k_m*n*(m+1)ⁿ, hodnota "k" ale není konstanta, ale funkce závislá na "m".

Článek Non-attacking placements on chessboards (.ps), jehož autorem je Sergey Kitaev, má shodné výsledky a kromě králů řeší i rozmístění neohrožujících se pěšců na polích stejné barvy (number of nonattacking pawns, all of the same colour). V případě pěšců Sergey Kitaev a Toufik Mansour ještě došli k dalším výsledkům, které popisují v článku The Problem of the Pawns, Annals of Combinatorics (2004) (z článku je bohužel volně dostupný jen abstract). Jakási verze je k dispozici zde The problem of the pawns (2003)

Tabulku hodnot pro šachovnice typu 8 x 2n (pro n=1 až 10) nalezneme už v knize Schach und Zahl (1966), str.53. Je až neuvěřitelné, co dokázal při tehdejší úrovni počítačů Christoph Bandelow vypočítat.

n	kings	board	1n/2x2n	kings	board	2n/4x2n	kings	board	3n/6x2n	kings	board	4n/8x2n	kings	board	5n/10x2n
1	1	2x2	4	2	4x2	12	3	6x2	32	4	8x2	80	5	10x2	192
2	2	2x4	12	4	4x4	79	6	6x4	408	8	8x4	1847	10	10x4	7698
3	3	2x6	32	6	4x6	408	9	6x6	3600	12	8x6	26040	15	10x6	166368
4	4	2x8	80	8	4x8	1847	12	6x8	26040	16	8x8	281571	20	10x8	2580754
5	5	2x10	192	10	4x10	7698	15	6x10	166368	20	8x10	2580754	25	10x10	?
6	6	2x12	448	12	4x12	30319	18	6x12	976640	24	8x12	21137959	30	10x12	?
7	7	2x14	1024	14	4x14	114606	21	6x14	5392704	28	8x14	159636030	35	10x14	?
8	8	2x16	2304	16	4x16	419933	24	6x16	28432288	32	8x16	1134127305	40	10x16	?
9	9	2x18	5120	18	4x18	1501674	27	6x18	144605184	36	8x18	7683664202	45	10x18	?
10	10	2x20	11264	20	4x20	5266069	30	6x20	714611200	40	8x20	50123713793	50	10x20	?
11	11	2x22	24576	22	4x22	18174084	33	6x22	3449705600	44	8x22	?	55	10x22	?
12	12	2x24	53248	24	4x24	61892669	36	6x24	16333065216	48	8x24	?	60	10x24	?
13	13	2x26	114688	26	4x26	208424880	39	6x26	76081271168	52	8x26	?	65	10x26	?
14	14	2x28	245760	28	4x28	695179339	42	6x28	349524164224	56	8x28	?	70	10x28	?
15	15	2x30	524288	30	4x30	2299608732	45	6x30	1586790140800	60	8x30	?	75	10x30	?
16	16	2x32	1114112	32	4x32	7552444115	48	6x32	7130144209024	64	8x32	?	80	10x32	?
17	17	2x34	2359296	34	4x34	24648046806	51	6x34	31752978219904	68	8x34	?	85	10x34	?
18	18	2x36	4980736	36	4x36	79994460139	54	6x36	140298397039232	72	8x36	?	90	10x36	?
19	19	2x38	10485760	38	4x38	258339007890	57	6x38	615604372260736	76	8x38	?	95	10x38	?
20	20	2x40	22020096	40	4x40	830619734681	60	6x40	2684534626000512	80	8x40	?	100	10x40	?

A018807 - Number of ways to place n² nonattacking kings on 2n x 2n chessboard
Asi nejzajímavější je případ na obecné čtvercové šachovnici sudých rozměrů 2n x 2n, kam se vejde n² neohrožujících se králů. V tomto případě je výsledků zatím málo, alespoň odhad průběhu této funkce v článku The Problem of Kings (.ps file) - Michael Larsen (The electronic journal of combinatorics 2, 1995). Let f(n) the number of configurations of n² mutually non-attacking kings on a 2n x 2n chessboard
log f(n) = 2n log n - 2n log 2 + O(n^4/5log n)

3.1) Rooks on board n x n - Věže na šachovnici n x n

Na doplnění ještě uvádím vzorce pro počet postavení k neohrožujících se věží na šachovnici n x n. Jako jediný z těchto problémů byl tento zcela vyřešen, obecný vzorec je
k rooks, board nxn: (COMB(n,k))²*k!
kde COMB(n,k)=n!/k!/(n-k)! je kombinační číslo ("n nad k")
Objevit tento vzorec je poměrně snadné, cituje jej třeba už Wilhelm Ahrens Mathematische unterhaltungen und spiele (1901).

Speciálně pokud k=n, vychází počet možných pozic n neohrožujících se věží na šachovnici n x n roven n! (n faktoriál)
n rooks, board nxn: n!
2 rooks, board nxn: n²(n-1)²/2
3 rooks, board nxn: n²(n-1)²(n-2)²/6

Pro srovnání s ostatními vzorci, počet těchto kombinací je také polynom, po roznásobení dostaneme jeho koeficienty ve tvaru:
n!²/(n-k)!²/k! = n^2k/k! - n^2k-1/(k-2)! + n^2k-2/(k-2)!*(3k²-5k+1)/6 - ...

Problém byl vyřešen i na obdélníkových šachovnicích, počet pozic k neohrožujících se věží na šachovnici m x n je:
(m! n!) / ((m-k)! (n-k)! k!)

Viz též Rook Polynomial nebo Rook Polynomials

3.2) Rooks on board k x n - Věže na šachovnici k x n

Z předchozího vzorce pro obecnou obdélníkovou šachovici vyplývá (při m=k) tento vzorec pro
k rooks, board kxn: n!/(n-k)!

Pro srovnání s ostatními vzorci, počet těchto kombinací je také polynom, po roznásobení dostaneme jeho koeficienty ve tvaru:
n!/(n-k)! = n^k -
n^k-1*k(k-1)/2 +
n^k-2*k(k-1)(k-2)(3k-1)/24 -
n^k-3*k²(k-1)²(k-2)(k-3)/48 +
n^k-4*k(k-1)(k-2)(k-3)(k-4)(15k³-30k²+5k+2)/5760 -
n^k-5*k²(k-1)²(k-2)k-3)(k-4)(k-5)(3k²-7k-2)/11520 +
n^k-6*k(k-1)(k-2)(k-3)(k-4)(k-5)(k-6)(63k⁵-315k⁴+315k³+91k²-42k-16)/2903040 - ...

Obecně má nejvyšší člen každého rozvoje tvar:
n^k-i * k²ⁱ / 2ⁱ / i! + ...

4.1) Bishops on board n x n - Střelci na šachovnici n x n

Vzorce pro počet pozic neohrožujících se střelců na šachovnici n x n najdeme např. v knize Schach und Zahl, 1966 (str.58-62), jejímž autorem je Karl Fabel, který většinu následujících vzorců sám objevil.

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

3 bishops, board nxn: n(n-2)(2n⁴-4n³+7n²-6n+4)/12, pro n sudé (even), (K. Fabel, 1966)
3 bishops, board nxn: (n-1)(2n⁵-6n⁴+9n³-11n²+5n-3)/12, pro n liché (odd), (K. Fabel, 1966)

4 bishops, board nxn: n(n-2)(15n⁶-90n⁵+260n⁴-524n³+727n²-646n+348)/360, pro n sudé (even), (K. Fabel, 1966)
4 bishops, board nxn: (n-1)(n-2)(15n⁶-75n⁵+185n⁴-339n³+388n²-258n+180)/360, pro n liché (odd), (K. Fabel, 1966 - tento vzorec sice není v knize "Schach und Zahl" uveden, ale předpokládám, že ho také objevil - nyní jsem ho vygeneroval a potvrdil počítačem)

5 bishops, board nxn: n(n-2)(3n⁸-34n⁷+177n⁶-590n⁵+1435n⁴-2592n³+3326n²-2844n+1344)/360, pro n sudé (even), (V. Kotesovec, 26.1.2010)
5 bishops, board nxn: (n-1)(n-2)(n-3)(3n⁷-22n⁶+80n⁵-204n⁴+379n³-464n²+378n-270)/360, pro n liché (odd), (V. Kotesovec, 26.1.2010)

Obecný vzorec není znám, ale první členy polynomu mají vždy tvar n^2k/k! - 2n^2k-1/3/(k-2)! + ...
Zatímco v případě dam a věží byl vždy počet kamenů maximálně n (k≤n), v případě střelců (i jezdců) může být takový počet větší než n. Horní omezení pro maximální počet střelců je 2n-2, více viz Bishops Problem.

Linky na OEIS
A172123 - 2 bishops NxN
A172124 - 3 bishops NxN
A172127 - 4 bishops NxN
A172129 - 5 bishops NxN

Nevím kdo je autorem vzorce pro k=2, ale (kromě Fabela) jej cituje již Henry Dudeney ve své knize "Amusements in Mathematics" (1917), str.96.

n	2 bishops	3 bishops	4 bishops	5 bishops
2	4	0	0
3	26	26	8	0
4	92	232	260	112
5	240	1124	2728	3368
6	520	3896	16428	39680
7	994	10894	70792	282248
8	1736	26192	242856	1444928
9	2832	56296	706048	5865552
10	4380	110960	1809464	20014112
11	6490	204130	4199064	59673360
12	9284	355000	8992684	159698416
13	12896	589196	18024072	391202680
14	17472	940072	34170724	890095584
15	23170	1450134	61784632	1902427800
16	30160	2172576	107243472	3853570560
17	38624	3172944	179645376	7450556064
18	48756	4530912	291667440	13829016768
19	60762	6342186	460615272	24759442464
20	74860	8720520	709686228	42930138864
21	91280	11799860	1069477928	72328779720
22	110264	15736600	1579767068	118747638592
23	132066	20711966	2291594536	190443610280

4.2) Bishops on board k x n - Střelci na šachovnici k x n

2 bishops, board 2xn: 2n²-3n+2
3 bishops, board 3xn: (9n³-45n²+106n-108)/2, n>=4, (V. Kotesovec, 26.1.2010)
4 bishops, board 4xn: (32n⁴-336n³+1702n²-4701n+5844)/3, n>=9, (V. Kotesovec, 26.1.2010)
5 bishops, board 5xn: (625n⁵-11250n⁴+98875n³-515250n²+1566016n-2194944)/24, n>=16, (V. Kotesovec, 26.1.2010)
6 bishops, board 6xn: (648n⁶-17820n⁵+240930n⁴-2011545n³+10806047n²-35094560n+53430940)/10, n>=25, (V. Kotesovec, 28.1.2010)

První členy těchto vzorců mají obecně tvar (kn)^k/k! - (kn)^k-1(2k-1)/2/(k-2)! + ...
Jiný možný zápis je (kn)^k/k! - (kn)^k-1(2k-1)*comb(2k-1,2)/2/(k-1)! + ...
kde comb(2k-1,2) je kombinační číslo "2k-1 nad 2".

OEIS linky:
A172207 - 3 bishops 3 X n
A172208 - 4 bishops 4 X n
A172210 - 5 bishops 5 X n
A172211 - 6 bishops 6 X n

n	2 bishops	3 bishops	4 bishops	5 bishops	6 bishops
2	4	6	9	12	16
3	11	26	61	143	313
4	22	86	260	770	2320
5	37	211	927	3368	12160
6	56	426	2578	12632	53744
7	79	758	5965	38566	209428
8	106	1234	12066	98968	683524
9	137	1881	22135	222351	1905625
10	172	2726	37678	450682	4664384
11	211	3796	60457	843169	10297579
12	254	5118	92488	1479116	20907590
13	301	6719	136043	2460912	39664250
14	352	8626	193650	3917228	71114916
15	407	10866	268093	6006056	121559433
16	466	13466	362412	8917888	199459466
17	529	16453	479903	12878847	315906248
18	596	19854	624118	18153806	485124352
19	667	23696	798865	25049515	725031335
20	742	28006	1008208	33917724	1057839684
21	821	32811	1256467	45158308	1510706686
22	904	38138	1548218	59222392	2116429956
23	991	44014	1888293	76615476	2914190277
24	1082	50466	2281780	97900560	3950340692
25	1177	57521	2734023	123701269	5279242444
26	1276	65206	3250622	154704978	6964147544
27	1379	73548	3837433	191665937	9078128011
28	1486	82574	4500568	235408396	11705051758
29	1597	92311	5246395	286829730	14940605138
30	1712	102786	6081538	346903564	18893362144
31	1831	114026	7012877	416682898	23685900265
32	1954	126058	8047548	497303232	29455962998

5.1) Knights on board n x n - Jezdci na šachovnici n x n

Vzorce pro počet pozic neohrožujících se jezdců na šachovnici n x n.
2 knights, board nxn: (n-1)(n+4)(n²-3n+4)/2, (E.Lucas, 1891)

3 knights, board nxn: (n-2)(n+5)(n⁴-3n³-8n²+66n-108)/6, n>=4 , (K. Fabel, 1966)

4 knights, board nxn: (n⁸-54n⁶+144n⁵+1019n⁴-5232n³-2022n²+51120n-77184)/24, n>=6 (K. Fabel, 1966)

5 knights, board nxn: (n¹⁰-90n⁸+240n⁷+3235n⁶-16320n⁵-40530n⁴+396480n³-231656n²-3359520n+6509280)/120, n>=8 (V. Kotesovec, 25.1.2010)

Obecný vzorec není znám, ale první členy polynomu mají vždy tvar n^2k/k! - 9n^2k-2/2/(k-2)! + 12n^2k-3/(k-2)! +...
Také v případě jezdců může být jejich počet větší než n (pro šachovnici 8x8 dokonce 32), obecně je tento maximální počet n²/2 (pro n>2 sudé) a (n²+1)/2 (pro n>1 liché), více viz Knights Problem

Linky na OEIS
A172132 - 2 knights NxN
A172134 - 3 knights NxN
A172135 - 4 knights NxN
A172136 - 5 knights NxN

Viz Edouard Lucas: Théorie des nombres (1891), vzorec pro počet rozmístění 2 neohrožujících se jezdců najdeme na str.98 (zde jsou správně znaménka, ale vypadl znak "p"), viz též Edouard Lucas: Récréations mathématiques (1894), str.132 (ve vzorci je však tisková chyba, před členem p² má být +, ne -. Správně má být tedy (p-1)(p³+p²-8p+16)/2)

n	2 knights	3 knights	4 knights	5 knights
2	6	4	1
3	28	36	18	2
4	96	276	412	340
5	252	1360	4436	9386
6	550	4752	26133	97580
7	1056	13340	111066	649476
8	1848	32084	376560	3184708
9	3016	68796	1080942	12472084
10	4662	135040	2732909	41199404
11	6900	247152	6253408	119171110
12	9856	427380	13204356	309957412
13	13668	705144	26100160	739123094
14	18486	1118416	48819677	1639655452
15	24472	1715220	87137934	3422020324
16	31800	2555252	149398608	6778432292
17	40656	3711620	247349946	12833460256
18	51238	5272704	397168485	23356032940
19	63756	7344136	620696612	41051290730
20	78432	10050900	946921684	69954580804

5.2) Knights on board k x n - Jezdci na šachovnici k x n

2 knights, board 2xn: 2n²-3n+4, n>=2
3 knights, board 3xn: (9n³-45n²+122n-144)/2, n>=4, (V. Kotesovec, 26.1.2010)
4 knights, board 4xn: 8(4n⁴-36n³+170n²-450n+537)/3, n>=6, (V. Kotesovec, 26.1.2010)
5 knights, board 5xn: (625n⁵-8250n⁴+57235n³-242778n²+608440n-705984)/24, n>=8, (V. Kotesovec, 26.1.2010)
6 knights, board 6xn: (648n⁶-11340n⁵+103770n⁴-606645n³+2328317n²-5466660n+6051720)/10, n>=10, (V. Kotesovec, 26.1.2010)
7 knights, board 7xn: (117649n⁷-2571471n⁶+29223943n⁵-216954465n⁴+1114503256n³-3907492824n²+8562799512n-8962924320)/720, n>=12, (V. Kotesovec, 29.1.2010)

První členy těchto vzorců mají obecně tvar (kn)^k/k! - 3(k-1)(3k-4)(kn)^k-1/k!/2 + ...
Jiný možný zápis je (kn)^k/k! - comb(3k-3,2)*(kn)^k-1/k! + ...
kde comb(3k-3,2) je kombinační číslo "3k-3 nad 2".

OEIS linky:
A172212 - 3 knights 3 X n
A172213 - 4 knights 4 X n
A172214 - 5 knights 5 X n
A172215 - 6 knights 6 X n
A172217 - 7 knights 7 X n

n	2 knights	3 knights	4 knights	5 knights	6 knights	7 knights	8 knights
2	6	12	16	28	58	78	81
3	13	36	84	259	729	1758	4409
4	24	100	412	1968	8830	38588	175720
5	39	233	1416	9386	60285	383246	2479881
6	58	456	3640	30842	257318	2135344	17925691
7	81	796	7928	82738	858262	8891854	92952858
8	108	1280	15384	192336	2404448	30108310	379978716
9	139	1935	27352	400277	5879329	86669806	1286959255
10	174	2788	45432	763984	12927182	219845764	3765248749
11	213	3866	71480	1360797	26115008	504261973	9805497200
12	256	5196	107608	2291056	49238436	1065642840	23226916560
13	303	6805	156184	3681226	87675623	2104251027	50866495373
14	354	8720	219832	5687022	148787822	3924818982	104288896551
15	409	10968	301432	8496534	242366502	6973786593	202154535834
16	468	13576	404120	12333352	381127124	11884673662	373400685738
17	531	16571	531288	17459691	581249573	19532410762	661407061211
18	598	19980	686584	24179516	862965246	31097451768	1129334088897
19	669	23830	873912	32841667	1251190796	48140491605	1866838857216
20	744	28148	1097432	43842984	1776208532	72688612756	?
21	823	32961	1361560	57631432	2474393475	107333684073	?
22	906	38296	1670968	74709226	3388987070	155343835434	?
23	993	44180	2030584	95635956	4570917554	220788831789	?
24	1084	50640	2445592	121031712	6079666980	308680170138	?
25	1179	57703	2921432	151580209	7984184897	425126722984	?

5.3) Knights on cylindrical board n x n - Jezdci na válcové šachovnici n x n

Válcová šachovnice (vertical cylinder, Vertikalzylinder) je šachovnice stočená do válce tak, aby okrajové sloupce byly vedle sebe. Vertical cylinder - board with a- and h- files alongside one another.

2 knights, board nxn: n(n³-9n+12)/2, n>=5, (V. Kotesovec, 31.1.2010)
3 knights, board nxn: n(n-3)(n⁴+3n³-18n²-18n+164)/6, n>=6, (V. Kotesovec, 31.1.2010)
4 knights, board nxn: n(n⁷-54n⁵+72n⁴+1115n³-2616n²-8502n+26712)/24, n>=9, (V. Kotesovec, 31.1.2010)
5 knights, board nxn: n(n⁹-90n⁷+120n⁶+3395n⁵-8160n⁴-62130n³+204000n²+463464n-1888080)/120, n>=10, (V. Kotesovec, 31.1.2010)

První členy polynomu mají vždy tvar n^2k/k! - 9n^2k-2/2/(k-2)! + 6n^2k-3/(k-2)! + ...

Počet pozic na válcové šachovnici n x n je vždy dělitelný n (to odpovídá tomu, že každou pozici je možno libovolně posunout doleva nebo doprava aniž by se nějak změnilo vzájemné napadání kamenů.)

OEIS linky:
A172964 - 2 knights cylindrical NxN
A172965 - 3 knights cylindrical NxN
A172966 - 4 knights cylindrical NxN
A172967 - 5 knights cylindrical NxN

n	2 knights	3 knights	4 knights	5 knights
2	4	0	0	0
3	18	6	0	0
4	92	240	306	208
5	230	1010	2365	3210
6	522	4056	19047	58056
7	1022	12068	90503	458157
8	1808	30000	328324	2524176
9	2970	65628	981693	10587591
10	4610	130480	2547955	36576380
11	6842	240856	5933257	109008735
12	9792	418968	12681288	289450344
13	13598	694200	25284363	700477401
14	18410	1104488	47595023	1570789892
15	24390	1697820	85357395	3304892985
16	31712	2533856	146879312	6586928032
17	40562	3685668	243867873	12530769343
18	51138	5241600	392452803	22891446252

5.4) Knights on toroidal board n x n - Jezdci na prstencové šachovnici n x n

Prstencová šachovnice je kombinace vertikální a horizontální válcové šachovnice. Toroidal chessboard (anchor-ring) - board on which the a- and h-files are joined and the bottom and top ranks are also joined. The anchor-ring is a combination of the vertical and horizontal cylinders.

2 knights, board nxn: n²(n+3)(n-3)/2, n>=5, (V. Kotesovec, 31.1.2010)
3 knights, board nxn: n²(n⁴-27n²+218)/6, n>=6, (V. Kotesovec, 31.1.2010)
4 knights, board nxn: n²(n⁶-54n⁴+1115n²-8934)/24, n>=9, (V. Kotesovec, 31.1.2010)
5 knights, board nxn: n²(n⁸-90n⁶+3395n⁴-64290n²+522504)/120, n>=10, (V. Kotesovec, 31.1.2010)
6 knights, board nxn: n²(n¹⁰-135n⁸+8005n⁶-262665n⁴+4816354n²-39858840)/720, n>=13, (V. Kotesovec, 31.1.2010)

První členy polynomu mají vždy tvar n^2k/k! - 9n^2k-2/2/(k-2)! + (243k+143)*n^2k-4/24/(k-3)! - ...

Počet pozic na prstencové šachovnici n x n je vždy dělitelný n² (to odpovídá tomu, že každou pozici je možno libovolně posunout ve směru obou os x nebo y aniž by se nějak změnilo vzájemné napadání kamenů). V případě bodových kamenů se se zvětšujícím se n zmenšuje rozdíl mezi normální a prstencovou šachovnicí, naopak v případě liniových kamenů tento rozdíl zůstává.

OEIS linky:
A172529 - 2 knights toroidal NxN
A172530 - 3 knights toroidal NxN
A172531 - 4 knights toroidal NxN
A172532 - 5 knights toroidal NxN
A172533 - 6 knights toroidal NxN

n	2 knights	3 knights	4 knights	5 knights	6 knights	7 knights
2	2	0	0	0	0	0
3	18	6	0	0	0	0
4	88	208	228	128	56	16
5	200	600	600	120	0	0
6	486	3252	12357	30312	54972	80352
7	980	10584	68796	283906	764596	1359288
8	1760	27584	275888	1872064	8972896	31404480
9	2916	61992	872532	8643186	62560728	339256836
10	4550	125300	2344025	31702920	322246800	2527519400
11	6776	233772	5580762	98179400	1323868260	14053530964
12	9720	409584	12107196	267487920	4595943336	63100177488
13	13520	682084	24392446	659015500	14000143196	240356217660
14	18326	1089172	46261537	1496908840	38413461800	803630856504
15	24300	1678800	83426400	3179369070	96746410800	2416671974700
16	31616	2510592	144157632	6382030592	226834407552	6655251717376
17	40460	3657584	240119696	12207535134	500492572112	17015566051020
18	51030	5208084	387393921	22396355496	1048044384360	?
19	63536	7267652	607715342	39617305308	2096986629308	?
20	78200	9961200	929951100	67860021680	4031211268200	?

6.1) Nightriders on board n x n - Tátoši na šachovnici n x n

Vzorce pro počet pozic neohrožujících se tátošů na šachovnici n x n. Tátoš je liniový kámen s jednotkovým tahem jezdce. Nightrider is rider [1,2].

2 nightriders, board nxn: n(3n³-5n²+9n-4)/6, pro n sudé (even), (C. Poisson, Rex Multiplex 29/1990, p.829)
2 nightriders, board nxn: n(n-1)(3n²-2n+7)/6, pro n liché (odd), (C. Poisson, Rex Multiplex 29/1990, p.829)

Link v OEIS
A172141 - 2 nightriders NxN

n	2 nightriders	3 nightriders	4 nightriders
2	6	4	1
3	28	36	18
4	96	276	412
5	240	1152	3046
6	518	3920	17365
7	980	10568	68540
8	1712	25348	232164
9	2784	53848	655852
10	4310	106292	1680033
11	6380	194732	3855946
12	9136	339416	8279704
13	12688	562652	16532026
14	17206	899796	31456369
15	22820	1388008	56832396
16	29728	2083908	99009508
17	38080	3044992	165941072
18	48102	4356344	270328605
19	59964	6102144	427383994
20	73920	8404204	660479212
21	90160	11380564	996624154
22	108966	15199100	1476091049
23	130548	20019856	2144134416
24	155216	26067112	3066551576
25	183200	33551812	4315580852
26	214838	42766092	5994143473
27	250380	53981600	8213049038
28	290192	67570804	11127498228
29	334544	83876732	14901856642
30	383830	103365728	19763006661
31	438340	126463668	25947796192
32	498496	153745412	33779182556
33	564608	185732188	43590211584
34	637126	223122948	55829979313
35	716380	266547472	70956669486
36	802848	316845560	89582262248
37	896880	374769664	112325177234
38	998982	441318188	140004466369
39	1109524	517381252	173440817244
40	1229040	604134684	213712999188
41	1357920	702622052	?
42	1496726	814216544	?
43	1645868	940132020	?
44	1805936	1081959860	?
45	1977360	1241101728	?
46	2160758	1419389236	?
47	2356580	1618430292	?
48	2565472	1840319784	?
49	2787904	2086891176	?
50	3024550	2360526732	?
51	3275900	2663305556	?
52	3542656	2997922516	?
53	3825328	3366723560	?
54	4124646	3772742240	?
55	4441140	4218613152	?
56	4775568	4707735876	?
57	5128480	5243056424	?
58	5500662	5828368716	?
59	5892684	6466953812	?
60	6305360	7163029360	?
61	6739280	7920235852	?
62	7195286	8743245188	?
63	7673988	9636082848	?
64	8176256	10603906308	?
65	8702720	11651152152	?
66	9254278	12783496072	?
67	9831580	14005812832	?
68	10435552	15324329940	?
69	11066864	16744388300	?
70	11726470	18272801892	?
71	12415060	19915406448	?
72	13133616	21679638248	?
73	13882848	23571857756	?
74	14663766	25600160124	?
75	15477100	27771460968	?
76	16323888	30094552244	?
77	17204880	32576936124	?
78	18121142	35228140248	?
79	19073444	38056285612	?
80	20062880	41071675484	?
81	21090240	44283082684	?
82	22156646	47701627220	?
83	23262908	51336767992	?
84	24410176	55200483576	?
85	25599280	59302953672	?
86	26831398	63657058652	?
87	28107380	68273734740	?
88	29428432	73166808260	?
89	30795424	78348008556	?
90	32209590	83832153128	?
91	33671820	89631801732	?
92	35183376	95762809460	?
93	36745168	102238605096	?
94	38358486	109076128388	?
95	40024260	116289716172	?
96	41743808	123897441384	?
97	43518080	131914588952	?
98	45348422	140360414436	?
99	47235804	149251191772	?
100	49181600	158607409644	?

Pro 3 a 4 tátoše se mi zatím nepodařilo objevit vzorec (nefunguje ani rozdělení na sudé/liché, typy 6n, 6n+1, apod.)
Odhad pro k=3 je n⁶ - 5/6*n⁵ + ...

6.2) Nightriders on board k x n - Tátoši na šachovnici k x n

2 nightriders, board 2xn: 2n²-3n+4, n>=2
3 nightriders, board 3xn: (9n³-57n²+210n-344)/2, n>=8, (V. Kotesovec, 26.1.2010)
4 nightriders, board 4xn: (32n⁴-432n³+3190n²-13323n+25530)/3, n>=18, (V. Kotesovec, 26.1.2010)
5 nightriders, board 5xn: (625n⁵-15250n⁴+197915n³-1588634n²+7645896n-17283552)/24, n>=32, (V. Kotesovec, 28.1.2010)

OEIS linky:
A172218 - 3 nightriders 3 X n
A172219 - 4 nightriders 4 X n
A172220 - 5 nightriders 5 X n

n	2 nightriders	3 nightriders	4 nightriders	5 nightriders	6 nightriders
2	6	12	16	28	58
3	13	36	84	157	315
4	24	100	412	1248	3862
5	39	213	1126	4650	19419
6	58	408	2760	15162	85358
7	81	712	5739	37988	256549
8	108	1148	10982	86958	706060
9	139	1745	19695	181423	1689706
10	174	2528	33068	351708	3745158
11	213	3524	52801	648441	7737606
12	256	4760	80638	1127392	15042498
13	303	6263	118731	1874194	28033286
14	354	8060	169368	2988466	49685456
15	409	10178	235135	4602096	84688103
16	468	12644	318890	6870240	138994668
17	531	15485	423733	9983347	220999518
18	598	18728	553028	14163972	341148264
19	669	22400	710389	19672403	513146177
20	744	26528	899690	26812260	753927570
21	823	31139	1125059	35929480	1084629369
22	906	36260	1390880	47418482	1530923606
23	993	41918	1701793	61723238	2123729778
24	1084	48140	2062694	79341720	2900209972
25	1179	54953	2478735	100828175	3904141919
26	1278	62384	2955324	126796852	?
27	1381	70460	3498125	157924785	?
28	1488	79208	4113058	194954956	?
29	1599	88655	4806299	238699512	?
30	1714	98828	5584280	290042826	?
31	1833	109754	6453689	349944662	?
32	1956	121460	7421470	419443276	?
33	2083	133973	8494823	499658555	?
34	2214	147320	9681204	591795132	?
35	2349	161528	10988325	697145517	?
36	2488	176624	12424154	817093220	?
37	2631	192635	13996915	953115876	?
38	2778	209588	15715088	1106788370	?
39	2929	227510	17587409	1279785962	?
40	3084	246428	19622870	1473887412	?

7.1) Amazons (superqueens) on board n x n - Amazonky na šachovnici n x n

Amazonka je kombinovaný kámen s pohyblivostí dámy a jezdce. Amazon (=Superqueen) is queen + knight.

2 amazons, board nxn: (n-1)(n-2)(n-3)(3n+8)/6, (Christian Poisson, 1990)

3 amazons, board nxn: (2n⁶-20n⁵+31n⁴+314n³-1452n²+2040n-672)/12, pro sudá n (even), n>=4, (Panos Louridas, 2007)
3 amazons, board nxn: (2n⁶-20n⁵+31n⁴+314n³-1452n²+2034n-669)/12, pro lichá n (odd), n>=5, (Panos Louridas, 2007)

I když máme zatím příliš málo hodnot, je pravděpodobný průběh této funkce pro k amazonek na šachovnici n x n podobný jako pro dámy:
n^2k/k! - 5/3*n^2k-1/(k-2)! + ...

OEIS linky:
A172200 - 2 amazons (superqueens) n X n
A172201 - 3 amazons (superqueens) n X n

Odkazy:
Christian Poisson, Rex Multiplex 29/1990, str. 829 (v té době vycházející francouzský časopis)
Panos Louridas, idee & form 93/2007, str. 2936-2938 (švýcarský časopis věnovaný skladebnímu šachu)

n	2 amazons	3 amazons	4 amazons
2	0	0	0
3	0	0	0
4	20	0	0
5	92	48	2
6	260	424	112
7	580	1976	1754
8	1120	6616	13074
9	1960	17852	63400
10	3192	41544	234014
11	4920	86660	712248
12	7260	166288	1882132
13	10340	298616	4457246
14	14300	508200	9679760
15	19292	827168	19584514
16	25480	1296744	37367934
17	33040	1968676	67849336
18	42160	2907016	118085614
19	53040	4189772	198107620
20	65892	5910944	321870956
21	80940	8182400	508359070
22	98420	11136168	782972820
23	118580	14926536	1179105738
24	141680	19732600	1740089734
25	167992	25760588	2521359260
26	197800	33246664	3593085246
27	231400	42459476	5043058972
28	269100	53703216	6980158088
29	311220	67320392	9538095102
30	358092	83695144	12879874324
31	410060	103256240	17202560582
32	467480	126480648	22742900942
33	530720	153896756	29783283628
34	600160	186088200	38658709554
35	676192	223697308	49764125812
36	759220	267429184	63562947328
37	849660	318055376	80595959410
38	947940	376418216	101491605140
39	1054500	443434712	126976666126
40	1169792	520101144	157888541850

Problémem n neohrožujících se amazonek na šachovnici n x n se jako první zabýval matematik s přezdívkou Durango Bill, na jeho stránce Durango Bill's - The N-Queens Problem najdeme doposud známé výsledky. Na první pohled se zdá že takové rozestavení pro Amazonky (označované zde jako Superqueen) není možné, ale od šachovnice 10x10 taková řešení existují! Solution exist also for Amazone, N≥10 !
Zkusil jsem vypočítat konstanty pro amazonky podle prvních dvou hypotéz (recomputing constants by both conjectures)
Pro posouzení konvergence obou řad je však zatím k dispozici málo hodnot...

                                                         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        495864256       61984976  0.3090010139 0.3341722647
      21         314666222712        39333324973       3977841852      497236090  0.3122951071 0.3457263661
      22        2691008701644       336376244042      34092182276     4261538564  0.3156003918 0.3566365819
      23       24233937684440      3029242658210     306819842212    38352532487  0.3186994535 0.3667617725
      24      227514171973736     28439272956934    2883202816808   360400504834  0.3215646055 0.3761463830
      25     2207893435808352    275986683743434   28144109776812  3518014210402  0.3241760378 0.3848344687
      26    22317699616364044   2789712466510289                ?              ?             ?            ?

Hodnoty pro N=24 a N=25 vypočítal Wolfram Schubert (2009), (updated 22.1.2010)
Hodnoty pro N=21 až 23 (updated 27.3.2007) jsou převzaty ze stránky "The Oprisch Family Web Site" N x N SuperQueens Solutions Table.

7.2) Amazons (superqueens) on board k x n - Amazonky na šachovnici k x n

Na stránce The Oprisch Family Web Site nalezneme také hodnoty i pro šachovnice k x n, včetně vzorců pro k = 2,3,4,5,6,7 a tabulek hodnot.
2xn:   (n-3)*(n-2), n > 3
3xn:   (n-6)*(n-5)*(n-4), n > 6
4xn:   [(n-7)*(n-6)*(n-5)*(n-4)+(n-10)*(n-9)*(n-8)*(n-7)]/2, n > 7
5xn:   n⁵ -44n⁴ +823n³ -8168n² +42796n -93984, n > 11
6xn:   n⁶ -63n⁵ +1775n⁴ -28613n³ +277462n² -1526716n +3699966, n > 16
7xn:   n⁷ -85n⁶ +3329n⁵ -77911n⁴ +1175240n³ -11392990n² +65448630n -171006180, n > 23

Obecně má polynom tvar: n^k - (k+3)(3k-4)n^k-1/2 + ...

Stejné hodnoty nalezneme také zde: OEIS - A051223, A051224

8.1) Zebras on board n x n - Zebry na šachovnici n x n

Vzorce pro počet pozic neohrožujících se zeber (skokanů [2,3]) na šachovnici n x n. Zebra is leaper [2,3].

2 zebras, board nxn: (n⁴-9n²+40n-48)/2, n>=2, (C. Poisson, Rex Multiplex 29/1990, p.829)

3 zebras, board nxn: (n⁶-27n⁴+120n³+74n²-1608n+2976)/6, n>=6, (V. Kotesovec, 24.1.2010)

4 zebras, board nxn: (n⁸-54n⁶+240n⁵+827n⁴-8592n³+10362n²+75600n-204864)/24, n>=9, (V. Kotesovec, 24.1.2010)

5 zebras, board nxn: (n¹⁰-90n⁸+400n⁷+2915n⁶-26880n⁵+2430n⁴+609920n³-1517496n²-4188480n+16581120)/120, n>=12, (V. Kotesovec, 26.1.2010)

Obecný vzorec není znám, ale první členy polynomu mají vždy tvar n^2k/k! - 9n^2k-2/2/(k-2)! + 20n^2k-3/(k-2)! +...

Linky na OEIS
A172137 - 2 zebras NxN
A172138 - 3 zebras NxN
A172139 - 4 zebras NxN
A172140 - 5 zebras NxN

n	2 zebras	3 zebras	4 zebras	5 zebras
2	6	4	1
3	36	84	126	126
4	112	452	1168	2032
5	276	1772	7334	20502
6	582	5596	35749	160696
7	1096	14888	137970	929880
8	1896	34640	438984	4117520
9	3072	72712	1208246	15037036
10	4726	140716	2969389	47368960
11	6972	255036	6662480	132577826
12	9936	437968	13873100	336828368
13	13756	718980	27144408	789558314
14	18582	1136092	50389581	1729320120
15	24576	1737376	89424014	3574328936
16	31912	2582576	152638280	7027309888
17	40776	3744848	251834530	13226773092
18	51366	5312620	403250693	23959787480
19	63892	7391572	628798516	41954706558
20	78576	10106736	957543164	71276149776
21	95652	13604716	1427453780	117848892710
22	115366	18056028	2087456085	190142197976

8.2) Zebras on board k x n - Zebry na šachovnici k x n

2 zebras, board 2xn: n(2n-1), =all combinations
3 zebras, board 3xn: (9n³-21n²+50n-48)/2, n>=6, (V. Kotesovec, 26.1.2010)
4 zebras, board 4xn: 4(8n⁴-48n³+202n²-471n+507)/3, n>=9, (V. Kotesovec, 26.1.2010)
5 zebras, board 5xn: 5(125n⁵-1250n⁴+7575n³-28426n²+64000n-67056)/24, n>=12, (V. Kotesovec, 26.1.2010)
6 zebras, board 6xn: (1944n⁶-27540n⁵+227070n⁴-1222555n³+4366071n²-9580580n+9925860)/30, n>=15, (V. Kotesovec, 26.1.2010)

První členy těchto vzorců mají obecně tvar (kn)^k/k! - (k-1)(9k-20)(kn)^k-1/2/k! + ...

OEIS linky:
A172221 - 3 zebras 3 X n
A172222 - 4 zebras 4 X n
A172223 - 5 zebras 5 X n
A172224 - 6 zebras 6 X n

n	2 zebras	3 zebras	4 zebras	5 zebras	6 zebras
2	6	20	70	252	924
3	15	84	406	1925	8989
4	28	200	1168	6534	37270
5	45	403	2948	20502	145233
6	66	720	6576	57710	525796
7	91	1180	13122	142312	1605490
8	120	1808	23808	308254	4136952
9	153	2631	40168	606051	9435413
10	190	3676	63996	1105332	19632414
11	231	4970	97344	1897899	37957424
12	276	6540	142516	3100250	69050898
13	325	8413	202072	4857000	119351315
14	378	10616	278828	7344010	197524064
15	435	13176	375856	10771530	314935542
16	496	16120	496484	15387310	486171662
17	561	19475	644296	21479725	729604121
18	630	23268	823132	29380900	1068003424
19	703	27526	1037088	39469835	1529198580
20	780	32276	1290516	52175530	2146783422
21	861	37545	1588024	67980110	2960869583
22	946	43360	1934476	87421950	4018886128
23	1035	49748	2334992	111098800	5376425842
24	1128	56736	2794948	139670910	7098138174
25	1225	64351	3319976	173864155	9258668837

9.1) Wazirs on board n x n - Vezíři na šachovnici n x n

Vzorce pro počet pozic neohrožujících se vezírů (skokanů [0,1]) na šachovnici n x n. Wazir is leaper [0,1].

2 wazirs, board nxn: n(n-1)(n²+n-4)/2, (C. Poisson, 1990)
3 wazirs, board nxn: (n-2)(n⁵+2n⁴-11n³-10n²+42n-12)/6, n>=2 (V. Kotesovec, 29.1.2010)
4 wazirs, board nxn: (n⁸-30n⁶+24n⁵+323n⁴-504n³-1110n²+2760n-1224)/24, n>=4, (V. Kotesovec, 29.1.2010)
5 wazirs, board nxn: (n¹⁰-50n⁸+40n⁷+995n⁶-1560n⁵-8890n⁴+21080n³+24264n²-97440n+59520)/120, n>=5, (V. Kotesovec, 29.1.2010)

Obecný vzorec není znám, ale první členy polynomu mají vždy tvar n^2k/k! - 5n^2k-2/2/(k-2)! + ...

OEIS linky:
A172225 - 2 wazirs n X n
A172226 - 3 wazirs n X n
A172227 - 4 wazirs n X n
A172228 - 5 wazirs n X n

n	2 wazirs	3 wazirs	4 wazirs	5 wazirs
2	2	0	0
3	24	22	9	1
4	96	276	405	359
5	260	1474	5024	10741
6	570	5248	31320	127960
7	1092	14690	133544	870589
8	1904	35012	446421	4197456
9	3096	74326	1258590	16005187
10	4770	144544	3126724	51439096
11	7040	262398	7042930	145085447
12	10032	450580	14669709	369074128
13	13884	739002	28658436	863338777
14	18746	1166176	53069000	1883786680
15	24780	1780714	93909924	3875953561
16	32160	2642948	159819965	7583888944
17	41072	3826670	262913874	14206566327
18	51714	5420992	419816676	25617069208
19	64296	7532326	652912510	44663199283
20	79040	10286484	991835749	75572017136

9.2) Wazirs on board k x n - Vezíři na šachovnici k x n

2 wazirs, board 2xn: 2(n-1)²
3 wazirs, board 3xn: (3n-5)(3n²-8n+8)/2, n>=2, (V. Kotesovec, 29.1.2010)
4 wazirs, board 4xn: (64n⁴-432n³+1235n²-1797n+1122)/6, n>=3, (V. Kotesovec, 29.1.2010)
5 wazirs, board 5xn: (625n⁵-5750n⁴+23535n³-54202n²+70640n-41616)/24, n>=4, (V. Kotesovec, 29.1.2010)
6 wazirs, board 6xn: 2*(486n⁶-5670n⁵+30240n⁴-95230n³+187899n²-220775n+120540)/15, n>=5, (V. Kotesovec, 29.1.2010)
7 wazirs, board 7xn: (117649n⁷-1663893n⁶+10942729n⁵-43685355n⁴+114945646n³-199980312n²+213228096n-107390880)/720, n>=6, (V. Kotesovec, 29.1.2010)

První členy těchto vzorců mají obecně tvar (kn)^k/k! - (k-1)(5k-2)*(kn)^k-1/2/k! + ...

OEIS linky:
A172229 - 3 wazirs 3 X n
A172230 - 4 wazirs 4 X n
A172231 - 5 wazirs 5 X n
A172232 - 6 wazirs 6 X n
A172234 - 7 wazirs 7 X n

n	2 wazirs	3 wazirs	4 wazirs	5 wazirs	6 wazirs	7 wazirs
2	2	2	2	2	2	2
3	8	22	61	174	504	1478
4	18	84	405	1998	10010	50726
5	32	215	1502	10741	78052	573797
6	50	442	4072	38438	368868	3581924
7	72	792	9091	107004	1280832	15516804
8	98	1292	17791	251354	3612344	52550366
9	128	1969	31660	522528	8774380	149162199
10	162	2850	52442	990816	19049692	370817854
11	200	3962	82137	1748883	37898664	831571604
12	242	5332	123001	2914894	70311824	1717417198
13	288	6987	177546	4635639	123209012	3316210152
14	338	8954	248540	7089658	205885204	6054985120
15	392	11260	339007	10490366	330502992	10545491888
16	450	13932	452227	15089178	512631720	17638773534
17	512	16997	591736	21178634	771833276	28489610297
18	578	20482	761326	29095524	1132294540	44631652698
19	648	24414	965045	39224013	1623506488	68064067456
20	722	28820	1207197	51998766	2280989952	101350519742

10) Other fairy pieces - další exokameny

Další vzorce pro rozmístění neohrožujících se exokamenů publikoval Christian Poisson v roce 1990 ve francouzském časopise Rex Multiplex. Celkem 44 vzorců (převážně vždy pro rozmístění 2-3 kamenů) vyšlo ve dvou pokračováních Rex Multiplex 29/1990, str. 829-830 a Rex Multiplex 30/1990, str. 914-915.

Nejzajímavější je tento pěkný obecný vzorec pro rozmístění dvou skokanů [x,y]
Two leapers [x,y] on chessboard n x n:

x >= y >= 0 and x+y <> 0
(n⁴-9n²+8(x+y)n-8xy)/2, for x <> y <> 0, n>=x
(n⁴-5n²+4(x+y)n-4xy)/2, for x=y or y=0, n>=x

Speciálně pro x=3 a y=2 dostaneme shodný vzorec pro 2 Zebry, pro x=1 a y=0 dostaneme shodný vzorec pro 2 Vezíry.

Jak jsem však nyní zjistil, tyto vzorce už objevil Edouard Lucas v roce 1891, když ve své knize Théorie des nombres uvádí na str.97 obecnější vzorec pro počet ohrožujících se skokanů [r,s] na šachovnici p x q
(2p - r - s)(2q - r - s) - (r - s)²
Když v tomto vzorci položíme p = q = n a uvědomíme-li si, že celkový počet kombinací 2 kamenů na šachovnici n x n je n² nad 2, dostáváme odtud pro počet neohrožujících se skokanů [r,s] výraz
n²(n²-1)/2 - (4n² - 4n(r + s) + 4rs) = (n⁴ - 9n² + 8n(r + s) - 8rs)/2, což odpovídá výše uvedenému vzorci

home page

Number of ways of placing non-attackingqueens, kings, bishops and knights