
related topics 
{math, number, function} 
{album, band, music} 
{game, team, player} 
{@card@, make, design} 
{son, year, death} 
{black, white, people} 
{disease, patient, cell} 
{township, household, population} 
{church, century, christian} 
{language, word, form} 
{system, computer, user} 

The knight's tour is a mathematical problem involving a knight on a chessboard. The knight is placed on the empty board and, moving according to the rules of chess, must visit each square exactly once. A knight's tour is called a closed tour if the knight ends on a square attacking the square from which it began (so that it may tour the board again immediately with the same path). Otherwise the tour is open. The exact number of open tours is still unknown. Creating a program to solve the knight's tour is a common problem given to computer science students.^{[1]} Variations of the knight's tour problem involve chessboards of different sizes than the usual 8 × 8, as well as irregular (nonrectangular) boards.
Contents
Theory
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. Note however that, unlike the general Hamiltonian path problem, the knight's tour problem can be solved in linear time.^{[2]}
History
The earliest known references to the Knight's Tour problem date back to the 9th century CE. The pattern of a knight's tour on a halfboard has been presented in verse form (as a literary constraint) in the highly stylized Sanskrit poem Kavyalankara^{[3]} written by the 9th century Indian poet Rudrata, which discusses the art of poetry, especially with relation to theater (Natyashastra). As was often the practice in ornate Sanskrit poetry, the syllabic patterns of this poem elucidate a completely different motif, in this case an open knight's tour on a halfchessboard.
Full article ▸


related documents 
Diffeomorphism 
Isomorphism theorem 
Discriminant 
Algebraic topology 
Generalized Riemann hypothesis 
Monotonic function 
Tree (data structure) 
Differential topology 
Conjunctive normal form 
Axiom of regularity 
Mean value theorem 
Spectrum of a ring 
Product topology 
Cartesian product 
Theory of computation 
Laurent series 
Kolmogorov space 
De Morgan's laws 
Diophantine set 
Wellorder 
Least common multiple 
Lebesgue measure 
Goodstein's theorem 
Carmichael number 
CauchyRiemann equations 
Automata theory 
Group representation 
Golden ratio base 
Graftal 
Local ring 
