Jumper problem

Graphic solution

Animated solution

The knight problem is a combinatorial problem that consists in finding a route for a knight on an empty chessboard , on which he visits each square exactly once. One of several possible generalizations is to use two-dimensional boards of any size n × m or even n-dimensional boards. A knight's tour is closed when the knight's end square is one knight move away from the start square. Otherwise the way is called open (as in the diagram).

The jumper problem is also known as the Rösselsprung . The latter expression, however, more often designates the knight jump puzzle , in which letters or syllables are entered in the fields of the board that, in the correct order, result in a solution sentence or a solution word. It should also be noted that the knight problem is something completely different from the women’s problem , but the two terms have historically become established.

history

The problem is found in a Sanskrit poem by Rudrata from the 9th century. In the west it is mentioned in a 14th century codex in the Paris National Library. Abraham de Moivre and Pierre Rémond de Montmort gave solutions at the beginning of the 18th century. The Swiss mathematician Leonhard Euler treated the Springer problem mathematically in 1759. Since then, many other mathematicians (including Legendre and Vandermonde ) and countless hobbyists have dealt with the matter.

In the 1950s, the pharmacist Gerard D'Hooghe developed a machine that demonstrates a knight round trip from any given starting square. He laid the foundations for this machine in 1962 in the book Les Secrets du Cavalier, Le Problème d'Euler . His so-called t'Zeepaard was shown to the public in 1960 during the Chess Olympiad in Leipzig.

Mathematical basics

Representation of the Springer problem for as an instance of the Hamilton circle problem . ${\displaystyle n=8}$

The jumper problem is a special case of the Hamilton path problem, a well-known problem in graph theory , in which all nodes in a graph have to be visited exactly once. If the first square can be reached from the last square in the sequence, a Hamilton circle has been found. The Hamilton path problem is NP-complete , so an efficient solution algorithm is not known and, as is generally assumed, does not exist either. In contrast, efficient algorithms exist for the jumper problem, which are presented below.

Solution method

Examples of open jumper tours (G. Mann, 120 new Rösselsprünge, 1859)

Examples of closed jumper tours (G. Mann, 120 new Rösselsprünge, 1859)

Backtracking process

A first approach for an algorithm is to use a simple backtracking method. Here you choose an arbitrary route and, when you reach a dead end, take the last train back and choose an alternative train instead. This algorithm will definitely find a solution if one exists, but it is very slow. On larger boards, a person can find a solution by skillful trial and error in a much shorter time than the simple backtracking algorithm reaches its goal.

Warning rule

In 1823 HC von Warnsdorf proposed a heuristic rule that greatly simplifies finding a solution. According to the warning rule, the knight always moves to the space from which he has the fewest free spaces (i.e. not yet visited) spaces available for his next move. This rule is immediately obvious; it prevents, for example, one of the two squares that the knight can reach from a corner from being visited early, so that he cannot later escape from the corner. The warning village rule does not give any instructions on what to do if there are several spaces, of which there are few spaces that can be reached in the next move.

Even if a solution exists, the Warnsdorelle rule cannot guarantee that it will be found, and indeed the jumper for large boards is increasingly reaching a dead end. Even on a chessboard (n = 8) the algorithm can fail if one chooses the wrong one from several possible alternatives, but this is very unlikely.

Starting here, improved heuristics have been developed, including an algorithm from Squirrel that specifies rather complicated decision rules for the case of several alternatives that are equivalent according to the Warnsdor rule, but apparently finds a solution for all boards larger than n = 75 in linear time (the formal proof of correctness is so far only performed for n = 7 mod 8). It is possible to combine the warning rule and backtracking procedure, but with large boards this leads to exponentially increasing runtime.

divide and conquer

As part of a work for Jugend forscht , a group developed various algorithms with which a solution can be found for fields of any size with a runtime complexity of . In their paper published in 1994 they presented a method in which they divide any chessboard into smaller sub-rectangles with sizes from 5 × 5 to 9 × 9, for which special solutions exist. ${\displaystyle n\times n}$ ${\displaystyle {\mathcal {O}}(n^{2})}$

Schwenk's theorem

For every board with , there is a closed knight tour, unless one of the following three cases is present: ${\displaystyle m\times n}$ ${\displaystyle m\leq n}$

1. and are both odd ${\displaystyle m}$ ${\displaystyle n}$

2. ${\displaystyle m=1,2,4}$

3rd and ${\displaystyle m=3}$ ${\displaystyle n=4,6,8}$

Proof can be derived from the algorithms presented in the above-mentioned youth research paper. Under the conditions mentioned, any start and finish fields can be selected, including those where the target field can be jumped back to the start field and the knight's tour can thus be closed.

