Knight's tour

An open knight's tour of a chessboard

An animation of the Knight's Tour.

File:Knight's tour graph.svg

Knight's graph showing all possible paths for a Knight's tour on a standard 8×8 chessboard. The numbers on each node indicate the number of possible moves that can be made from that position.

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.

A graphical representation of the Knight's Tour implemented using Warnsdorff's Algorithm. The numbers in red circles denote the number of next possible moves that the knight could make if it moves from the start position to the one with the circle on it.

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. A knight's tour is called a closed tour if the knight ends on a square attacking the square from which it began (so that it may tour the board again immediately with the same path). Otherwise the tour is open. The exact number of open tours is still unknown.

Theory

The knight's tour problem is an instance of the more general Hamiltonian path problem in graph theory. 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.

Closed tours

On an 8 × 8 board, there are exactly 26,534,728,821,064 (directed, i.e. two tours along the same path that travel in opposite directions are counted separately) closed tours. The number of undirected closed tours is half this number, since every tour can be traced in reverse. There are 9,862 undirected closed tours on a 6 × 6 board. No closed tours exist for smaller boards (this is a corollary of the following theorem).

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

One can show that condition 1 prohibits closed tours by a simple argument based on parity and coloring. For the standard black-and-white coloring of the chessboard, the knight must move either from a black square to a white square or from a white square to a black square. Thus in a closed tour the knight must visit the same number of white squares as black squares, and the number of squares visited in total must therefore be even. But if m and n are both odd, the total number of squares is odd. (For example, in a 5 × 5 checkerboard there are 13 of one color and 12 of the other.) Therefore closed tours do not exist. Open tours may still exist.

Condition 2

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

When m = 1 or 2, no closed tour is possible because the knight would not be able to reach every square (with the exception of the trivial case 1 × 1). It can be shown that a 4 × n board cannot have a closed tour either, by using a coloring argument.

The knight must alternate between green and red.

Start by assuming that a 4 × n board has a closed knight's tour. Let $A_{1}$ be the set of all squares that would be black and $A_{2}$ all the squares that would be white, if they were colored according to the alternating black-and-white checkerboard scheme. Consider the figure at right. Define $B_{1}$ to be the set of green squares and $B_{2}$ as the set of red squares. There are an equal number of red squares as green squares. Note that from a square in $B_{1}$ the knight must next jump to a square in $B_{2}$. And since the knight must visit every square once, when the knight is on a square in $B_{2}$ it must move to a square in $B_{1}$ next (otherwise the knight will need to travel to two squares in $B_{1}$ later).

If we follow the hypothetical knight's tour we will find a contradiction.

1. The first square the knight goes to will be a square of $A_{1}$ and $B_{1}$. If it is not, we switch the definitions of $B_{1}$ and $B_{2}$ so that it is true.
2. The second square must be an element of the sets $A_{2}$ and $B_{2}$.
3. The third square must be an element of $A_{1}$ and $B_{1}$.
4. The fourth square must be an element of the sets $B_{1}$ and $A_{1}$.
5. And so on.

