|
| |
|
|
A165143
|
|
Length of longest cyclic knight path on an n X n chessboard that is determined (up to starting point and direction) by the fields visited.
|
|
2
|
| |
|
|
|
OFFSET
|
3,1
|
|
|
COMMENTS
|
More mathematically, a(n) is also the biggest possible number of vertices (or edges) of a circular graph in the plane with all vertices being distinct and having integer coordinates between 1 and n, inclusive, and all edges having length sqrt(5).
Opinions on a(1) and a(2) may differ: The only possible circular path consists of staying at the starting field, hence we have 1 field visited (thus a(1) = a(2) = 1) or it takes 0 knight moves to complete the tour (thus a(1) = a(2) = 0). The graph with one vertex and no edges is not considered a cyclic graph since all vertices must have degree two; even adding a loop edge would produce an edge of length 0 (thus a(1) and a(2) are either undefined or = 0 if one accepts the empty graph as cyclic).
Put another way, a(n) is the length of a longest induced cycle in the n X n knight graph. - Pontus von Brömssen, Oct 02 2022
|
|
|
REFERENCES
|
Thomas Dawson, Échecs Féeriques, L'Échiquier, volume 2, issue 2, 1930; issue 3, 1931.
Donald E. Knuth, The Art of Computer Programming, Volume 4B, Combinatorial Algorithms, Part 2, Addison-Wesley, 2023. See exercise 7.2.2.1-172 and its solution.
|
|
|
LINKS
|
Sequence mentioned in the related Solution to problem #12, Missoury State Math Dept. Challenge Problem Archive, 2007/08.
|
|
|
FORMULA
|
a(n) = n^2/2 + O(n) (Beluhov 2023).
(End)
|
|
|
EXAMPLE
|
The eight non-center fields of a 3 X 3 chessboard can be visited cyclically in a unique manner up to selection of starting point and clockwise vs. counterclockwise direction; since the center field cannot be part of a (longer) cycle, we have a(3) = 8.
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
more,nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
