Polyknight

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

Polyknight
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]

Enumeration of polyknights

Free, one-sided, and fixed polyknights

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

  • free polyknights are distinct when none is a rigid transformation (translation, rotation, reflection or glide reflection) of another (pieces that can be picked up and flipped over).
  • one-sided polyknights are distinct when none is a translation or rotation of another (pieces that cannot be flipped over).
  • fixed polyknights are distinct when none is a translation of another (pieces that can be neither flipped nor rotated).

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

n free one-sided fixed
1 1 1 1
2 1 2 4
3 6 8 28
4 35 68 234
5 290 550 2,162
6 2,680 5,328 20,972
7 26,379 52,484 209,608
8 267,598 534,793 2,135,572
9 2,758,016 5,513,338 22,049,959
10 28,749,456 57,494,308 229,939,414
OEIS A030446 A030445 A030444
Free polyknights
  • The 290 free pentaknights.
    The 290 free pentaknights.
  • The 2,680 free hexaknights.
    The 2,680 free hexaknights.

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

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.