It follows that set $A_{1}$ has the same elements as set $B_{1}$, and set $A_{2}$ has the same elements as set $B_{2}$. 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 may be proved using casework. Attempting to construct a closed 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 have closed tours by induction (a repeating 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 closed knight's tours (Watkins 2004).

Computer algorithms

Neural network solutions

File:Knightstour24x24.png

Knight's Tour on a 24 × 24 board solved by a neural network.

The Knight's Tour problem also lends itself to being solved by a neural network implementation. The network is set up such that every legal knight's move is represented by a neuron, and each neuron is initialized randomly to be either "active" or "inactive" (output of 1 or 0), with 1 implying that the neuron is part of the final solution. Each neuron also has a state function (described below) which is initialized to 0.

When the network is allowed to run, each neuron can change its state and output based on the states and outputs of its neighbors (adjacent knight's moves) according to the following transition rules:

$U_{t+1}(N_{i,j})=U_{t}(N_{i,j})+2-\sum _{N\in G(N_{i,j})}V_{t}(N)$

$V_{t+1}(N_{i,j})=\left\{{\begin{array}{ll}1&{\mbox{if}}\,\,U_{t+1}(N_{i,j})>3\\0&{\mbox{if}}\,\,U_{t+1}(N_{i,j})<0\\V_{t}(N_{i,j})&{\mbox{otherwise}},\end{array}}\right.$

where $t$ represents discrete intervals of time, $U(N_{i,j})$ is the state of the neuron connecting square $i$ to square $j$, $V(N_{i,j})$ is the output of the neuron from $i$ to $j$, and $G(N_{i,j})$ is the set of neighbors of the neuron.

Although divergent cases are possible, the network should eventually converge, which occurs when no neuron changes its state from time $t$ to $t+1$. When the network converges, a solution is found. The solution found by the network will be either a knight's tour, or a series of two or more independent knight's tours within the same board.

Variations

Many variations on this topic have been studied by mathematicians, including Euler, over the centuries using:

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

History

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

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.

Warnsdorff's algorithm is a heuristic method for solving the Knight's Tour. The algorithm was first described in "Des Rösselsprungs einfachste und allgemeinste Lösung" by H. C. Warnsdorff in 1823.

Overview

Warnsdorff's rule was to always choose the next square that had the fewest possible further knight's moves. This more generally can be applied to any graph, by always choosing the next node that has smallest degree. Pohl generalized this by adding a rule for breaking ties. Although the Hamiltonian path problem is NP-hard in general, on many graphs that occur in practice this linear-time heuristic is able to successfully locate a solution. The knight's tour is a special case.

How it Works

Warnsdorff’s algorithm for solving the Knight’s Tour problem works by placing the knight at any position on the board. The algorithm will then assess find the next possible moves it can take. From there the algorithm then calculates how many possible moves each of those next moves can make. The algorithm then moves to the one that has the least amount of next possible moves and repeats the process again.

What is the Knight’s Tour

The Knight’s Tour is an ancient puzzle, where the goal is to move a knight to every position on a chess board without going to the same place twice. The Knight's Tour is a common problem in Computer Science classes that students must solve by creating an algorithm in a programming language. Warnsdorff's algorithm is only one option. An example of another answer to this problem would be a brute force attack algorithm, where the program will go from move to move until it either finds a working tour or it can't move anymore in which case the program will backtrack and tries a different path.

Pseudocode

Some definitions:

• A position Q is accessible from a position P if P can move to Q by a single knight's move, and Q has not yet been visited.
• The accessibility of a position P is the number of positions accessible from P.

Algorithm:

set P to be a random initial position on the board
mark the board at P with the move number "1"
for each move number from 2 to the number of squares on the board,
	let S be the set of positions accessible from the input position
	set P to be the position in S with minimum accessibility
	mark the board at P with the current move number
return the marked board -- each square will be marked with the move number on which it is visited.

Example of the Knight's Tour Problem Solved in C

The following C code solves the Knight's Tour problem starting from a random position on a 10x10 chess board.

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

#define NUMMOVES 8
#define BOARDSIZE 10

const int moves[NUMMOVES][2]={{2,1},{2,-1},{1,2},{1,-2},{-1,2},{-1,-2},{-2,1},{-2,-1}};
int board [BOARDSIZE][BOARDSIZE];

int inRangeAndEmpty(const int posx, const int posy) {
	return (posx < BOARDSIZE && posx >= 0 && posy < BOARDSIZE && posy >= 0
		    && board[posx][posy] == 0);
}

int getAccessibility(const int x, const int y) {
	int accessibility = 0;
	int i;
	for(i=0;i<NUMMOVES;i++)
		if(inRangeAndEmpty(x+moves[i][0],y+moves[i][1]))
			accessibility++;

	return accessibility;
}

void getNextMoves(int move[]) {
	int positionx = move[0];
	int positiony = move[1];
	int newx,newy,newacc;
	int i;
	int accessibility=NUMMOVES;
	for(i=0;i<NUMMOVES;i++) {
		newx=positionx+moves[i][0];
		newy=positiony+moves[i][1];
		newacc=getAccessibility(newx,newy);
		if(inRangeAndEmpty(newx,newy) && newacc < accessibility) {
			move[0]=newx;
			move[1]=newy;
			accessibility=newacc;
		}
	}
}

int main() {
	srand((unsigned)time(0));
	int positionx = (rand()%BOARDSIZE);
	int positiony = (rand()%BOARDSIZE);
	int moveNumber = 2;
	int move [2];
	int i, j;

	// initialize board
	for (i = 0; i < BOARDSIZE; i++)
		for (j = 0; j < BOARDSIZE; j++)
			board[i][j] = 0;
	board[positionx][positiony] = 1;

	// compute moves
	for (i = 1; i < BOARDSIZE*BOARDSIZE; i++) {
		move[0] = positionx;
		move[1] = positiony;
		getNextMoves(move);
		positionx = move[0];
		positiony = move[1];
		board[positionx][positiony] = moveNumber;
		moveNumber++;
	}

	// print board
	for (i = 0; i < BOARDSIZE; i++) {
		for (j = 0; j < BOARDSIZE; j++) {
			printf("%d\t",board[i][j]);
		}
		printf("\n\n");
	}
	return 0;
}

References

• Watkins, John J. (2004), Across the Board: the Mathematics of Chessboard Problems, Princeton University Press, ISBN 978-0691130620

See also

• Abu-Bakr Muhammad ben Yahya as-Suli
• George Koltanowski
• Longest uncrossed knight's path
• Knight's tour graph

External links

• A Knight of Egodeth: Zen Raptured Quietude 240 Solutions to the Knights Tour in form of Game Book, published by Dr. Eugene "Roger" Apodaca
• Warnsdorff's rule II - Efficiency of Warnsdorff´s Rule
• Warnsdorff's Rule Web Page
• The ultimate Knight's Tour page of Links
• The knight's tour
• Knight's tour notes
• A Simple backtracking implementation in C++
• An implementation in C#
• Sloane's Integer Sequence A001230
• The Knight's Tour by Jay Warendorff based on a program by Arnd Roth, Wolfram Demonstrations Project.
• Knight's Tours Using a Neural Network Program that creates tours using a neural network, plus gallery of images.
• Warnsdorff's rule
• Preprint of Pohl's paper (freely accessible)