History
The earliest known reference to the Knight's Tour problem dates back to the 9th century AD. In Rudraṭa's Kavyalankara (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 ("citra-alaṅkāra") called the "turagapadabandha" 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:
से ना ली ली ली ना ना ना ली
ली ना ना ना ना ली ली ली ली
न ली ना ली ली ले ना ली ना
ली ली ली ना ना ना ना ना ली
se nā lī lī lī nā nā lī
lī nā nā nā nā lī lī lī
na lī nā lī le nā lī nā
lī lī lī nā nā nā nā lī
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 mathematicians to investigate the knight's tour was Leonhard Euler. The first procedure for completing the Knight's Tour was Warnsdorff's rule, first described in 1823 by H. C. von Warnsdorff.
In the 20th century, the Oulipo group of writers used it among many others. The most notable example is the 10 × 10 Knight's Tour which sets the order of the chapters in Georges Perec's novel Life: A User's Manual. The sixth game of the 2010 World Chess Championship between Viswanathan Anand and Veselin Topalov saw Anand making 13 consecutive knight moves (albeit using both knights) -– online commentors jested that Anand was trying to solve the Knight's Tour problem during the game.
Read more about this topic: Knight's Tour
Famous quotes containing the word history:
“He wrote in prison, not a History of the World, like Raleigh, but an American book which I think will live longer than that. I do not know of such words, uttered under such circumstances, and so copiously withal, in Roman or English or any history.”
—Henry David Thoreau (1817–1862)
“The custard is setting; meanwhile
I not only have my own history to worry about
But am forced to fret over insufficient details related to large
Unfinished concepts that can never bring themselves to the point
Of being, with or without my help, if any were forthcoming.”
—John Ashbery (b. 1927)
“We have need of history in its entirety, not to fall back into it, but to see if we can escape from it.”
—José Ortega Y Gasset (1883–1955)