Longest cross-free jumper path

A closed path for n = 7 with length 24.

The longest open path on a standard chessboard at 35 jumps.

The longest cross-free knight path is a problem from the field of entertainment mathematics and a type of chess composition .

The aim is to move a knight on an empty chessboard in as long a series of jumps as possible, the marked course of which remains free of intersections. Originally conceived for the chessboard, the problem was extended to other square boards n × n , or formulated for any rectangular boards. One possible variant is to look for the longest possible closed tour in which the destination point is back on the starting point.

General

Exact solutions to the problem are only known with certainty for values n <10. A square board must be at least 3 × 3 in size, in this case two cross-free moves are possible. The sequence of numbers for the longest open paths for square boards ( OEIS sequence A003192 ) begins with

{\ displaystyle 2,5,10,17,24,35,47. \}

For small n ( n <9), the results can be verified relatively easily with a backtracking method. However, the runtime of the program grows exponentially, so that the entries from n = 9 can possibly be improved. The following table provides an overview of the longest known open jumper paths:

n	3	4th	5	6th	7th	8th	9	10	11	12	13	14th	15th
Longest path	2	5	10	17th	24	35	47	61	76	94	113	135	158

Some solutions can be systematically expanded step-by-step to ever larger boards and thus obtain a downward estimate for the minimum length of a path on boards of any size. In this way one finds that the minimum number of jumps (= visited fields-1) increases quadratically in relation to the existing fields . For provides a good approximation, ab the longest possible path is always at least long. ${\ displaystyle n ^ {2}}$ ${\ displaystyle 7 \ leq n \ leq 31}$ ${\ displaystyle n ^ {2} -7 \ cdot n + 24}$ ${\ displaystyle n> 31}$ ${\ displaystyle n ^ {2} -7 \ cdot n + 22}$

Generalizations

In addition to rectangular boards , the question can also be investigated for polyominos of any shape . Examining other chess pieces does not give any interesting results. If you generalize the common knight (1; 2), you get figures borrowed from fairy tale chess , such as the camel (1; 3), the zebra (2; 3) or the giraffe (1; 4). The investigation of the longest path is as complex for these figures as it is for the jumper.

One can abandon the condition that the knight is moving on a chessboard and instead only require that the next jump be of the same length and at certain angles to the previous jump. Instead of limiting the path to a square field, one looks for either the longest jumps within simple geometric figures or generally the longest series of jumps within a given radius. The last variant was the content of a programming competition by Al Zimmermann. The website enginemonitoring.net provides an overview of the solutions .

Recently, the investigation of cross-free jumper paths has also been proposed for a three-dimensional grid. A jumper who starts in the cell (0,0,0) can 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 approximately to (0,2,1) or (1,0,2). A cube is defined as the limiting field in this case . ${\ displaystyle n \ times n \ times n}$

literature

LD Yarbrough: Uncrossed Knight's Tours . In: Journal of Recreational Mathematics . tape 1 , no. 3 , 1969, p. 140-142 .

Web links

Non-Intersecting Paths , by George Jelliss.

Individual evidence

[1] ttp://www.mathpuzzle.com/17Dec06.html

[2] ttp://www.fischer-mathe.de/uncrossedleapers.html

[3] ttp://www2.stetson.edu/~efriedma/mathmagic/0503.html

[4] ttp://www.azspcs.net/

[5] ttp://www.enginemonitoring.net/azpc/zz/azpczzresults.htm

[6] ttp://arxiv.org/abs/0803.4259