The longest uncrossed (or nonintersecting) knight's path is a mathematical problem involving a
knight on the standard 8×8
chessboard
A chessboard is a used to play chess. It consists of 64 squares, 8 rows by 8 columns, on which the chess pieces are placed. It is square in shape and uses two colours of squares, one light and one dark, in a chequered pattern. During play, the bo ...
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
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
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
A camel (from: la, camelus and grc-gre, κάμηλος (''kamēlos'') from Hebrew or Phoenician: גָמָל ''gāmāl''.) is an even-toed ungulate in the genus ''Camelus'' that bears distinctive fatty deposits known as "humps" on its back. C ...
((3,1)-leaper),
giraffe
The giraffe is a large African hoofed mammal belonging to the genus ''Giraffa''. It is the tallest living terrestrial animal and the largest ruminant on Earth. Traditionally, giraffes were thought to be one species, ''Giraffa camelopardalis ...
((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
Non-Intersecting Paths2018 ICPC World Finals solutions (Problem J)
External links
Uncrossed knight's tours
Mathematical chess problems
Computational problems in graph theory