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:
“I believe that history has shape, order, and meaning; that exceptional men, as much as economic forces, produce change; and that passé abstractions like beauty, nobility, and greatness have a shifting but continuing validity.”
—Camille Paglia (b. 1947)
“No one can understand Paris and its history who does not understand that its fierceness is the balance and justification of its frivolity. It is called a city of pleasure; but it may also very specially be called a city of pain. The crown of roses is also a crown of thorns. Its people are too prone to hurt others, but quite ready also to hurt themselves. They are martyrs for religion, they are martyrs for irreligion; they are even martyrs for immorality.”
—Gilbert Keith Chesterton (1874–1936)
“Every generation rewrites the past. In easy times history is more or less of an ornamental art, but in times of danger we are driven to the written record by a pressing need to find answers to the riddles of today.... In times of change and danger when there is a quicksand of fear under men’s reasoning, a sense of continuity with generations gone before can stretch like a lifeline across the scary present and get us past that idiot delusion of the exceptional Now that blocks good thinking.”
—John Dos Passos (1896–1970)