# 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.