Knight's tour
Channel: 宇宙のすべての知識 プリンシピア
Date: 08/03/2019

Knight's tour, by Wikipedia https://en.wikipedia.org/wiki?curid=38501 / CC BY SA 3.0

#Graph_algorithms
#Mathematical_chess_problems
#Chess_problems
#Hamiltonian_paths_and_cycles
#Mathematical_problems
Knight's tour

A knight's tour is a sequence of moves of a knight on a chessboard such that the knight visits every square only once. If the knight ends on a square that is one knight's move from the beginning square (so that it could tour the board again immediately, following the same path), the tour is "closed", otherwise it is "open".

The knight's tour problem is the mathematical problem of finding a knight's tour. Creating a program to find a knight's tour is a common problem given to computer science students. Variations of the knight's tour problem involve chessboards of different sizes than the usual , as well as irregular (non-rectangular) boards.

The knight's tour problem is an instance of the more general Hamiltonian path problem in graph theory. The problem of finding a closed knight's tour is similarly an instance of the Hamiltonian cycle problem. Unlike the general Hamiltonian path problem, the knight's tour problem can be solved in linear time.
The earliest known reference to the knight's tour problem dates back to the 9th century AD. In Rudraṭa's (5.15), a Sanskrit work on Poetics, the pattern of a knight's tour on a half-board has been presented as an elaborate poetic figure () called the or 'arrangement in the steps of a horse'. The same verse in four lines of eight syllables each can be read from left to right or by following the path of the knight on tour. Since the Indic writing systems used for Sanskrit are syllabic, each syllable can be thought of as representing a square on a chess board. Rudrata's example is as follows:

transliterated:

For example, the first line can be read from left to right or by moving from the first square to second line, third syllable (2.3) and then to 1.5 to 2.7 to 4.8 to 3.6 to 4.4 to 3.2.

One of the first mathem...