FACTOID # 26: Delaware is the latchkey kid capital of America, with 71.8% of households having both parents in the labor force.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Knight's tour
An open knight's tour of a chessboard
An open knight's tour of a chessboard
The Knight's tour as solved by The Turk, a chess-playing machine hoax. This particular solution is closed (circular), and can be completed from any point on the board.
The Knight's tour as solved by The Turk, a chess-playing machine hoax. This particular solution is closed (circular), and can be completed from any point on the board.
An animation of the Knight's Tour.
An animation of the Knight's Tour.

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. Image File history File links Knight's_tour. ... Image File history File links Knight's_tour. ... Image File history File links No higher resolution available. ... Image File history File links No higher resolution available. ... An engraving of the Turk from Karl Gottlieb von Windischs 1784 book Inanimate Reason The Turk was a famous hoax that purported to be a chess-playing machine. ... Image File history File links No higher resolution available. ... Image File history File links No higher resolution available. ... The knight moves in an L shape. ... Chessboard Chessboard with Staunton chess pieces A chessboard is often painted or engraved on a chess table. ... Chess is a recreational and competitive game for two players. ...


There are a great many solutions to the problem, of which exactly 26,534,728,821,064 have the knight finishing on a square from which it attacks the starting square. [1] Such a tour is described as directed and closed. The number of undirected closed tours is half this number, since every tour can be traced in reverse. Otherwise the tour is open (as in the first diagram).


Many variations on this topic have been studied by mathematicians, including Euler, over the centuries using: Leonhard Euler, considered one of the greatest mathematicians of all time A mathematician is a person whose primary area of study and research is the field of mathematics. ... Leonhard Paul Euler (pronounced Oiler; IPA ) (April 15, 1707 – September 18 [O.S. September 7] 1783) was a pioneering Swiss mathematician and physicist, who spent most of his life in Russia and Germany. ...

  • differently sized boards
  • two-player games based on this idea
  • problems using slight variations on the way the knight moves.

The knight's tour problem is an instance of the more general Hamiltonian path problem in graph theory, which is NP-complete. The problem of getting 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] In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path or a Hamiltonian cycle exists in a given graph (whether directed or undirected). ... A pictorial representation of a graph In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. ... In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use... In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem is the problem of determinining whether a Hamiltonian path or a Hamiltonian cycle exists in a given graph. ... In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path or a Hamiltonian cycle exists in a given graph (whether directed or undirected). ... In computational complexity, an algorithm is said to take linear time, or O(n) time, if the time it requires is proportional to the size of the input, which is usually denoted n. ...


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 Kashmiri 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. Constrained writing is a literary technique in which the writer is bound by some condition that forbids certain things or imposes a pattern. ... The Sanskrit language ( , for short ) is a classical language of India, a liturgical language of Hinduism, Buddhism, Sikhism, and Jainism, and one of the 23 official languages of India. ... As a means of recording the passage of time the 9th century was the century that lasted from 801 to 900. ... Kashmir (or Cashmere) may refer to: Kashmir region, the northwestern region of the Indian subcontinent India, Kashmir conflict, the territorial dispute between India, Pakistan, and the China over the Kashmir region. ... Natya Shastra is the classic Indian text of theater, acting, dance, music, and gesture. ...


