Knight's tour

The Springer problem is a combinatorial problem which is to find for a knight on a chessboard empty a route on which of these each field visited exactly once. One of several possible generalizations is to use boards of size n × m or n-dimensional boards. A knight's tour is called closed when the end panel of the knight is a knight move away from the starting field. Otherwise, is the way to open ( as in the diagram).

The Springer problem is also known under the name Rösselsprung. However, the latter term more commonly referred to the knight's tour puzzles, are registered in the letters or syllables in the fields of the board that visited in the correct order by a knight's tour, give a set of solutions or a solution word. It should also be noted that the Springer problem is something completely different than the women's problem, but the two terms have historically naturalized.

• 4.1 Case 1
• 4.2 Case 2
• 4.3 Case 3

History

The problem is found in a Sanskrit poem by Rudrata from the 9th century. In the West, it is mentioned in a codex of the 14th century, the National Library in Paris. Abraham de Moivre and Pierre Remond de Mont Mort gave the early 18th century solutions. The Swiss mathematician Leonhard Euler treated the Springer 1759 problem mathematically. Since then, many other mathematicians ( among them Legendre and Vandermonde ) and countless hobby tinkerers studied the matter.

In the 1950s, the pharmacist Gerard D' Hooghe developed a machine that demonstrated a Springer roundtrip from an arbitrarily specified output field. The bases for these machines he introduced in 1962 in the book Les Secrets du Cavalier, Le Problème d' Euler dar. His so-called t'Zeepaard 1960 shown publicly during the Chess Olympiad in Leipzig.

Mathematical Foundations

The Springer problem is a special case of the Hamiltonian path problem, a well-known problem in graph theory in which all the nodes in a graph must be visited exactly once. If the first field can be reached by the last field of the sequence of moves, one has a Hamiltonian cycle found. The Hamilton Path problem is NP-complete, an efficient solution algorithm is not so well known and exist, as is generally believed, either. On the other hand, there are efficient algorithms that are presented below for the Springer problem.

Solution method

Backtracking method

A first approach for an algorithm is to apply a simple backtracking process. Here one chooses an arbitrary route and decreases when one has arrived at an impasse, the respective last train back and chooses instead of an alternative train. This algorithm is definitely a solution, if one exists, but it is very slow. On larger boards can a man be found by skillful Try within much less time a solution as that of the simple backtracking algorithm comes to the destination.

Warnsdorff rule

In 1823 HC Warnsdorff proposed a heuristic rule, which greatly simplifies finding a solution. After Warnsdorff rule of Springer always takes to the field, from which he for his next train at least free ( ie unvisited ) fields at its disposal. This rule is immediately obvious; it prevents, for example, that one of the two fields that the jumper can reach from a corner, is visited early so that he could no longer escape from the corner later. The Warnsdorff rule is no instruction, what to do if there are multiple fields, of which there are the same few fields achievable in the next train.

The Warnsdorff rule, even if a solution exists, does not guarantee that it will be found, and in fact gets the Springer for large boards increasingly often in a dead end. Even on a chessboard ( n = 8) may fail if one of several possible alternatives selects the wrong, this is very unlikely the algorithm.

Here quoting improved heuristics have been developed, including one algorithm of Squirrel, indicating rather complicated decision rules for the case of several after Warnsdorff usually equivalent alternatives, however, appear for all boards larger than n = 75 in linear time a solution found ( the formal correctness proof is been performed only for n = 7 mod 8 ). The combination of Warnsdorff rule and backtracking method is possible, but in turn leads to an exponential for large boards anwachsender runtime.

Divide and rule

As part of a work for Young Scientists, a group developed several algorithms that for arbitrarily large fields a solution in a run- time complexity of can be found. In her essay published in 1994, they introduced a method in which they divide any chess boards into smaller rectangles with sizes ranging from 5x5 to 9x9, for which there are special solutions.

Cal pivot theorem

For each board, with, there is a closed knight's tour, unless one of the following three cases occurs:

A proof can be derived based on the algorithms presented in the aforementioned youth research work. Under the conditions mentioned any start and finish fields can be selected, including those in which jumped from the target field back to the start field and thus the knight's tour can be closed.

Case 1

Imagine, the fields are colored checkerboard pattern in black and white. Start and end field must have different colors in a closed path. Since the Springer after each train its field color changes, he must on his way just as much white as black boxes exceed, ie an even number of fields.

Case 2

Is or so of Springer obviously can not reach each field ( except in the trivial case of the 1x1 board ).

If, as was the amount of white fields, the amount of the black boxes, the amount of fringing fields at the two opposite long board edges and the set of all fields that are not to be included, ie. has the same number of elements as.

In each train of Springer change the field color and the type of field between and. The latter follows from the following consideration: from a marginal field (quantity ), the jumper only on a field in the middle reach ( quantity). If the jumper is now a train within run (which is possible ), he would be more fields of visiting of which can lead to no solution, because the two amounts comprise the same number of fields.

Without limiting the initial field is an item then. Swap this necessary, and the roles of and the roles of and.

The next train is the Color box item and then again and so on.

This shows, firstly, that the same elements as has, and secondly that the same elements as has, therefore, and, which obviously is not true.

Case 3

On the boards 3 × 4, 3 × 6 and 3 × 8 can not find a closed path.

Ways for board sizes 3 × 10, 3 × 12, 3 × 14, etc. are possible, with the repeated solution patterns.

Number of closed tours

On a 6x6 board, there are 9862 and on a 8x8 board 13,267,364,410,532 undirected closed tours. On boards with there is no closed tour, and for boards with and upright is the number still open.

On boards with an odd number of fields, there are parity reasons no closed tour (see the first case of pan cal theorem).