User:Benhoman/Sandbox
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
[edit]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
[edit]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
[edit]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.
Pseudo code
[edit]
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
for every value of the variable i starting from zero ending at seven
for every value of the variable j starting from zero ending at seven
set board array at position i,j equal to zero to show that position hasn’t been reached yet
end for loop
end for loop
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++
[edit]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.
<source lang="cpp">
- include <stdio.h>
- include <stdlib.h>
- include <time.h>
int checkMovability( int[][ 8 ], int, int ); void printBoard( int[][ 8 ] );
int main()
{
int currentRow = rand() % 8, currentColumn = rand() % 8, moveNumber, counter = 1;
int vertical[ 8 ] = { -1, -2, -2, -1, 1, 2, 2, 1 }, horizontal[ 8 ] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int board[ 8 ][ 8 ] = { 0 };
int tourLength[ 65 ] = { 0 };
int tour, i;
srand( time(NULL) );
for (tour = 1; tour <= 1000; ++tour) {
while ( checkMovability( board, currentRow, currentColumn ) == 1 && counter <= 64 ) {
moveNumber = rand() % 8;
if ( board[ currentRow + vertical[ moveNumber ] ][ currentColumn + horizontal[ moveNumber ] ] == 0 ) {
// printf("inner if 1\n");
if ( ( currentRow + vertical[ moveNumber ] ) <= 7 && ( currentRow + vertical[ moveNumber ] ) >= 0 ) {
// printf("inner if 2\n");
if ( (currentColumn + horizontal[ moveNumber ]) <= 7 && ( currentColumn + horizontal[ moveNumber ] ) >= 0 ) {
currentRow += vertical[ moveNumber ];
currentColumn += horizontal[ moveNumber ];
board[ currentRow ][ currentColumn ] = counter;
++counter;
// printBoard( board );
// printf("Knight at %d %d\n", currentRow, currentColumn);
}
}
}
}
// printBoard( board );
// printf("No more moves can be made\n");
++tourLength[ counter - 1];
}
for (i = 0; i <= 64; ++i) {
printf("%d: %d\n", i, tourLength[ i ] );
}
return 0;
}
int checkMovability( int grid[][ 8 ], int row, int column ) {
int h[ 8 ] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int v[ 8 ] = { -1, -2, -2, -1, 1, 2, 2, 1 };
int move;
for (move = 0; move <= 7; ++move) {
if ( grid[ row + v[ move ] ][ column + h[ move ] ] == 0 ) {
if ( ( row + v[ move ] ) <= 7 && ( row + v[ move ] ) >= 0 ) {
if ( (column + h[ move ]) <= 7 && ( column + h[ move ] ) >= 0 ) {
// printf("checkMovability returned 1\n");
// printf("checkMovability says you can move v: %d h: %d\n", v[ move ], h[ move ] );
// printBoard( grid );
return 1;
}
}
}
}
return 0;
}
void printBoard( int grid[][ 8 ] )
{
int i, j;
printf("\n\n");
for (i = 0; i <= 7; i++) {
for (j = 0; j <= 7; j++) {
printf("%4d", grid[ i ][ j ] );
if ( (j + 1) % 8 == 0 )
printf("\n\n");
}
}
return;
}
References
[edit]- ^ 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}}: Unknown parameter|coauthors=ignored (|author=suggested) (help) - ^ 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.
- ^ 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}}: Unknown parameter|coauthors=ignored (|author=suggested) (help) - ^ Törnberg, Gunno (1999). "Warnsdorff's rule". Retrieved 2008-9-25.
{{cite web}}: Check date values in:|accessdate=(help) - ^ 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}}: Unknown parameter|coauthors=ignored (|author=suggested) (help) - ^ Cancela, Hector (2006-08-31). "Counting Knight's Tours through the Randomized Warnsdorff Rule".
{{cite journal}}: Cite journal requires|journal=(help); Unknown parameter|coauthors=ignored (|author=suggested) (help)