Polyknight

Last updated
The 35 free tetraknights Tetraknights.png
The 35 free tetraknights

A polyknight is a plane geometric figure formed by selecting cells in a square lattice that could represent the path of a chess knight in which doubling back is allowed. It is a polyform with square cells which are not necessarily connected, comparable to the polyking. Alternatively, it can be interpreted as a connected subset of the vertices of a knight's graph, a graph formed by connecting pairs of lattice squares that are a knight's move apart. [1]

Contents

Enumeration of polyknights

Free, one-sided, and fixed polyknights

Three common ways of distinguishing polyominoes for enumeration [2] can also be extended to polyknights:

The following table shows the numbers of polyknights of various types with n cells.

nfreeone-sidedfixed
1111
2124
36828
43568234
52905502,162
62,6805,32820,972
726,37952,484209,608
8267,598534,7932,135,572
92,758,0165,513,33822,049,959
1028,749,45657,494,308229,939,414
OEIS A030446 A030445 A030444

Notes

  1. ↑ Aleksandrowicz, Gadi; Barequet, Gill (2011), "Parallel enumeration of lattice animals", in Atallah, Mikhail J.; Li, Xiang-Yang; Zhu, Binhai (eds.), Frontiers in Algorithmics and Algorithmic Aspects in Information and Management - Joint International Conference, FAW-AAIM 2011, Jinhua, China, May 28-31, 2011. Proceedings, Lecture Notes in Computer Science, vol. 6681, Springer, pp. 90–99, doi:10.1007/978-3-642-21204-8_13, ISBN   978-3-642-21203-1 .
  2. ↑ Redelmeier, D. Hugh (1981), "Counting polyominoes: yet another attack", Discrete Mathematics, 36 (2): 191–203, doi: 10.1016/0012-365X(81)90237-5
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.