The first algorithm for completing the Knight's Tour was Warnsdorff's algorithm, first described in 1823 by H. C. 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. (19th century - 20th century - 21st century - more centuries) Decades: 1900s 1910s 1920s 1930s 1940s 1950s 1960s 1970s 1980s 1990s As a means of recording the passage of time, the 20th century was that century which lasted from 1901–2000 in the sense of the Gregorian calendar (1900–1999... Oulipo stands for Ouvroir de littérature potentielle, which translates roughly as workshop of potential literature. It is a loose gathering of French-speaking writers and mathematicians, and seeks to create works using constrained writing techniques. ... Image of artist Georges Perec (March 7, 1936 - March 3, 1982) was a 20th century French novelist, filmmaker and essayist, a member of the Oulipo group and considered by many to be one of the most important post-WWII authors. ...

Contents

Schwenk's Theorem

For any m × n board with m less than or equal to n, a closed knight's tour is always possible unless one or more of these three conditions are true:

  1. m and n are both odd
  2. m = 1, 2, or 4; m and n are not both 1
  3. m = 3 and n = 4, 6, or 8

Condition 1

It is not hard to show that when condition 1 is true a closed knight's tour is impossible.


Imagine a chessboard colored black and white in the manner that we are all familiar with (alternating). Whenever a knight moves it lands on the opposite color. If it is on white, it moves to black. If it is on black, it moves to white.


Since m and n are both odd, the number of white squares and black squares are different. For example, in a 5×5 checkerboard there are 13 of one color and 12 of the other.


For a knight to have a closed tour it must visit the same number of white squares and black squares. But we have just seen that odd × odd boards have a different number of white squares and black squares, therefore closed tours do not exist. Open tours may still exist.


Condition 2

Condition 2 states that when the shorter side is length 1, 2, or 4, no closed tour is possible.


It is easy to see why when m = 1 or 2 that no knight's tour is possible: the knight would not be able to reach every square (with the exception of the trivial case 1x1).


It can be shown that a 4 × n board cannot have a closed tour.


Start by assuming that a 4 × n board has a closed knight's tour. Let us construct 2 sets of squares, A1 and B1, A1 containing one half of the squares on the board and B1 containing the other half of the squares on the board. If we color this 4 × n board with a checkerboard pattern, we can define A1 as the set of white squares and B1 as the set of black squares. As previously established, the knight must alternate between white and black (A1 and B1).

The knight must alternate between green and red.
The knight must alternate between green and red.

Consider the figure on the right. Define A2 as the set of green squares and B2 as the set of red squares in the figure. There are an equal number of red squares as green squares. Note that from a square in A2 the knight must next jump to a square in B2. And since the knight must visit every square, when the knight is on a B2 square in must move to an A2 next (otherwise the knight will need to make a repeat on an A2 square as well, but this is impossible). Image File history File links Grid4xnColoredSquares. ... Image File history File links Grid4xnColoredSquares. ...


If we follow the knight we will find a contradiction.

  1. The first square the knight goes to will be a square of A1 and A2. If it is not, we switch A2 and B2 so that it is true.
  2. The second square must be an element of the sets B1 and B2.
  3. The third square must be an element of A1 and A2.
  4. The fourth square must be an element of the sets B1 and B2.
  5. And so on.

It follows that set A1 has the same elements as set A2, and set B1 has the same elements as set B2. But this is obviously not true, as the red and green pattern shown above is not the same as a checkerboard pattern; the set of red squares is not the same as the set of black squares (or white, for that matter).


So our above assumption was false and there are no closed knight's tours for and 4 × n board, for any n.


Condition 3

Condition 3 is proved case by case. Attempting to construct a knight's tour on a 3 by 4, 3 by 6, or 3 by 8 will lead to definite failure.


3 by n boards with n not equal to 4, 6, or 8 can be shown to be possible with a repeated pattern.


All other cases

Simply proving the above three conditions does not prove the theorem; it is still required to prove that all rectangular boards that do not fall in one of the above three categories have knight's tours.


See also

Abu-Bakr Muhammad ben Yahya as-Suli (circa 880 - 946) was an Arab shatranj (an ancestor of chess) player who came to prominence sometime in between 902 and 908 when he beat al-Mawardi, the court shatranj champion of al-Mukafti, the Caliph of Baghdad. ... The longest uncrossed (or nonintersecting) knights path is a mathematical problem involving a knight on a standard 8 Ã— 8 chessboard or, more generally, on a square n Ã— n board. ... In graph theory, a knights tour graph is a graph that represents all legal moves of the knight piece on a chessboard where each vertex represents a square on a chessboard and each edge is a legal move. ... An engraving of the Turk from Karl Gottlieb von Windischs 1784 book Inanimate Reason The Turk was a famous hoax that purported to be a chess-playing machine. ...

References

  1. ^ Wegener, I. (January 1, 1987). Branching Programs and Binary Decision Diagrams. Society for Industrial & Applied Mathematics. ISBN 0-898-71458-3. 
  2. ^ A. Conrad, T. Hindrichs, H. Morsy, and I. Wegener. "Solution of the Knight's Hamiltonian Path Problem on Chessboards." Discrete Applied Math, volume 50, no.2, pp.125-134. 1994.
  3. ^ Satyadev, Chaudhary. Kavyalankara of Rudrata (Sanskrit Text, with Hindi translation);. Delhi: Parimal Sanskrit Series No. 30. 
  • Watkins, John J. Across the Board: the Mathematics of Chessboard Problems. Princeton UP, 2004.

Hindi ( , Devanagari: or , IAST: , IPA: ), an Indo-European language spoken mainly in northern and central India, is the official language of the Union along with English. ...

External links


 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m