Jump to content

Warnsdorff's algorithm

Add links
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Nneonneo (talk | contribs) at 21:25, 30 November 2008 (→Pseudo code: lang=text). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Template:Fixbunching

Template:Fixbunching

An animation of the Knight's Tour.

Template:Fixbunching

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.

Template:Fixbunching

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

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.[2] The knight's tour is a special case.[3]

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.[4] The algorithm then moves to the one that has the least amount of next possible moves and repeats the process again.[5][6]

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.

Pseudo code

board variable which is a two dimensional array representing the chess board

main Function
	moveNumber variable set equal to 2
	temp variable array of two integers
	move variable array of two integers
	positionx variable for the x coordinate of the position
	positiony variable for the y coordinate of the position
	clear the board (set all positions to 0)
	set board array at positionx,positiony equal to one for starting position
	for every value of i from zero to sixty three
		set move array at zero to positionx
		set move array at one to positiony
		call the getNetMoves function on the move array
		set positionx to move array at zero
		set positiony to move array at one
		set board array at positionx,positiony to the moveNumber counter
		increment moveNumber counter by one
	end for
end Main function

getNextMoves takes move array as input
	positionx variable to move array at zero
	positiony variable to move array at one
	accessibility variable set at eight for highest accessibility
	check each possible move from positionx, positiony to see if its on the board
	if the move is on the board and equal to zero
		call getAccessibilty function to check the accessibility
		if the returned value is less than the value of accessibility
			set accessibility to the returned value
		end if
	end if
end getNextMoves function

getAccessibility takes x and y coordinates
	set positionx variable to x
	set positiony variable to y
	create accessibility variable
	if each of the next possible moves are on the board and equal to zero
		increment the accessibility variable by one for each position that is possible and equal to zero
	end if
end getAccessibility function

Example of the Knight’s Tour Problem Solved in C++

The following code is an example of the source from a C++ file that will take an eight by eight chess board and solve the Knight’s Tour problem starting from a random position on the chess board. 

#include <cstdlib>
#include <iostream>

using namespace std;

void getNextMoves(int move[]);
int getAccessibility(int x, int y);
int board [8][8];

int main() {
	srand((unsigned)time(0));
	int positionx = (rand()%8);
	int positiony = (rand()%8);
	int moveNumber = 2;
	int temp [2];
	int move [2];
	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) {
			board[i][j] = 0;
		}
	}

	board[positionx][positiony] = 1;
	for (int i = 1; i < 64; i++) {
		move[0] = positionx;
		move[1] = positiony;
		getNextMoves(move);
		positionx = move[0];
		positiony = move[1];
		board[positionx][positiony] = moveNumber;
		moveNumber++;
	}
	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) {
			cout << board[i][j] << "\t";
		}
		cout << "\n\n";
	}
	return 0;
}

void getNextMoves(int move[]) {
	int positionx = move[0];
	int positiony = move[1];
	int accessibility = 8;
	if (((positionx + 2) < 8) && ((positiony + 1) < 8) && (board[positionx + 2][positiony + 1] == 0)) {
		if((getAccessibility((positionx + 2), (positiony + 1)) < accessibility)) {
			accessibility = getAccessibility((positionx + 2), (positiony + 1));
			move[0] = positionx + 2;
			move[1] = positiony + 1;
		}
	}
	if(((positionx + 2) < 8) && ((positiony - 1) >= 0) && (board[positionx + 2][positiony - 1] == 0)) {
		if((getAccessibility((positionx + 2), (positiony - 1)) < accessibility)) {
			accessibility = getAccessibility((positionx + 2), (positiony - 1));
			move[0] = positionx + 2;
			move[1] = positiony - 1;
		}
	}
	if(((positionx + 1) < 8) && ((positiony + 2) < 8) && (board[positionx + 1][positiony + 2] == 0)) {
		if((getAccessibility((positionx + 1), (positiony + 2)) < accessibility)) {
			accessibility = getAccessibility((positionx + 1), (positiony + 2));
			move[0] = positionx + 1;
			move[1] = positiony + 2;
		}
	}
	if(((positionx + 1) < 8) && ((positiony - 2) >= 0) && (board[positionx + 1][positiony - 2] == 0)) {
		if((getAccessibility((positionx + 1), (positiony - 2)) < accessibility)) {
			accessibility = getAccessibility((positionx + 1), (positiony - 2));
			move[0] = positionx + 1;
			move[1] = positiony - 2;
		}
	}
	if(((positionx - 1) >= 0) && ((positiony + 2) < 8) && (board[positionx - 1][positiony + 2] == 0)) {
		if((getAccessibility((positionx - 1), (positiony + 2)) < accessibility)) {
			accessibility = getAccessibility((positionx - 1), (positiony + 2));
			move[0] = positionx - 1;
			move[1] = positiony + 2;
		}
	}
	if(((positionx - 1) >= 0) && ((positiony - 2) >= 0) && (board[positionx - 1][positiony - 2] == 0)) {
		if((getAccessibility((positionx - 1), (positiony - 2)) < accessibility)) {
			accessibility = getAccessibility((positionx - 1), (positiony - 2));
			move[0] = positionx - 1;
			move[1] = positiony - 2;
		}
	}
	if(((positionx - 2) >= 0) && ((positiony + 1) < 8) && (board[positionx - 2][positiony + 1] == 0)) {
		if((getAccessibility((positionx - 2), (positiony + 1)) < accessibility)) {
			accessibility = getAccessibility((positionx - 2), (positiony + 1));
			move[0] = positionx - 2;
			move[1] = positiony + 1;
		}
	}
	if(((positionx - 2) >= 0) && ((positiony - 1) >= 0) && (board[positionx - 2][positiony - 1] == 0)) {
		if((getAccessibility((positionx - 2), (positiony - 1)) < accessibility)) {
			accessibility = getAccessibility((positionx - 2), (positiony - 1));
			move[0] = positionx - 2;
			move[1] = positiony - 1;
		}
	}
}

