The knight’s tour problem is the mathematical problem of finding a knight’s tour.
Creating a program to find a knight’s tour is a common problem given to computer science students .
Backtracking is an algorithmic paradigm that tries different solutions until finds a solution that “works”.
Problems that are typically solved using the backtracking technique have the following property in common.
These problems can only be solved by trying every possible configuration and each configuration is tried only once.
A Naive solution for these problems is to try all configurations and output a configuration that follows given problem constraints.
Backtracking works incrementally and is an optimization over the Naive solution where all possible configurations are generated and tried.
For example, consider the following Knight’s Tour problem.
Question:::
Given a N*N board with the Knight placed on the first block of an empty board.
Moving according to the rules of chess knight must visit each square exactly once.
Print the order of each cell in which they are visited.
Input :
N = 8
Output:
0 59 38 33 30 17 8 63
37 34 31 60 9 62 29 16
58 1 36 39 32 27 18 7
35 48 41 26 61 10 15 28
42 57 2 49 40 23 6 19
47 50 45 54 25 20 11 14
56 43 52 3 22 13 24 5
51 46 55 44 53 4 21 12
This Knight's tour problem defines that if it is possible to travel all the possible blocks of chess from the starting position of the chessboard.
To be clear a Knight can move only in eight specific directions/blocks from its current location.
The "Knight's Tour" of the chessboard was first proposed (solved) in a ninth century Arabic manuscript by Abu Zakariya Yahya ben Ibrahim al-Hakim.
The author give two tours, one by Ali C. Mani, an otherwise unknown chess player, and the other by al-Adli ar-Rumi,
who flourished around 840 and is known to have written a book on Shatranj (the form of chess then popular).
A "closed tour" is one in which the square at the end of a Knight's Tour is a knight move away from the first square, as in the second example above.
The master of Shatranj as-Suli, who based his works on those of al-Adli (which he criticized), published the two closed tours given above on the right.
The first example shows perfect axial symmetry on the left half-board, the second is composed of two quasi-symmetrical half-board tours.
The first comprehensive mathematical analysis of the Knight's Tour was presented by the eighteenth century mathematician Leonhard Euler (1707–1783)
to the Academy of Sciences at Berlin in 1759. The Academy had proposed a prize of 4,000 Francs for the best memoir on the problem,
but it was never awarded, probably since Euler was at that time Director of Mathematics at the Berlin Academy and presumably ineligible.
Incidentally the number of possible knight's tours on an 8x8 board is surprisingly large — estimates range between 13 and 33 trillion. And much more on bigger boards. Here, for curiosity’s sake, is a Knight Tour on a 130x130 board.
If you want to learn a closed knight's tour by heart pick one of the following by Leonhard Euler.
Learning a closed tour had the important advantage of allowing you to start from any square on the board and complete the tour from there.
It is as easy as reciting the numbers from 1–64 starting from some random number and cycling to 1 after reaching 64.
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.
But Indians solved 600 years before Euler.
Comments
Post a Comment