Longest uncrossed knight's path
{{Short description|Mathematical problem set on a chessboard}}
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.
Known solutions
The longest open paths on an n×n board are known only for n ≤ 9. Their lengths for n = 1, 2, …, 9 are:
:0, 0, 2, 5, 10, 17, 24, 35, 47 {{OEIS|A003192}}
The longest closed paths are known only for n ≤ 10. Their lengths for n = 1, 2, …, 10 are:
: 0, 0, 0, 4, 8, 12, 24, 32, 42, 54 {{OEIS|A157416}}
| style="margin:auto" |
| valign="bottom"
| style="padding: 0 1em" | 210px | style="padding: 0 1em" | 240px |
| align="center" | The longest closed path for n = 7 of length 24. | align="center" | The longest open path for n = 8 |
Generalizations
The problem can be further generalized to rectangular n×m boards, or even to boards in the shape of any polyomino. The problem for n×m boards, where n doesn't exceed 8 and m might be very large, was given at 2018 ICPC World Finals. The solution used dynamic programming and uses the fact that the solution should exhibit a cyclic behavior.
Other standard chess pieces than the knight are less interesting, but fairy chess pieces like the camel ((3,1)-leaper), giraffe ((4,1)-leaper) and zebra ((3,2)-leaper) lead to problems of comparable complexity.
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.
References
- {{cite journal |author=L. D. Yarbrough |title=Uncrossed knight's tours |journal=Journal of Recreational Mathematics |volume=1 |year=1968 |issue=3 |pages=140–142}}
- George Jelliss, [http://www.mayhematics.com/t/2n.htm Non-Intersecting Paths]
- [http://euler.free.fr/knight/index.htm Non-crossing knight tours]
- [https://www.csc.kth.se/~austrin/icpc/finals2018solutions.pdf 2018 ICPC World Finals solutions (Problem J)]
External links
- [http://ukt.alex-black.ru Uncrossed knight's tours]