Warnsdorff's algorithm

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.

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

A position Y is accessible from a position X if X can move to Y by a single knight's move, and Y has not yet been visited.

Define the accessibility of a position X to be the positions accessible from X.

Algorithm:
	clear the board (set all positions to 0)
	pick a random initial position on the board and call it X
	mark the board at X 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 X to be the position in S with minimum accessibility
		mark the board at X with the current move number

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;
}

External Links

• Warnsdorff's rule
• Preprint of Pohl's paper (freely accessible)