Longest uncrossed knight's path
From Wikipedia, the free encyclopedia
The longest uncrossed (or nonintersecting) knight's path is a mathematical problem involving a knight on a 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.
 |
 |
| A closed path for n = 7 of length 24. |
An open path for n = 8 of length 35. |
Solutions are known only up to n = 8. The length of the longest path, whether open or closed (OEIS sequence A003192), for n = 3…8 is:
- 2, 5, 10, 17, 24, 35.
These results can readily be reproduced by a simple backtracking computer program. However, the running time for such a program becomes prohibitively long for n ≥ 9.
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, Uncrossed knight's tours, Journal of Recreational Mathematics 1 (1969), no. 3, pp. 140-142.
[edit] External links
- Non-Intersecting Paths by Leapers, by George Jelliss.
