knight´s tour[ edit ]


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

There are several billion solutions to the problem, of which about 122,000,000 have the knight finishing on the same square on which it begins.

Many variations on this topic have been studied by mathematicians, including Euler, during the centuries using:
  • 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. See How to solve the knight´s tour for instructions on solving the knight´s tour problem. Note however that, unlike the general Hamiltonian path problem, the knight´s tour problem can be solved in linear time (Conrad et al 1994).

The pattern made by a Knight´s Tour has often been used as a literary constraint. The earliest instance of this is found in Rudrata´s Kavyalankara written during the 9th century.

In the 20th century the Oulipo group of writers used it among many others. The most notable example is the 10x10 Knight Tour which sets the order of the chapters in Georges Perec´s novel A User´s Manual.

References
  • A. Conrad, T. Hindrichs, H. Morsy, and I. Wegener. "Solution of the Knight´s Hamiltonian Path Problem on Chessboards." Discrete Applied Math, volume 50, pp.125-134. 1994.


categories: myChess-Wiki | Chess history | Timeline of chess | Mechanical Turk | knight´s tour
article No 838 / last change on 2005-06-30, 11:01pm

back  write a new article  show all articles  


direct links: chess chess960 correspondence chess Fischer Random Chess chess terminology chess players chess opening


This article is based on the article knight´s tour from the free encyclopaedia Wikipedia and stands under the GNU-Licence for free documentation. In the Wikipedia a list of the authors is available.

9 chessplayers online and 1 in the chat! Games are being played: 426, Challenges: 2, Halfmoves up to now: 6.323.297
Copyright 2003-2017 Karkowski & Schulz - All rights reserved - privacy statement