Knight's tour

From Wikipedia, the free encyclopedia

Jump to: navigation, search
An open knight's tour of a chessboard
An animation of the Knight's Tour.
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.

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. Creating a program to solve the knight's tour is a common problem given to computer science students.[1]

The knight's tour problem is an ancient problem dating back to as far as the 9th century.

Contents

[edit] Theory

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

[edit] 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.[3][4][5] 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.[6] No closed tours exist for smaller boards (this is a corollary of the following theorem).

[edit] 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

[edit] 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.

[edit] 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 A1 be the set of all squares that would be black and A2 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 B1 to be the set of green squares and B2 as the set of red squares. There are an equal number of red squares as green squares. Note that from a square in B1 the knight must next jump to a square in B2. And since the knight must visit every square once, when the knight is on a square in B2 it must move to a square in B1 next (otherwise the knight will need to travel to two squares in B1 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 A1 and B1. If it is not, we switch the definitions of B1 and B2 so that it is true.
  2. The second square must be an element of the sets A2 and B2.
  3. The third square must be an element of A1 and B1.
  4. The fourth square must be an element of the sets A2 and B2.
  5. And so on.

It follows that set A1 has the same elements as set B1, and set A2 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.

[edit] 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).

[edit] 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. [7]

[edit] Computer algorithms

Algorithms other than the simple brute-force search to find knight's tour solutions are discussed below.

[edit] Neural network solutions

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.[8] 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(Ni,j) is the state of the neuron connecting square i to square j, V(Ni,j) is the output of the neuron from i to j, and G(Ni,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.

[edit] Warnsdorff's algorithm

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.

Warnsdorff's algorithm is a heuristic method for solving the knight's tour, based on the rule of choosing the square among those immediately accessible by the knight move that would give the fewest possible knight's moves following the move to that square. In graph-theoretic terms, each move is made to the adjacent vertex with the least degree. (Pohl has devised a rule for breaking ties.) This algorithm may also more generally be applied to any graph. Although the Hamiltonian path problem is NP-hard in general, on many graphs that occur in practice this heuristic is able to successfully locate a solution in linear time.[9] The knight's tour is a special case.[10]

The algorithm was first described in "Des Rösselsprungs einfachste und allgemeinste Lösung" by H. C. Warnsdorff in 1823.[11]

[edit] Algorithm

Warnsdorff’s algorithm will do for any initial position of the knight on the board. All the possible squares which may be reached in one move from this position are located, and the number of moves that the knight would be able to make from each of these squares is found. [12] Then, the algorithm dictates that the knight move to the square that has the least number of possible following moves. The process is then repeated until each square has been visited.[13][14]

[edit] In 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.

[edit] 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;
}

[edit] In Java

In java the above code looks like this:

import java.util.Random;
 
public class ChessBoardTester {
   public static void main(String[] args) {
 
      // Helper methods... The tester is at the bottom.
      class ChessBoard {
         public ChessBoard(){
            boardLength = BOARD_SIZE;
            boardWidth = BOARD_SIZE;
            theBoard = new int[boardLength][boardWidth];
            moveNumber=0;
         }
 
         public int[] initialPosition(){
            Random generator = new Random();
            int[] pos = new int[2];
            pos[0] = generator.nextInt(boardLength);
            pos[1] = generator.nextInt(boardWidth);
            theBoard[ pos[0] ][ pos[1] ] = ++moveNumber;
            return pos;
         }
 
         public int[] nextMove(int[] pos){
            int xPos = pos[0];
            int yPos = pos[1];
            int accessibility = NUM_OF_MOVES;
 
            for (int i=0 ; i< NUM_OF_MOVES ; i++){
               int newX = xPos + MOVES[i][0];
               int newY = yPos + MOVES[i][1];
               int newAccessibility = getAccessibility(newX, newY);
 
               if( inRangeAndEmpty(newX, newY) && newAccessibility < accessibility ){
                  pos[0] = newX;
                  pos[1] = newY;
                  accessibility = newAccessibility;
               }
            }
 
            theBoard[ pos[0] ][ pos[1] ] = ++moveNumber;
            return pos;
         }
 
         private int getAccessibility(int x, int y){
            int accessibility = 0;
            for(int i=0; i < NUM_OF_MOVES ; i++){
               if ( inRangeAndEmpty(x + MOVES[i][0], y + MOVES[i][1] ) )
                  accessibility++;
            }
            return accessibility;
         }
 
         private boolean inRangeAndEmpty(int x, int y){
            return ( x < boardLength  && x >= 0 && y < boardWidth   && y >=0  &&
                theBoard[x][y] == 0 );
         }
 
         public void printBoard(){
            for (int i=0; i < boardLength ; i++){
               for (int j=0; j < boardWidth ; j++){
                  System.out.print(theBoard[i][j] + "\t");
               }
               System.out.print("\n");
            }
         }
 
         public int getSize(){
            return boardLength * boardWidth;
         }
 
         private final int BOARD_SIZE=10;
         private final int NUM_OF_MOVES = 8;
         private final int[][] MOVES ={{2,1},{2,-1},{1,2},{1,-2},{-1,2},{-1,-2},{-2,1},{-2,-1}};
 
         private int moveNumber;
         private int[][] theBoard;
         private int boardLength;
         private int boardWidth;
      }
 
/*********************************
 * Beggining of the Tester class *
 *********************************/
      // Initialize board 
      ChessBoard knightsChessBoard = new ChessBoard();
      int[] position = knightsChessBoard.initialPosition();
 
      // Determine the next position
      for (int i=1; i< knightsChessBoard.getSize() ; i++){
         position = knightsChessBoard.nextMove(position);
      }
 
      // Print board
      knightsChessBoard.printBoard();
 
   }
}

