Knight's tour

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 (non-rectangular) 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 half-board 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 half-chessboard.

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
Well-order
Least common multiple
Lebesgue measure
Goodstein's theorem
Carmichael number
Cauchy-Riemann equations
Automata theory
Group representation
Golden ratio base
Graftal
Local ring