1st case

Imagine that the fields are colored black and white like a checkerboard. The start and end fields must have different colors for a closed path. Since the knight changes his field color after each move, he has to cross as many white as black fields on his way, i.e. an even number of fields.

2nd case

If or , the knight obviously cannot reach every square (unless in the trivial case of the 1 × 1 board). ${\displaystyle m=1}$ ${\displaystyle m=2}$

If , let the number of white fields, the number of black fields, the number of marginal fields on the two opposite longer board edges and the number of all fields that do not belong, that is . has the same number of elements as . ${\displaystyle m=4}$ ${\displaystyle A_{1}}$ ${\displaystyle B_{1}}$ ${\displaystyle A_{2}}$ ${\displaystyle B_{2}}$ ${\displaystyle A_{2}}$ ${\displaystyle B_{2}=\!^{\complement }A_{2}}$ ${\displaystyle B_{2}}$ ${\displaystyle A_{2}}$

In each move the knight changes the field color and the field type between and . The latter follows from the following consideration: The knight can only move from an edge square (crowd ) to a square in the middle (crowd ). If the knight were to make a move within (which is possible), he would visit more spaces from than from , which cannot lead to a solution because the two sets comprise the same number of spaces. ${\displaystyle A_{2}}$ ${\displaystyle B_{2}}$ ${\displaystyle A_{2}}$ ${\displaystyle B_{2}}$ ${\displaystyle B_{2}}$ ${\displaystyle B_{2}}$ ${\displaystyle A_{2}}$

Without limitation, the starting field is an element of and . If necessary, swap the roles of and and the roles of and . ${\displaystyle A_{1}}$ ${\displaystyle A_{2}}$ ${\displaystyle A_{1}}$ ${\displaystyle B_{1}}$ ${\displaystyle A_{2}}$ ${\displaystyle B_{2}}$

In the next move the field color element is off and , then off again and and so on. ${\displaystyle B_{1}}$ ${\displaystyle B_{2}}$ ${\displaystyle A_{1}}$ ${\displaystyle A_{2}}$

This shows on the one hand that the same elements as has and on the other hand that the same elements as has, thus and , which is obviously not true. ${\displaystyle A_{1}}$ ${\displaystyle A_{2}}$ ${\displaystyle B_{1}}$ ${\displaystyle B_{2}}$ ${\displaystyle A_{1}=A_{2}}$ ${\displaystyle B_{1}=B_{2}}$

3. Case

You can't find a closed path on the 3 × 4, 3 × 6 and 3 × 8 boards.

Paths for board sizes 3 × 10, 3 × 12, 3 × 14 etc. are possible, whereby the solution pattern is repeated.

Number of closed tours

On a 6 × 6 board there are 9862 and on an 8 × 8 board 13,267,364,410,532 undirected closed tours. There is no closed tour on boards with , and for boards with and just the number is still open. ${\displaystyle n\times n}$ ${\displaystyle n\leq 4}$ ${\displaystyle n\times n}$ ${\displaystyle n\geq 10}$ ${\displaystyle n}$

For reasons of parity, there is no closed tour on boards with an uneven number of fields (see first case of Schwenk's theorem).

See also

• Longest cross-free jumper path

Individual evidence

1. ^ Bill Wall Earliest chess books and references ( Memento of January 21, 2012 in the Internet Archive )
2. ^ Wilhelm Ahrens Mathematische Unterhaltungen und Spiele , Teubner 1901, p. 165. He quotes A. von der Linde History and Literature of the Chess Game , Berlin 1874, Volume 2, p. 101. See also WW Rouse Ball Mathematical recreations and essays , 4. Edition. Macmillan 1905, p. 158ff, online with Gutenberg
3. ↑ Axel Conrad, Tanja Hindrichs, Hussein Morsy, Ingo Wegener : Solution of the Knight's Hamiltonian Path Problem on Chessboards. Discrete Applied Mathematics, Volume 50, Issue 2, May 1994, Pages 125-134.
4. ↑ A short journey through the world of the jumper
5. ^ Ingo Wegener Branching Programs and Binary Decision Diagrams , Society for Industrial & Applied Mathematics, Philadelphia, 2000.

literature

• Douglas Squirrel, Paul Cull: A Warnsdorff-Rule Algorithm for Knight's Tours on Square Chessboards . Oregon State REU Program, 1996. (Description of an extension of the Warnsdor rule that solves the jumper problem in linear time)

Web links

Commons : Knight's Tours  - collection of images, videos and audio files

• Detailed page with an optimal solution
• Page on the warning rule, including applet to try out ( Memento from August 2, 2012 in the Internet Archive )