Longest uncrossed knight's path

The longest crossing-free path Springer is a problem from the field of recreational mathematics and a kind of chess composition.

The aim is to move a knight on an empty chessboard in a possible long series of jumps, which marked polyline is crossing-free. Originally conceived for the chessboard, the problem in another square n × n boards was extended, or formulated for arbitrary rectangular boards. One possible variant is to look for a possible long closed tour, where the target point is again on the starting point.

General

Exact solutions of the problem are known only for certain values ​​of n <9. A square board has 3 × 3 have, in this case two crossing-free moves are possible at least the size. The number sequence of the longest open paths for square boards ( OEIS sequence A003192 ) begins with

The results can be relatively easily detected with a backtracking process for small n ( n < 9). However, the duration of the program is growing exponentially, so that the entries from n = 9 may still be improved. An overview of the oldest known open Springer paths yields the following table:

You can extend some solutions in a systematic way to ever- boards, giving it an estimate downward for the minimum length of a path to arbitrarily large boards. One finds in this way that the minimum number of jumps ( = visited fields -1) in relation to the existing fields also grows quadratically. For provides a good approximation, from the longest possible path is always at least long.

Generalizations

The question can be examined in addition to square boards for arbitrarily shaped polyominoes. The investigation of other chess pieces does not provide interesting results. It generalizes the ordinary Springer (1, 2), we obtain the fairy chess borrowed figures, such as the camel (1, 3), the zebra (2, 3) or the giraffe (1, 4). The investigation of the longest path is just as complex as the Springer for these figures.

You can give up the condition that the jumper moves on a chessboard, and instead only require that a next hop has a unit length and occurs in certain angles to the previous jump. Instead of limiting the path on a square box, looking either longest jumps within simple geometric figures or in general the longest jump series within a given radius. The last variant was the subject of a programming competition by Al Zimmermann. An overview of the solutions, the site enginemonitoring.net.

Recently, the study has been proposed by crossing-free Springer paths for a three-dimensional lattice. A jumper, which starts in the cell ( 0,0,0) may then not only in the XY plane according to ( 1,2,0 ) or ( 2,1,0 ), but also in the xz - and yz jump level after about ( 0,2,1 ) or ( 1,0,2 ). As a bounding box is defined in this case a cube.