int getAccessibility(int x, int y) {
	int positionx = x;
	int positiony = y;
	int accessibility = 0;
	if (((positionx + 2) < 8) && ((positiony + 1) < 8)
	&& (board[positionx + 2][positiony + 1] == 0))
		accessibility++;

	if (((positionx + 2) < 8) && ((positiony - 1) >= 0)
	&& (board[positionx + 2][positiony - 1] == 0))
		accessibility++;

	if (((positionx + 1) < 8) && ((positiony + 2) < 8)
	&& (board[positionx + 1][positiony + 2] == 0))
		accessibility++;

	if (((positionx + 1) < 8) && ((positiony - 2) >= 0)
	&& (board[positionx + 1][positiony - 2] == 0))
		accessibility++;

	if (((positionx - 1) >= 0) && ((positiony + 2) < 8)
	&& (board[positionx - 1][positiony + 2] == 0))
		accessibility++;

	if (((positionx - 1) >= 0) && ((positiony - 2) >= 0) && (board[positionx - 1][positiony - 2] == 0))
		accessibility++;

	if (((positionx - 2) >= 0) && ((positiony + 1) < 8)
	&& (board[positionx - 2][positiony + 1] == 0))
		accessibility++;

	if (((positionx - 2) >= 0) && ((positiony - 1) >= 0) && (board[positionx - 2][positiony - 1] == 0))
		accessibility++;

	return accessibility;
}

References

  1. ^ Alwan, Karla (1992), "Finding Re-entrant Knight's Tours on N-by-M Boards", ACM Southeast Regional Conference, New York, New York: ACM, pp. 377–382 {{citation}}: |access-date= requires |url= (help); |format= requires |url= (help); Cite has empty unknown parameter: |coeditors= (help); Unknown parameter |coauthors= ignored (|author= suggested) (help)
  2. ^ 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.
  3. ^ Alwan, Karla (1992), "Finding Re-entrant Knight's Tours on N-by-M Boards", ACM Southeast Regional Conference, New York, New York: ACM, pp. 377–382 {{citation}}: |access-date= requires |url= (help); |format= requires |url= (help); Cite has empty unknown parameter: |coeditors= (help); Unknown parameter |coauthors= ignored (|author= suggested) (help)
  4. ^ Törnberg, Gunno (1999). "Warnsdorff's rule". Retrieved 2008-9-25. {{cite web}}: Check date values in: |accessdate= (help)
  5. ^ Alwan, Karla (1992), "Finding Re-entrant Knight's Tours on N-by-M Boards", ACM Southeast Regional Conference, New York, New York: ACM, pp. 377–382 {{citation}}: |access-date= requires |url= (help); |format= requires |url= (help); Cite has empty unknown parameter: |coeditors= (help); Unknown parameter |coauthors= ignored (|author= suggested) (help)
  6. ^ Cancela, Hector (2006-08-31). "Counting Knight's Tours through the Randomized Warnsdorff Rule". {{cite journal}}: |access-date= requires |url= (help); |format= requires |url= (help); Cite journal requires |journal= (help); Unknown parameter |coauthors= ignored (|author= suggested) (help)
Stub icon

This combinatorics-related article is a stub. You can help Wikipedia by expanding it.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Warnsdorff%27s_algorithm&oldid=255063492"