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.
The longest open paths on an nÃÂn board 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:
The problem can be further generalized to rectangular mÃÂn boards, or even to boards in the shape of any polyomino. A restricted form of the problem for mÃÂn boards, where nâ¤8 and m might be very large, was given at 2018 ICPC World Finals. It may be solved by dint of dynamic programming, helped by the insight that the solution should exhibit a cyclic behaviour.
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.