Polyknight

From Wikipedia, the free encyclopedia
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 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, 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, 6681, Springer, pp. 90–99, doi:10.1007/978-3-642-21204-8_13 .
  2. ^ Redelmeier, D. Hugh (1981), "Counting polyominoes: yet another attack", Discrete Mathematics, 36: 191–203, doi:10.1016/0012-365X(81)90237-5 
Retrieved from "https://en.wikipedia.org/w/index.php?title=Polyknight&oldid=656823645"
This content was retrieved from Wikipedia : http://en.wikipedia.org/wiki/Polyknight
This page is based on the copyrighted Wikipedia article "Polyknight"; it is used under the Creative Commons Attribution-ShareAlike 3.0 Unported License (CC-BY-SA). You may redistribute it, verbatim or modified, providing that you comply with the terms of the CC-BY-SA