[edit] Variations

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

  • differently sized boards
  • variations on the way the knight moves

Two player games based on the idea have also been explored.

[edit] 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[15] 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.

[edit] See also

[edit] Notes

  1. ^ H. M. Deitel, P. J. Deitel. "Java How To Program Fifth Edition." Prentice Hall, Upper Saddle River, New Jersey, pp. 326-328. 2003.
  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. ^ Martin Loebbing; Ingo Wegener (1996). "The Number of Knight's Tours Equals 33,439,123,484,294 — Counting with Binary Decision Diagrams". The Electronic Journal of Combinatorics 3 (1): R5. http://www.combinatorics.org/Volume_3/Abstracts/v3i1r5.html.  Remark: The authors later admitted that the announced number is incorrect. According to McKay's report, the correct number is 13,267,364,410,532.
  4. ^ Brendan McKay (1997). "Knight's Tours on an 8x8 Chessboard". Technical Report TR-CS-97-03 (Department of Computer Science, Australian National University). http://www.combinatorics.org/Volume_3/Comments/v3i1r5.01.ps. 
  5. ^ Wegener, I. (January 1, 1987). Branching Programs and Binary Decision Diagrams. Society for Industrial & Applied Mathematics. ISBN 0-898-71458-3. 
  6. ^ Eric W. Weisstein, Knight's Tour at MathWorld.
  7. ^ Watkins, John J. (2004), Across the Board: the Mathematics of Chessboard Problems, Princeton University Press, ISBN 0691115036 
  8. ^ Y. Takefuji, K. C. Lee. "Neural network computing for knight's tour problems." Neurocomputing, 4(5):249-254, 1992.
  9. ^ Pohl, Ira (July 1967). "A method for finding Hamilton paths and Knight's tours". Communications of the ACM 10 (7): 446–449. doi:10.1145/363427.363463. http://portal.acm.org/citation.cfm?id=363463. 
  10. ^ Alwan, Karla; K. Waters (1992), "Finding Re-entrant Knight's Tours on N-by-M Boards" (PDF), ACM Southeast Regional Conference, New York, New York: ACM, pp. 377-382 
  11. ^ Alwan, Karla; K. Waters (1992), "Finding Re-entrant Knight's Tours on N-by-M Boards" (PDF), ACM Southeast Regional Conference, New York, New York: ACM, pp. 377-382 
  12. ^ Törnberg, Gunno (1999). "Warnsdorff's rule". http://web.telia.com/~u85905224/knight/eWarnsd.htm. Retrieved on 2008-9-25. 
  13. ^ Alwan, Karla; K. Waters (1992), "Finding Re-entrant Knight's Tours on N-by-M Boards" (PDF), ACM Southeast Regional Conference, New York, New York: ACM, pp. 377-382 
  14. ^ Cancela, Hector; Ernesto Mordecki (2006-08-31) (PDF). Counting Knight’s Tours through the Randomized Warnsdorff Rule. 
  15. ^ Satyadev, Chaudhary. Kavyalankara of Rudrata (Sanskrit Text, with Hindi translation);. Delhi: Parimal Sanskrit Series No. 30. 

[edit] External links

[edit] Implementations

Retrieved from "http://en.wikipedia.org/wiki/Knight%27s_tour"
Personal tools