- Longest uncrossed knight's path
The

**longest uncrossed**(or**nonintersecting**)**knight's path**is a mathematical problem involving a knight on a standard 8 × 8chessboard 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 ), 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, butfairy chess piece s like camel, giraffe and zebra lead to problems of comparable complexity.**ee 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*** L. D. Yarbrough, Uncrossed knight's tours, "Journal of Recreational Mathematics" 1 (1969), no. 3, pp. 140-142.

**External links*** [

*http://www.ktn.freeuk.com/2b.htm Non-Intersecting Paths by Leapers*] , by George Jelliss.

*Wikimedia Foundation.
2010.*

### Look at other dictionaries:

**Knight's tour**— The Knight s Tour is a mathematical problem involving a knight on a chessboard. The knight is placed on the empty board and, moving according to the rules of chess, must visit each square exactly once. olutionsThere are a great many solutions to… … Wikipedia**List of mathematics articles (L)**— NOTOC L L (complexity) L BFGS L² cohomology L function L game L notation L system L theory L Analyse des Infiniment Petits pour l Intelligence des Lignes Courbes L Hôpital s rule L(R) La Géométrie Labeled graph Labelled enumeration theorem Lack… … Wikipedia