View source for 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 (chess)|knight]] on the standard 8×8 [[chessboard]] or, more generally, on a square ''n''×''n'' board. The problem is to find the longest [[path (graph theory)|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" | [[File:UncrossedKnightsPath7x7.svg|210px]]
| style="padding: 0 1em" | [[File:UncrossedKnightsPath8x8.svg|240px]]
|-
| align="center" | The longest closed path for ''n'' = 7<br>of length 24.
| align="center" | The longest open path for ''n'' = 8<br>of length 35.
|}
== 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 [[chess piece|standard chess piece]]s than the knight are less interesting, but [[fairy chess piece]]s like the [[camel (chess)|camel]] ((3,1)-leaper), [[giraffe (chess)|giraffe]] ((4,1)-leaper) and [[zebra (chess)|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]
[[Category:Mathematical chess problems]]
[[Category:Computational problems in graph theory]]