Longest uncrossed knight's path
Encyclopedia
The longest uncrossed 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 closed paths are known only for n ≤ 10. Their lengths for n = 1, 2, …, 10 are:
. Other standard chess piece
s than the knight are less interesting, but fairy chess piece
s like camel, giraffe and zebra lead to problems of comparable complexity.
Knight (chess)
The knight is a piece in the game of chess, representing a knight . It is normally represented by a horse's head and neck. Each player starts with two knights, which begin on the row closest to the player, one square from the corner...
on the standard 8×8 chessboard
Chessboard
A chessboard is the type of checkerboard used in the board game chess, and consists of 64 squares arranged in two alternating colors...
or, more generally, on a square n×n board. The problem is to find the longest path
Path (graph theory)
In graph theory, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. A path may be infinite, but a finite path always has a first vertex, called its start vertex, and a last vertex, called its end vertex. Both of them...
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 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
| A longest closed path for n = 7 of length 24. | An longest open path for n = 8 of length 35. |
Generalizations
The problem can be further generalized to rectangular n×m boards, or even to boards in the shape of any polyominoPolyomino
A polyomino is a plane geometric figure formed by joining one or more equal squares edge to edge. It is a polyform whose cells are squares. It may be regarded as a finite subset of the regular square tiling with a connected interior....
. Other standard chess piece
Chess piece
Chess pieces or chessmen are the pieces deployed on a chessboard to play the game of chess. The pieces vary in abilities, giving them different values in the game...
s than the knight are less interesting, but fairy chess piece
Fairy chess piece
A fairy chess piece or unorthodox chess piece is a piece analogous to a chess piece. It is not used in conventional chess, but is used in certain chess variants and some chess problems...
s like camel, giraffe and zebra lead to problems of comparable complexity.
See also
- A knight's tourKnight's tourThe 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. A knight's tour is called a closed tour if the knight ends on a square attacking the square from...
is a self-intersecting knight's path visiting all fields of the board. - TwixTTwixTTwixT is a two-player abstract strategy game invented by Alex Randolph. It is a member of the connection game family, along with games such as Hex, Havannah, Y, PÜNCT and *Star...
, a board game based on uncrossed knight's paths.