The Knight’s Tour

A Knight’s Tour is a sequence of moves of a knight on a chessboard such that the knight lands on every square only once. If the knight’s tour ends on the square that it began on, then the tour path is closed. Otherwise, it is open.

Knight’s Tour | Source: Wikipedia

The Knight’s Tour is a common mathematical problem given to computer science students; it is a more general Hamiltonian path problem in graph theory. The Hamiltonian path problem is a problem of “determining whether a Hamiltonian path (a path in an undirected or directed graph that visits each vertex exactly once) exists in a given graph.”

One of the first mathematicians to analyse this problem was Euler. However, the first procedure for completing the Knight’s Tour was Warnsdorf’s rule, which was described by H.C. von Warnsdorf in 1823.

Warnsdorf’s Rule states that the knight should always move to the square from which the knight will have the “fewest onward moves”. There can be, of course, two squares which have the same number of onward moves, and consequently there are ways to break such ties, for example the methods devised by Pohl and Squirrel.

Is a Knight’s Tour always possible?

Allen Schwenk proved that for any m x n boards, where m is smaller or equal to n, a closed knight tour is always possible if one of the following conditions is met:

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

 

Hope you enjoyed today’s post. M x

 

Advertisements

3 comments

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s