Longest uncrossed knight's path
 |
This article is an orphan, as few or no other articles link to it. Please introduce links to this page from related articles; suggestions may be available. (November 2010) |
The longest uncrossed (or nonintersecting) knight's path is a mathematical problem involving a knight on the standard 8×8 chessboard or, more generally, on a square n×n board. The problem is to find the longest path the knight can take on the given board, such that the path does not intersect itself. A further distinction can be made between a closed path, which ends on the same field as where it begins, and an open path, which ends on a different field from where it begins.
Contents |
[edit] Known solutions
The longest open paths are known only for n ≤ 9. Their lengths for n = 1, 2, …, 9 are:
The longest closed paths are known only for n ≤ 10. Their lengths for n = 1, 2, …, 10 are:
 |
 |
| A longest closed path for n = 7 of length 24. |
A longest open path for n = 8 of length 35. |
[edit] Generalizations
The problem can be further generalized to rectangular n×m boards, or even to boards in the shape of any polyomino. Other standard chess pieces than the knight are less interesting, but fairy chess pieces like camel, giraffe and zebra lead to problems of comparable complexity.
[edit] See also
- A knight's tour is a self-intersecting knight's path visiting all fields of the board.
- TwixT, a board game based on uncrossed knight's paths.
[edit] References
- L. D. Yarbrough (1969). "Uncrossed knight's tours". Journal of Recreational Mathematics 1 (3): 140–142.
- George Jelliss, Non-Intersecting Paths
- Non-crossing knight tours
